Turán number of a finite family.

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite nonempty family $\mathcal F$ of finite simple graphs, let $\operatorname{ex}(n,\mathcal F)$ be the maximum number of edges of an $n$-vertex graph containing no member of $\mathcal F$ as a subgraph; write $\operatorname{ex}(n,F)=\operatorname{ex}(n,\{F\})$. Let $C_j$ be the cycle of length $j$ and $e(G)=|E(G)|$. A graph is $F$-free if it contains no subgraph isomorphic to $F$.

Statement recorded in the supplied source.

For every such $\mathcal F$, is there a member $F\in\mathcal F$ and constants $C>0,n_0$ such that \[\operatorname{ex}(n,F)\le C\operatorname{ex}(n,\mathcal F)\qquad(n\ge n_0)?\] The source also asks the following stronger even-cycle question: for each integer $\ell\ge3$, does there exist $c(\ell)>0$ such that for every integer $2\le k<\ell$ and every $C_{2\ell}$-free graph $G$, some $C_{2k}$-free subgraph $H\subseteq G$ satisfies $e(H)\ge e(G)/c(\ell)$? [S2]

Short English statement

Can one forbidden graph in a finite family determine its extremal edge count up to a constant factor? The accompanying stronger question asks whether deleting a bounded fraction of edges avoids any shorter prescribed even cycle.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3127 (OPG-46706). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Turán number of a finite family., original node 46706, statement and mathematical discussion. https://www.openproblemgarden.org/op/turan_number_of_a_finite_family.