← All papers
First page of A finite forbidden family with superlinear surplus and non-join extremal graphs

A finite forbidden family with superlinear surplus and non-join extremal graphs

Chuandong Xu

math.CO Aug 3, 2026 · v3
Provides a complete Lean 4 formalization of the main counterexample theorem and its general-p extension in a public GitHub repository.
We give a common counterexample to two product-structure conjectures in extremal graph theory. More precisely, we construct a fixed nonempty finite family $\mathcal L$ with $p(\mathcal L)=2$ such that, for some $c>0$, \[ \operatorname{ex}(n,\mathcal L)>t_2(n)+cn^{3/2} \] for every sufficiently large $n$. Nevertheless, at every such order there is an $\mathcal L$-extremal graph whose complement is connected and which therefore admits no decomposition as a join of two nonempty graphs. This superlinear surplus also forces the decomposition family of $\mathcal L$ to contain no forest. The construction uses endpoint-injective repair with a finite obstruction family admitting an exact extremal formula and equality classification.

Simonovits's Product Conjecture and a related conjecture on decomposition families predict product (join) structure for extremal graphs of forbidden families whose Turán number exceeds the Turán graph count by a superlinear amount. The goal is to refute both with a single finite family.

An endpoint-injective repair construction defines, from a base family B, the family of minimal non-repairable graphs, where repairs delete at most one vertex and two edges. An exact extremal formula ex(n,L)=ex(n-1,B)+n-1 and a classification of equality cases are proved. Applying this to B={O_6} gives a family with p=2 and superlinear surplus. Theorem 3.1 and the general-p extension are formalized in Lean 4, with the formalization produced by an AI model.

The family satisfies ex(n,L)>t_2(n)+cn^{3/2} and has an extremal graph with connected complement, so that graph is not a join. This refutes the Simonovits Product Conjecture for p=2 and shows the decomposition family contains no forest. The analogous statement holds for every p≥2. The Weak Product Conjecture is not refuted.