Minimum degree stability of \(H\)-free graphs (Q6057487)

\textit{P. Erdős} and \textit{M. Simonovits} [Discrete Math. 5, 323--334 (1973; Zbl 0268.05121)] showed that if \(H\) is a fixed graph with chromatic number \(\chi(H)=r+1\), then \(H\)-free graphs \(G\) on \(n\) vertices have at most \(\left(1-1/r+o(1)\right)\binom{n}{2}\) edges, and any graph on \(n\) vertices which has \(\left(1-1/r+o(1)\right)\binom{n}{2}\) edges can be obtained from the \(r\)-partite Turán graph by adding and/or deleting \(o(n^{2})\) edges. In particular, it is close to being \((\chi(H)-1)\)-partite.\par It is now natural to ask if \(H\)-free graphs on \(n\) vertices with minimum degree \(cn\) are close to being \((\chi(H)-1)\)-partite. Define \(\delta(H)\) to be the infimum of all \(c\) such that every \(n\)-vertex graph \(G\) with minimum degree \(\geq cn\) can be made \(H\)-free by deleting \(o(n^{2})\) edges. For example, \textit{B. Andrásfai} et al. [ibid. 8, 205--218 (1974; Zbl 0284.05106)] showed that \(\delta_{K_{r+1}}=1-1/(r-1/3)\). \textit{N. Alon} and \textit{B. Sudakov} [Electron. J. Comb. 13, No. 1, Research paper R19, 9 p. (2006; Zbl 1085.05036)] observed (more than) the fact that if \(H=K_{r+1}(t)\), a complete multipartite graph with \(t\) vertices in each of the \((r+1)\) classes, then \(\delta_{K_{r+1}(t)}=1-1/(r-1/3)\). Now, of course, this implies, as any \(H\) with \(\chi(H)=r+1\) is a subgraph of \(K_{r+1}(t)\) for some \(t\) that \(\delta_{H}\leq 1-1/(r-1/3)\), however, the inequality may be strict, so accurate estimates of \(\delta_{H}\) are desirable. \par For 3-chromatic graphs \(H\), the paper under review shows that \(\delta_{H}=2/(2g+1)\) where \(g\) is the smallest positive integer for which there is not a homomorphism \(G\longrightarrow C_{2g+1}\) where \(C_{r}\) is the cycle of length \(r\). The result for \(H\) whose chromatic number is greater than 3 is more complicated. It is that there is a sequence of eleven graphs \((F_{g})_{g=1}^{11}\) and eleven constants \((c_{g})_{g=1}^{11}\) such that if \(r\geq 3\) and \(H\) has chromatic number \(r+1\) then if \(g\) is minimal such that there is no homomorphism \(H\longrightarrow K_{r-3}+F_{g}\) (here \(+\) denotes join) then \(\delta_{H}=1-1/(r-1+c_{g})\). If instead there is a homomorphism to all eleven graphs \(K_{r-3}+F_{g}\), there will be a least \(g\) such that there is no homomorphism \(H\longrightarrow K_{r-2}+C_{2g+1}\) and we then have the bounds \[1-\frac{1}{r-1+2./(2g-1)}\leq \delta_{H} \leq 1-\frac{1}{r-1+1/7}.\] The parameter \(\delta_{H}\) is also put into the context of approximate chromatic profiles. Proofs make much use of the regularity lemma and associated machinery.