2024/08/10 by Halevi, Yatir, Kaplan, Itay, Shelah, Saharon
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2408.05605
Suppose that G is a graph of cardinality μ+ with chromatic number χ(G)≥ μ+. One possible reason that this could happen is if G contains a clique of size μ+. We prove that this is indeed the case when the edge relation is stable. When G is a random graph (which is simple but not stable), this is not true. But still if in general the complete theory of G is simple, G must contain finite cliques of unbounded sizes.