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 Free Access
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.
- 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
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
MR Author ID:
809431
Email:
marks@caltech.edu
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
