Turán extremal problem for H-free bounded matching

Extension to H-free graphs · arXiv:2210.15076

arXiv Informal medium confidence— first stated 2022-10-26

Authors: Noga Alon, Peter Frankl

Status partial high confidence

Gerbner (arXiv 2211.03272, J. Graph Theory 2024) directly took up this problem immediately after Alon–Frankl's paper, determining the maximum number of edges in n-vertex F-free graphs with matching number at most s apart from a constant additive term for all fixed F and s, with several exact results also obtained. The asymptotic form of the answer is thus settled for fixed parameters, but a complete exact determination for all H, n, s remains open. Ma and Hou (arXiv 2301.05625) subsequently extended the framework to the generalized Turán setting (counting copies of K_r).

Cited literature (2)

partial On Turán problems with bounded matching number (2022)

Dániel Gerbner · Journal of Graph Theory · arXiv:2211.03272 · doi:10.1002/jgt.23067

Determines the maximum number of edges in n-vertex F-free graphs with matching number at most s apart from a constant additive term for all fixed F and s, providing several exact results; directly extends the Alon–Frankl program to general forbidden subgraphs H.
partial Generalized Turán problem with bounded matching number (2023)

Yue Ma, Xinmin Hou · arXiv preprint · arXiv:2301.05625

Extends the bounded-matching-number framework to the generalized Turán problem, determining ex(n, K_r, {K_{k+1}, M_{s+1}}) exactly for r ≥ 3 and providing O(1)-error bounds for general H.

Reviewer notes. Gerbner's paper 2211.03272 was submitted just 12 days after the Alon–Frankl paper and is the principal follow-up; it is published in J. Graph Theory (DOI 10.1002/jgt.23067). The asymptotic answer for fixed F and s is settled, so the status is 'partial' rather than 'open'. Full exact determination for all parameters and all H remains open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Determine the maximum possible number of edges of an $H$-free graph on $n$ vertices with matching number at most $s$, for general forbidden subgraphs $H$ (extending Theorem 1.1 beyond the case $H = K_{k+1}$).

Context

At the opening of Section 3, the authors note it may be interesting to extend Theorem 1.1 by replacing the forbidden clique $K_{k+1}$ by other forbidden subgraphs $H$. Proposition 3.1 settles this for color-critical $H$ when $s$ and $n$ are sufficiently large, but the problem for general $H$ (including non-color-critical graphs and small parameters) remains open.

Notes. No labeled environment; posed as a research direction at the start of Section 3, partially addressed by Proposition 3.1 in the same section.

Source paper

Turán graphs with bounded matching number
Noga Alon, Peter Frankl · 2022-10-26
https://arxiv.org/abs/2210.15076 PDF source