Extremal graph theory asks: given a forbidden subgraph, which graphs pack in the most copies of some fixed pattern? A central object here is the Turan graph, which is the densest graph on n vertices that avoids a complete graph of a given size. Researchers say a pattern graph H is "Turan-good" with respect to avoiding a clique of size r+1 if the Turan graph always maximizes the count of copies of H among all graphs that avoid that clique. A 2023 paper established that every graph H is Turan-good as long as r is at least roughly 300 times the ninth power of the number of vertices in H, but this left open whether the threshold could be brought down significantly.
This paper resolves both open questions posed in that 2023 work. First, it sharply improves the sufficient condition for Turan-goodness: it is enough that r is at least 168 times the number of edges in H, a bound that is linear in the edge count rather than a ninth-power function of the vertex count. For sparse graphs, where the number of edges grows proportionally to the number of vertices, this gives a linear condition in the vertex count, a dramatic improvement. The result also comes with a uniqueness guarantee, meaning the Turan graph is not just one maximizer but the only one, and a stability property saying that near-maximizers must structurally resemble the Turan graph.
Second, the paper shows that Turan-goodness does not automatically pass from one clique size to the next. One might hope that if H is Turan-good for avoiding r-cliques, it would remain so when you forbid slightly larger (r+1)-cliques instead. The paper constructs explicit counterexamples for every r at least 3, showing this monotonicity can fail. Combining both results, the paper pins down the threshold at which monotonicity eventually kicks in to within a factor that is between roughly h and h squared, where h is the number of vertices in H, leaving a gap that future work will need to close.