A determinacy approach to Borel combinatorics

Marks, Andrew¹

¹ Department of Mathematics, California Institute of Technology, Pasadena, California 91125

Journal of the American Mathematical Society, Tome 29 (2016) no. 2, pp. 579-600

Résumé

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

Détail

DOI : 10.1090/jams/836

Bibliographie

[1] Bowen, Lewis Weak isomorphisms between Bernoulli shifts Israel J. Math. 2011 93 102

[2] Bowen, Lewis Every countably infinite group is almost Ornstein 2012 67 78

[3] Conley, Clinton T., Kechris, Alexander S. Measurable chromatic and independence numbers for ergodic graphs and group actions Groups Geom. Dyn. 2013 127 180

[4] Conley, Clinton T., Kechris, Alexander S., Tucker-Drob, Robin D. Ultraproducts of measure preserving actions and graph combinatorics Ergodic Theory Dynam. Systems 2013 334 374

[5] Conley, Clinton, Miller, Benjamin Measurable matchings in acyclic countable finite Borel graphs

[6] Conley, Clinton T., Miller, Benjamin D. An antibasis result for graphs of infinite Borel chromatic number Proc. Amer. Math. Soc. 2014 2123 2133

[7] Conley, Clinton T. Measure-theoretic unfriendly colorings Fund. Math. 2014 237 244

[8] Csoka, Endre, Lippner, Gabor Invariant random matchings in Cayley graphs

[9] Diestel, Reinhard Graph theory 2005

[10] Dorais, Franã§Ois G., Dzhafarov, Damir D., Hirst, Jeffry L., Mileti, Joseph R., Shafer, Paul On uniform relationships between combinatorial problems

[11] Elek, Gã¡Bor, Lippner, Gã¡Bor Borel oracles. An analytical approach to constant-time algorithms Proc. Amer. Math. Soc. 2010 2939 2947

[12] Frieze, A. M., ŁUczak, T. On the independence and chromatic numbers of random regular graphs J. Combin. Theory Ser. B 1992 123 132

[13] Gao, Su, Jackson, Steve Countable abelian group actions and hyperfinite equivalence relations 2012

[14] Hatami, Hamed, Lovã¡Sz, Lã¡Szlã³, Szegedy, Balã¡Zs Limits of local-global convergent graph sequences

[15] Jackson, S., Kechris, A. S., Louveau, A. Countable Borel equivalence relations J. Math. Log. 2002 1 80

[16] Kechris, A. S., Solecki, S., Todorcevic, S. Borel chromatic numbers Adv. Math. 1999 1 44

[17] Kechris, Alexander S. Classical descriptive set theory 1995

[18] Kechris, Alexander S., Miller, Benjamin D. Topics in orbit equivalence 2004

[19] Laczkovich, M. Closed sets without measurable matching Proc. Amer. Math. Soc. 1988 894 896

[20] Lyons, Russell, Nazarov, Fedor Perfect matchings as IID factors on non-amenable groups European J. Combin. 2011 1115 1125

[21] Martin, Donald A. Borel determinacy Ann. of Math. (2) 1975 363 371

[22] Miller, Arnold W. Arnie Miller’s problem list 1993 645 654

[23] Miller, Benjamin D. The graph-theoretic approach to descriptive set theory Bull. Symbolic Logic 2012 554 575

[24] Seward, Brandon, Tucker-Drob, Robin D. Borel structurability on the 2-shift of a countable group

[25] Thomas, Simon Universal Borel actions of countable groups Groups Geom. Dyn. 2012 389 407