A determinacy approach to Borel combinatorics

Marks, Andrew

doi:10.1090/jams/836

A determinacy approach to Borel combinatorics
HTML articles powered by AMS MathViewer

by Andrew S. Marks

J. Amer. Math. Soc. 29 (2016), 579-600

DOI: https://doi.org/10.1090/jams/836

Published electronically: June 26, 2015

PDF | Request permission

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

Lewis Bowen, Weak isomorphisms between Bernoulli shifts, Israel J. Math. 183 (2011), 93–102. MR 2811154, DOI 10.1007/s11856-011-0043-3
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, DOI 10.1090/conm/567/11234
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, DOI 10.4171/GGD/179
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, DOI 10.1017/S0143385711001143
Clinton Conley and Benjamin Miller, Measurable matchings in acyclic countable finite Borel graphs. Preprint.
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, DOI 10.1090/S0002-9939-2014-11918-6
Clinton T. Conley, Measure-theoretic unfriendly colorings, Fund. Math. 226 (2014), no. 3, 237–244. MR 3229757, DOI 10.4064/fm226-3-3
Endre Csoka and Gabor Lippner, Invariant random matchings in Cayley graphs, available at arXiv:1211.2374.
Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
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.
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, DOI 10.1090/S0002-9939-10-10291-3
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, DOI 10.1016/0095-8956(92)90070-E
Su Gao and Steve Jackson, Countable abelian group actions and hyperfinite equivalence relations (2012). Preprint.
Hamed Hatami, László Lovász, and Balázs Szegedy, Limits of local-global convergent graph sequences, available at arXiv:1205.4356.
S. Jackson, A. S. Kechris, and A. Louveau, Countable Borel equivalence relations, J. Math. Log. 2 (2002), no. 1, 1–80. MR 1900547, DOI 10.1142/S0219061302000138
A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1–44. MR 1667145, DOI 10.1006/aima.1998.1771
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
Alexander S. Kechris and Benjamin D. Miller, Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154, DOI 10.1007/b99421
M. Laczkovich, Closed sets without measurable matching, Proc. Amer. Math. Soc. 103 (1988), no. 3, 894–896. MR 947676, DOI 10.1090/S0002-9939-1988-0947676-2
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, DOI 10.1016/j.ejc.2011.03.008
Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
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
Benjamin D. Miller, The graph-theoretic approach to descriptive set theory, Bull. Symbolic Logic 18 (2012), no. 4, 554–575. MR 3053069, DOI 10.2178/bsl.1804030
Brandon Seward and Robin D. Tucker-Drob, Borel structurability on the 2-shift of a countable group, available at arXiv:1402.4184.
Simon Thomas, Universal Borel actions of countable groups, Groups Geom. Dyn. 6 (2012), no. 2, 389–407. MR 2914864, DOI 10.4171/GGD/161