PreprintarXiv licencearXiv
A finite forbidden family with superlinear surplus and non-join extremal graphs
Abstract
We give a common counterexample to two product-structure conjectures in extremal graph theory. More precisely, we construct a fixed nonempty finite family ℒ with p(ℒ)=2 such that, for some c>0, ex(n,ℒ)>t2(n)+cn3/2 for every sufficiently large n. Nevertheless, at every such order there is an ℒ-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 ℒ to contain no forest. The construction uses endpoint-injective repair with a finite obstruction family admitting an exact extremal formula and equality classification.
Related
- Letter frequency in shifts of finite type with one forbidden word
- Sharp endpoint extension inequalities for the moment curve on finite fields II: an extremal property of the uniform distribution
- Maximal proper extremal subset in the crystal basis of a finite-dimensional irreducible module
- The relative dimension set of an extremal subfactor of finite index
- Extremal subspace covers in finite vector spaces
BibTeX
@misc{xu2026finite,
title = {{A finite forbidden family with superlinear surplus and non-join extremal graphs}},
author = {Chuandong Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.02115},
eprint = {2608.02115},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.02115},
}
RIS
TY - UNPB
TI - A finite forbidden family with superlinear surplus and non-join extremal graphs
AU - Chuandong Xu
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2608.02115
UR - https://arxiv.org/abs/2608.02115
AB - We give a common counterexample to two product-structure conjectures in extremal graph theory. More precisely, we construct a fixed nonempty finite family ℒ with p(ℒ)=2 such that, for some c>0, ex(n,ℒ)>t_2(n)+cn^3/2 for every sufficiently large n. Nevertheless, at every such order there is an ℒ-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 ℒ to contain no forest. The construction uses endpoint-injective repair with a finite obstruction family admitting an exact extremal formula and equality classification.
ER -