A determinacy approach to Borel combinatorics. (English) Zbl 1403.03088
Summary: We introduce a new method, involving infinite games and Borel determinacy, which we use to answer several well-known questions in Borel combinatorics.
MSC:
| 03E15 | Descriptive set theory |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 37A15 | General groups of measure-preserving transformations and dynamical systems |
References:
| [1] | Bowen, Lewis, Weak isomorphisms between Bernoulli shifts, Israel J. Math., 183, 93\textendash 102 pp. (2011) · Zbl 1253.37008 · doi:10.1007/s11856-011-0043-3 |
| [2] | Bowen, Lewis, Every countably infinite group is almost Ornstein. Dynamical systems and group actions, Contemp. Math. 567, 67\textendash 78 pp. (2012), Amer. Math. Soc., Providence, RI · Zbl 1277.37016 · doi:10.1090/conm/567/11234 |
| [3] | Conley, Clinton T.; Kechris, Alexander S., Measurable chromatic and independence numbers for ergodic graphs and group actions, Groups Geom. Dyn., 7, 1, 127\textendash 180 pp. (2013) · Zbl 1315.03082 · doi:10.4171/GGD/179 |
| [4] | Conley, Clinton T.; Kechris, Alexander S.; Tucker-Drob, Robin D., Ultraproducts of measure preserving actions and graph combinatorics, Ergodic Theory Dynam. Systems, 33, 2, 334\textendash 374 pp. (2013) · Zbl 1268.05104 · doi:10.1017/S0143385711001143 |
| [5] | Conley, Clinton; Miller, Benjamin, Measurable matchings in acyclic countable finite {B}orel graphs · Zbl 1496.03186 |
| [6] | Conley, Clinton T.; Miller, Benjamin D., An antibasis result for graphs of infinite Borel chromatic number, Proc. Amer. Math. Soc., 142, 6, 2123\textendash 2133 pp. (2014) · Zbl 1351.03037 · doi:10.1090/S0002-9939-2014-11918-6 |
| [7] | Conley, Clinton T., Measure-theoretic unfriendly colorings, Fund. Math., 226, 3, 237\textendash 244 pp. (2014) · Zbl 1341.03063 · doi:10.4064/fm226-3-3 |
| [8] | Csoka, Endre; Lippner, Gabor, Invariant random matchings in {C}ayley graphs · Zbl 1369.05102 |
| [9] | Diestel, Reinhard, Graph theory, Graduate Texts in Mathematics 173, xvi+411 pp. (2005), Springer-Verlag, Berlin · Zbl 1074.05001 |
| [10] | Dorais, Fran\c cois G.; Dzhafarov, Damir D.; Hirst, Jeffry L.; Mileti, Joseph R.; Shafer, Paul, On uniform relationships between combinatorial problems · Zbl 1528.03095 |
| [11] | Elek, G{\'a}bor; Lippner, G{\'a}bor, Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc., 138, 8, 2939\textendash 2947 pp. (2010) · Zbl 1200.68283 · doi:10.1090/S0002-9939-10-10291-3 |
| [12] | Frieze, A. M.; \L uczak, T., On the independence and chromatic numbers of random regular graphs, J. Combin. Theory Ser. B, 54, 1, 123\textendash 132 pp. (1992) · Zbl 0771.05088 · doi:10.1016/0095-8956(92)90070-E |
| [13] | Gao, Su; Jackson, Steve, Countable abelian group actions and hyperfinite equivalence relations (2012) · Zbl 1388.03044 |
| [14] | Hatami, Hamed; Lov{\'a}sz, L{\'a}szl{\'o}; Szegedy, Bal{\'a}zs, Limits of local-global convergent graph sequences · Zbl 1294.05109 |
| [15] | Jackson, S.; Kechris, A. S.; Louveau, A., Countable Borel equivalence relations, J. Math. Log., 2, 1, 1\textendash 80 pp. (2002) · Zbl 1008.03031 · doi:10.1142/S0219061302000138 |
| [16] | Kechris, A. S.; Solecki, S.; Todorcevic, S., Borel chromatic numbers, Adv. Math., 141, 1, 1\textendash 44 pp. (1999) · Zbl 0918.05052 · doi:10.1006/aima.1998.1771 |
| [17] | Kechris, Alexander S., Classical descriptive set theory, Graduate Texts in Mathematics 156, xviii+402 pp. (1995), Springer-Verlag, New York · Zbl 0819.04002 · doi:10.1007/978-1-4612-4190-4 |
| [18] | Kechris, Alexander S.; Miller, Benjamin D., Topics in orbit equivalence, Lecture Notes in Mathematics 1852, x+134 pp. (2004), Springer-Verlag, Berlin · Zbl 1058.37003 · doi:10.1007/b99421 |
| [19] | Laczkovich, M., Closed sets without measurable matching, Proc. Amer. Math. Soc., 103, 3, 894\textendash 896 pp. (1988) · Zbl 0668.28002 · doi:10.2307/2046871 |
| [20] | Lyons, Russell; Nazarov, Fedor, Perfect matchings as IID factors on non-amenable groups, European J. Combin., 32, 7, 1115\textendash 1125 pp. (2011) · Zbl 1229.05115 · doi:10.1016/j.ejc.2011.03.008 |
| [21] | Martin, Donald A., Borel determinacy, Ann. of Math. (2), 102, 2, 363\textendash 371 pp. (1975) · Zbl 0336.02049 |
| [22] | Miller, Arnold W., Arnie Miller’s problem list. Set theory of the reals, Ramat Gan, 1991, Israel Math. Conf. Proc. 6, 645\textendash 654 pp. (1993), Bar-Ilan Univ., Ramat Gan · Zbl 0828.03017 |
| [23] | Miller, Benjamin D., The graph-theoretic approach to descriptive set theory, Bull. Symbolic Logic, 18, 4, 554\textendash 575 pp. (2012) · Zbl 1361.03047 |
| [24] | Seward, Brandon; Tucker-Drob, Robin D., Borel structurability on the 2-shift of a countable group · Zbl 1403.03090 |
| [25] | Thomas, Simon, Universal Borel actions of countable groups, Groups Geom. Dyn., 6, 2, 389\textendash 407 pp. (2012) · Zbl 1284.03230 · doi:10.4171/GGD/161 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
