2021/03/25 by Yatir Halevi, Halevi, Yatir, Itay Kaplan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2103.13931
openalex publication_date 2021/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove a version of the strong Taylor's conjecture for stable graphs: if G is a stable graph whose chromatic number is strictly greater than \beth2(ℵ0) then G contains all finite subgraphs of Shn(ω) and thus has elementary extensions of unbounded chromatic number. This completes the picture from our previous work. The main new model theoretic ingredient is a generalization of the classical construction of Ehrenfeucht-Mostowski models to an infinitary setting, giving a new characterization of stability.