Infinite Stable Graphs With Large Chromatic Number

2020/07/23 by Halevi, Yatir, Kaplan, Itay, Shelah, Saharon
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2007.12139

Abstract

We prove that if G=(V,E) is an ω-stable (respectively, superstable) graph with χ(G)>ℵ₀ (respectively, 2^ℵ₀) then G contains all the finite subgraphs of the shift graph Sh_n(ω) for some n. We prove a variant of this theorem for graphs interpretable in stationary stable theories. Furthermore, if G is ω-stable with U(G)≤ 2 we prove that n≤ 2 suffices.

Related

• Infinite Stable Graphs With Large Chromatic Number II
• Infinite Cliques in Simple and Stable Graphs
• A note on hitting maximum and maximal cliques with a stable set
• On α⁺⁺-Stable Graphs
• On the Structure of α-Stable Graphs