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
Bibliographic 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. - © Copyright 2015 American Mathematical Society
- 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
- MathSciNet review: 3454384