A determinacy approach to Borel combinatorics

Marks, Andrew

doi:10.1090/jams/836

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
DOI: https://doi.org/10.1090/jams/836
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.

[1] Lewis Bowen, Weak isomorphisms between Bernoulli shifts, Israel J. Math. 183 (2011), 93–102. MR 2811154, https://doi.org/10.1007/s11856-011-0043-3
[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, https://doi.org/10.1090/conm/567/11234
[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, https://doi.org/10.4171/GGD/179
[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, https://doi.org/10.1017/S0143385711001143
[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, https://doi.org/10.1090/S0002-9939-2014-11918-6
[7] Clinton T. Conley, Measure-theoretic unfriendly colorings, Fund. Math. 226 (2014), no. 3, 237–244. MR 3229757, https://doi.org/10.4064/fm226-3-3
[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
[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, https://doi.org/10.1090/S0002-9939-10-10291-3
[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, https://doi.org/10.1016/0095-8956(92)90070-E
[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, https://doi.org/10.1142/S0219061302000138
[16] A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1–44. MR 1667145, https://doi.org/10.1006/aima.1998.1771
[17] Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597
[18] Alexander S. Kechris and Benjamin D. Miller, Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154
[19] M. Laczkovich, Closed sets without measurable matching, Proc. Amer. Math. Soc. 103 (1988), no. 3, 894–896. MR 947676, https://doi.org/10.1090/S0002-9939-1988-0947676-2
[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, https://doi.org/10.1016/j.ejc.2011.03.008
[21] Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 0403976, https://doi.org/10.2307/1971035
[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
[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, https://doi.org/10.4171/GGD/161