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

arXiv2110.10931MaRDI QIDQ6504729

Author name not available (Why is that?)

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"omel, and Taraz that addressed the case where $H$ is an odd cycle, Balogh, Morris, Samotij, and Warnke proved that, for every $rge3$, 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.

This page was built for publication: On the typical structure of graphs not containing a fixed vertex-critical subgraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504729)