Infinite stable graphs with large chromatic number

Halevi, Yatir; Kaplan, Itay; Shelah, Saharon

doi:10.1090/tran/8570

Infinite stable graphs with large chromatic number
HTML articles powered by AMS MathViewer

by Yatir Halevi, Itay Kaplan and Saharon Shelah PDF

Trans. Amer. Math. Soc. 375 (2022), 1767-1799 Request permission

Abstract:

We prove that if $G=(V,E)$ is an $\omega$-stable (respectively, superstable) graph with $\chi (G)>\aleph _0$ (respectively, $2^{\aleph _0}$) then $G$ contains all the finite subgraphs of the shift graph $\mathrm {Sh}_n(\omega )$ for some $n$. We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if $G$ is $\omega$-stable with $\operatorname {U}(G)\leq 2$ we prove that $n\leq 2$ suffices.

References

G. Conant, A. Pillay, and C. Terry, A group version of stable regularity, Math. Proc. Cambridge Philos. Soc. 168 (2020), no. 2, 405–413. MR 4064112, DOI 10.1017/s0305004118000798
Saharon Shelah and Moran Cohen, Stable theories and representation over sets, MLQ Math. Log. Q. 62 (2016), no. 3, 140–154. MR 3509699, DOI 10.1002/malq.200920105
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
P. Erdős and A. Hajnal, On chromatic number of infinite graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 83–98. MR 0263693
P. Erdős, A. Hajnal, and S. Shelah, On some general properties of chromatic numbers, Topics in topology (Proc. Colloq., Keszthely, 1972) Colloq. Math. Soc. János Bolyai, Vol. 8, North-Holland, Amsterdam, 1974, pp. 243–255. MR 0357194
P. Erdös and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249–255. MR 37886, DOI 10.1112/jlms/s1-25.4.249
András Hajnal and Péter Komjáth, What must and what need not be contained in a graph of uncountable chromatic number?, Combinatorica 4 (1984), no. 1, 47–52. MR 739412, DOI 10.1007/BF02579156
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Péter Komjáth, The chromatic number of infinite graphs—a survey, Discrete Math. 311 (2011), no. 15, 1448–1450. MR 2800970, DOI 10.1016/j.disc.2010.11.004
Péter Komjáth and Saharon Shelah, Finite subgraphs of uncountably chromatic graphs, J. Graph Theory 49 (2005), no. 1, 28–38. MR 2130468, DOI 10.1002/jgt.20060
Benoit Mariou, Modeles engendres par des indiscernables et modeles satures, PhD thesis, 1999. Thèse de doctorat dirigée par Bouscaren, Élisabeth Logique et fondements de l’informatique Paris 7 1999.
Benoît Mariou, Modèles saturés et modèles engendrés par des indiscernables, J. Symbolic Logic 66 (2001), no. 1, 325–348 (French, with English summary). MR 1825188, DOI 10.2307/2694925
M. Malliaris and S. Shelah, Regularity lemmas for stable graphs, Trans. Amer. Math. Soc. 366 (2014), no. 3, 1551–1585. MR 3145742, DOI 10.1090/S0002-9947-2013-05820-5
Anand Pillay, Geometric stability theory, Oxford Logic Guides, vol. 32, The Clarendon Press, Oxford University Press, New York, 1996. Oxford Science Publications. MR 1429864
Klaus-Peter Podewski and Martin Ziegler, Stable graphs, Fund. Math. 100 (1978), no. 2, 101–107. MR 485336, DOI 10.4064/fm-100-2-101-107
Philipp Rothmaler, Stationary types in modules, Z. Math. Logik Grundlag. Math. 29 (1983), no. 5, 445–464. MR 716859, DOI 10.1002/malq.19830290805
Saharon Shelah, Divide and Conquer: Dividing lines on universality.
Saharon Shelah, Classification theory and the number of nonisomorphic models, Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam-New York, 1978. MR 513226
Saharon Shelah, Superstable theories and representation, Sarajevo J. Math. 16(29) (2020), no. 1, 71–82. MR 4144091, DOI 10.5644/sjm
Combinatorial structures and their applications, volume 1969 of Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications held at the University of Calgary, Calgary, Alberta, Canada, June. Gordon and Breach, Science Publishers, New York-London-Paris, 1970.
Walter Taylor, Atomic compactness and elementary equivalence, Fund. Math. 71 (1971), no. 2, 103–112. MR 299550, DOI 10.4064/fm-71-2-103-112
Carsten Thomassen, Cycles in graphs of uncountable chromatic number, Combinatorica 3 (1983), no. 1, 133–134. MR 716429, DOI 10.1007/BF02579349
Katrin Tent and Martin Ziegler, A course in model theory, Lecture Notes in Logic, vol. 40, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012. MR 2908005, DOI 10.1017/CBO9781139015417