Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 956

Preprint Number 956

Previous Next Preprint server

956. Maryanthe Malliaris, Caroline Terry
On unavoidable induced subgraphs in large prime graphs

Submission date: 9 November 2015


Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present paper we reprove their theorem using many of the same ideas, but with the key model-theoretic ingredient of first determining the so-called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof which implies the finite result.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1511.02544: pdf, ps.

Last updated: November 25 2015 16:09 Please send your corrections to: