On the typical structure of graphs not containing a fixed vertex-critical subgraph

Abstract

This work studies the typical structure of sparse $H$-free graphs, that is, graphs that do not contain a subgraph isomorphic to a given graph $H$. Extending the seminal result of Osthus, Prömel, and Taraz that addressed the case where $H$ is an odd cycle, Balogh, Morris, Samotij, and Warnke proved that, for every $r\ge 3$, the structure of a random $K_{r+1}$-free graph with $n$ vertices and $m$ edges undergoes a phase transition when $m$ crosses an explicit (sharp) threshold function $m_r(n)$. They conjectured that a similar threshold phenomenon occurs when $K_{r+1}$ is replaced by any strictly $2$-balanced, edge-critical graph $H$. In this paper, we resolve this conjecture. In fact, we prove that the structure of a typical $H$-free graph undergoes an analogous phase transition for every $H$ in a family of vertex-critical graphs that includes all edge-critical graphs.

54 pages; minor edits; to appear in Random Structures and Algorithms (RSA)

References in corpus (4)

• On the number of graphs without large cliques
• The typical structure of sparse $K_{r+1}$-free graphs
• An efficient container lemma
• On the typical structure of graphs not containing a fixed vertex-critical subgraph

Cited by in corpus (1)

• On the typical structure of graphs not containing a fixed vertex-critical subgraph