Measurable chromatic and independence numbers for ergodic graphs and group actions

Creators: Conley, Clinton T.; Kechris, Alexander S.

Abstract

We study in this paper combinatorial problems concerning graphs generated by measure preserving actions of countable groups on standard measure spaces. In particular we study chromatic and independence numbers, in both the measure-theoretic and the Borel context, and relate the behavior of these parameters to properties of the acting group such as amenability, Kazhdan's property (T), and freeness. We also prove a Borel analog of the classical Brooks' Theorem in finite combinatorics for actions of groups with finitely many ends.

Additional Information

© 2013 European Mathematical Society. Received July 9, 2010; revised August 2, 2011. The authors would like to thank M. Abért, G. Elek, G. Hjorth, A. Ioana, R. Lyons, B. Miller, Y. Shalom, B. Sudakov, S. Thomas, B. Weiss and the referees for many useful conversations and suggestions, and wish to extend additional thanks to B. Miller for allowing inclusion of Lemma 3.2. M.Abért and G. Elek pointed out an error in our original proof of a version of Theorem 0.1 (ii). This has now been repaired by an alternative argument (see 2.19, 2.20). G. Elek has also independently suggested a somewhat related proof. A. S. Kechris was partially supported by NSF Grant DMS-0968710, the E. Schrödinger Institute, Vienna, and the Mittag-Leffler Institute, Djursholm.

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes

Measurable chromatic and independence numbers for ergodic graphs and group actions

Abstract

Additional Information

Additional details