A finite forbidden family with superlinear surplus and no three-factor product extremizers

Abstract

We construct a fixed finite family $\mathcal{L}$ of ordinary forbidden subgraphs with $p(\mathcal{L})=3$ and a constant $c>0$ such that $$ex(n,\mathcal{L})>t_3(n)+c{n}^{3/2}$$ at every sufficiently large order. Nevertheless, the complement of every sufficiently large $\mathcal{L}$-extremal graph has at most two connected components. In particular, no such extremal graph is a complete join of three graphs of positive order. This gives a negative answer to a natural existence-only question motivated by the Simonovits Product Conjecture, in which one asks only for one product extremizer at each sufficiently large order.

8 pages