Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



A determinacy approach to Borel combinatorics

Author: Andrew S. Marks
Journal: J. Amer. Math. Soc. 29 (2016), 579-600
MSC (2010): Primary 03E15; Secondary 05C15, 05C70, 37A15
Published electronically: June 26, 2015
MathSciNet review: 3454384
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a new method, involving infinite games and Borel determinacy, which we use to answer several well-known questions in Borel combinatorics.

References [Enhancements On Off] (What's this?)

  • [1] Lewis Bowen, Weak isomorphisms between Bernoulli shifts, Israel J. Math. 183 (2011), 93-102. MR 2811154 (2012k:37008),
  • [2] Lewis Bowen, Every countably infinite group is almost Ornstein, Dynamical systems and group actions, Contemp. Math., vol. 567, Amer. Math. Soc., Providence, RI, 2012, pp. 67-78. MR 2931910,
  • [3] Clinton T. Conley and Alexander S. Kechris, Measurable chromatic and independence numbers for ergodic graphs and group actions, Groups Geom. Dyn. 7 (2013), no. 1, 127-180. MR 3019078,
  • [4] Clinton T. Conley, Alexander S. Kechris, and Robin D. Tucker-Drob, Ultraproducts of measure preserving actions and graph combinatorics, Ergodic Theory Dynam. Systems 33 (2013), no. 2, 334-374. MR 3035288,
  • [5] Clinton Conley and Benjamin Miller, Measurable matchings in acyclic countable finite Borel graphs. Preprint.
  • [6] Clinton T. Conley and Benjamin D. Miller, An antibasis result for graphs of infinite Borel chromatic number, Proc. Amer. Math. Soc. 142 (2014), no. 6, 2123-2133. MR 3182030,
  • [7] Clinton T. Conley, Measure-theoretic unfriendly colorings, Fund. Math. 226 (2014), no. 3, 237-244. MR 3229757,
  • [8] Endre Csoka and Gabor Lippner, Invariant random matchings in Cayley graphs, available at arXiv:1211.2374.
  • [9] Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259 (2006e:05001)
  • [10] François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer, On uniform relationships between combinatorial problems, available at arXiv:1212.0157.
  • [11] Gábor Elek and Gábor Lippner, Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2939-2947. MR 2644905 (2011g:03117),
  • [12] A. M. Frieze and T. Łuczak, On the independence and chromatic numbers of random regular graphs, J. Combin. Theory Ser. B 54 (1992), no. 1, 123-132. MR 1142268 (92m:05170),
  • [13] Su Gao and Steve Jackson, Countable abelian group actions and hyperfinite equivalence relations (2012). Preprint.
  • [14] Hamed Hatami, László Lovász, and Balázs Szegedy, Limits of local-global convergent graph sequences, available at arXiv:1205.4356.
  • [15] S. Jackson, A. S. Kechris, and A. Louveau, Countable Borel equivalence relations, J. Math. Log. 2 (2002), no. 1, 1-80. MR 1900547 (2003f:03066),
  • [16] A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1-44. MR 1667145 (2000e:03132),
  • [17] Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)
  • [18] Alexander S. Kechris and Benjamin D. Miller, Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154 (2005f:37010)
  • [19] M. Laczkovich, Closed sets without measurable matching, Proc. Amer. Math. Soc. 103 (1988), no. 3, 894-896. MR 947676 (89f:28018),
  • [20] Russell Lyons and Fedor Nazarov, Perfect matchings as IID factors on non-amenable groups, European J. Combin. 32 (2011), no. 7, 1115-1125. MR 2825538 (2012m:05423),
  • [21] Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363-371. MR 0403976 (53 #7785)
  • [22] Arnold W. Miller, Arnie Miller's problem list, Set theory of the reals (Ramat Gan, 1991) Israel Math. Conf. Proc., vol. 6, Bar-Ilan Univ., Ramat Gan, 1993, pp. 645-654. MR 1234292 (94m:03073)
  • [23] Benjamin D. Miller, The graph-theoretic approach to descriptive set theory, Bull. Symbolic Logic 18 (2012), no. 4, 554-575. MR 3053069
  • [24] Brandon Seward and Robin D. Tucker-Drob, Borel structurability on the 2-shift of a countable group, available at arXiv:1402.4184.
  • [25] Simon Thomas, Universal Borel actions of countable groups, Groups Geom. Dyn. 6 (2012), no. 2, 389-407. MR 2914864,

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 03E15, 05C15, 05C70, 37A15

Retrieve articles in all journals with MSC (2010): 03E15, 05C15, 05C70, 37A15

Additional Information

Andrew S. Marks
Affiliation: Department of Mathematics, California Institute of Technology, Pasadena, California 91125

Received by editor(s): April 12, 2013
Received by editor(s) in revised form: April 29, 2015
Published electronically: June 26, 2015
Additional Notes: The author is partially supported by the National Science Foundation under grant DMS-1204907 and the John Templeton foundation under Award No. 15619.
The author would also like to thank the Institute for Mathematical Sciences and the Department of Mathematics of the National University of Singapore and the John Templeton Foundation for their support to attend the 2012 summer school in logic, where the main lemma of this paper was conceived.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society