arxiv: 2605.01768 · v2 · submitted 2026-05-03 · 🧮 math.CO

Recognition: no theorem link

Hypergraph extensions of the Alon--Frankl Theorem and rainbow Tur\'an problems

Xiamiao Zhao , Yuanpei Wang , Junpeng Zhou

Authors on Pith no claims yet

Pith reviewed 2026-05-13 07:10 UTC · model grok-4.3

classification 🧮 math.CO

keywords hypergraph Turán problemsmatchingsexpansionsrainbow Turán numbersAlon-Frankl theoremcliquesextremal functionsforbidden subhypergraphs

0 comments

The pith

The maximum number of edges in an r-uniform hypergraph avoiding both a matching of size s+1 and the r-expansion of K_{ℓ+1} is determined exactly for small s and for large s.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper extends the Alon-Frankl theorem from graphs to hypergraphs by determining the maximum number of edges in an n-vertex r-uniform hypergraph that contains neither a matching M^r_{s+1} nor the r-expansion K_{ℓ+1}^{(r)+} of the complete graph K_{ℓ+1}. The exact maximum is found for all small s below (ℓ²-1)/2 and for all sufficiently large s, with the bound given by a standard balanced construction. The proof proceeds by first computing the rainbow hyper-Turán number for these expanded cliques, which extends a known graph result of Keevash, Saks, Sudakov and Verstraëte. The work partly confirms a conjecture of Gerbner, Tompkins and Zhou on hypergraph Turán problems with bounded matching number and highlights a direct link between ordinary and rainbow versions of the hyper-Turán problem.

Core claim

We determine the maximum number of hyperedges in an n-vertex r-uniform hypergraph containing neither a matching M^r_{s+1} nor the expansion K_{ℓ+1}^{(r)+} of the clique K_{ℓ+1} for all small s<(ℓ²-1)/2 and all sufficiently large s, respectively. This result partly confirms a conjecture proposed by Gerbner, Tompkins and Zhou. As a key tool, we determine the rainbow hyper-Turán number for expansions of cliques, which is the maximum sum of sizes of a sequence of hypergraphs containing no rainbow copy of a given expanded clique; this extends the graph result of Keevash, Saks, Sudakov and Verstraëte and shows a correlation between the hyper-Turán problem and the rainbow hyper-Turán number.

What carries the argument

The rainbow hyper-Turán number for expansions of cliques, defined as the largest possible sum of edge counts over a sequence of r-uniform hypergraphs with no rainbow copy of K_{ℓ+1}^{(r)+}.

If this is right

The extremal function ex(n, {M^r_{s+1}, K_{ℓ+1}^{(r)+}}) equals the size of the natural balanced construction for the stated ranges of s and ℓ.
The rainbow hyper-Turán number for clique expansions coincides with the classical hyper-Turán number in this setting.
Part of the conjecture on the maximum edges in hypergraphs with bounded matching number is confirmed.
The same rainbow technique applies directly to other families of expanded forbidden subhypergraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Rainbow methods may resolve additional classical hypergraph extremal problems that remain open in the non-rainbow setting.
For intermediate values of s between the small and large regimes, a different extremal construction may be needed.
The observed correlation suggests that rainbow variants can serve as a general tool for bounding ordinary Turán numbers in uniform hypergraphs.

Load-bearing premise

The rainbow hyper-Turán number for the expanded cliques equals exactly the threshold value needed to force the claimed extremal construction for all sufficiently large n.

What would settle it

An r-uniform hypergraph on sufficiently large n vertices with strictly more edges than the claimed maximum, while containing neither a matching of size s+1 nor a copy of K_{ℓ+1}^{(r)+}, for some s in the small or large range.

read the original abstract

Given a graph $F$, the $r$-expansion $F^{(r)+}$ of $F$ is the $r$-uniform hypergraph obtained from $F$ by inserting $r-2$ new distinct vertices in each edge of $F$. Recently, Alon and Frankl (JCTB, 2024) and Gerbner (JGT, 2023) studied the maximum number of edges in $n$-vertex $F$-free graphs with bounded matching number, respectively. Gerbner, Tompkins and Zhou (EJC, 2025) considered the analogous Tur\'{a}n problems on hypergraphs with bounded matching number. In this paper, we study hypergraph extensions of the Alon--Frankl Theorem. More precisely, we determine the maximum number of hyperedges in an $n$-vertex $r$-uniform hypergraph containing neither a matching $M^r_{s+1}$ nor the expansion $K_{\ell+1}^{(r)+}$ of the clique $K_{\ell+1}$ for all small $s<\frac{\ell^2-1}{2}$ and all sufficiently large $s$, respectively. This result partly confirms a conjecture proposed by Gerbner, Tompkins and Zhou (EJC, 2025). As a key tool, we determine the rainbow hyper-Tur\'{a}n number for expansions of cliques, which is defined as the maximum sum of size of a sequence of hypergraphs $\mathcal{H}_1,\dots,\mathcal{H}_k$ that contains no rainbow copies of expansions of cliques with given size. It extends the result of Keevash, Saks, Sudakov and Verstra{\"e}te (AAM, 2004), which determined the rainbow Tur\'an number of cliques in the graph case. These results shows a correlation between the hyper-Tur\'an problem and the rainbow hyper-Tur\'an number.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles the joint extremal number for r-uniform hypergraphs avoiding both a matching of size s+1 and the expansion of K_{ℓ+1} in the small-s and large-s regimes, using a new rainbow hyper-Turán number as the main tool.

read the letter

The main point is that the authors settle the maximum size of an r-uniform hypergraph on n vertices with no matching of size s+1 and no copy of the r-expansion of K_{ℓ+1}, for s below (ℓ²-1)/2 and for all sufficiently large s. They achieve this by first finding the rainbow hyper-Turán number for the expansions, which is the max sum of edges over a sequence of hypergraphs without rainbow copies of the forbidden expansion. This rainbow number extends the graph result from Keevash, Saks, Sudakov and Verstraëte in 2004 to the hypergraph setting, and it serves as the key auxiliary to control the ordinary extremal function. The paper shows a correlation between the two problems, which is a nice structural observation. What stands out is the clean separation into small and large s cases, each handled by stability methods that push the hypergraph toward one of the two natural constructions: one with bounded matching or the Turán hypergraph avoiding the expansion. This partly confirms the conjecture of Gerbner, Tompkins and Zhou. The arguments appear consistent with prior work on Alon-Frankl theorems and hypergraph Turán problems. The weaker parts are the open interval for intermediate s, where the behavior might be more complicated, and the fact that everything is asymptotic for large n. The rainbow determination itself relies on the value being exactly what is needed to force the bound, which holds in the stated ranges but would benefit from explicit checks in small cases if possible. This paper is for researchers in extremal combinatorics focused on hypergraphs and rainbow variants. A reader interested in matching-constrained problems or rainbow Turán numbers will find it useful. It shows clear thinking and honest engagement with the literature, so it deserves a serious referee rather than a desk rejection.

Referee Report

0 major / 3 minor

Summary. The manuscript determines the extremal number ex(n, {M^r_{s+1}, K_{ℓ+1}^{(r)+}}) for r-uniform hypergraphs on n vertices, for all s < (ℓ²-1)/2 and all sufficiently large s (with n large). The proof proceeds by first establishing the exact value of the rainbow hyper-Turán number for the family of K_{ℓ+1}^{(r)+} expansions, then applying stability to show that any extremal hypergraph must be either a bounded matching or the Turán hypergraph for the expansion; this partly confirms the Gerbner-Tompkins-Zhou conjecture.

Significance. If the derivations hold, the work supplies the first exact results for hypergraph Turán problems with an additional matching-number constraint, extends the rainbow Turán theorem of Keevash-Saks-Sudakov-Verstraëte from graphs to hypergraphs, and exhibits a direct correlation between the rainbow auxiliary and the ordinary extremal function. The stability arguments for the two regimes of s constitute a technically substantive contribution to the field.

minor comments (3)

The abstract states the result for 'all small s < (ℓ²-1)/2' and 'all sufficiently large s' but does not indicate whether the two regimes meet or leave a gap; a sentence clarifying the transition (or its dependence on r and ℓ) would improve readability.
Notation for the rainbow hyper-Turán number is introduced without an explicit symbol in the abstract; defining it (e.g., as ex_rainbow(n, K_{ℓ+1}^{(r)+})) at first use would help readers track the auxiliary quantity through the argument.
The manuscript cites Gerbner-Tompkins-Zhou (EJC 2025) for the conjecture but does not compare the new ranges of s with those already settled in that paper; a short paragraph in the introduction would clarify the incremental progress.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive summary and recommendation of minor revision. We appreciate the recognition of the technical contributions, including the rainbow hyper-Turán result and the stability arguments in the two regimes of s. We will incorporate any minor suggestions into the revised version.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper derives the rainbow hyper-Turán number for clique expansions independently by extending the external Keevash-Saks-Sudakov-Verstraëte theorem on rainbow Turán numbers, then applies this auxiliary quantity to bound the primary extremal function (maximum edges without M^r_{s+1} or K_{ℓ+1}^{(r)+}). The main result for small s < (ℓ²-1)/2 and large s uses separate stability arguments that force the extremal construction once the rainbow threshold is reached; neither step reduces to self-definition, fitted inputs renamed as predictions, nor a load-bearing self-citation chain. The partial confirmation of the Gerbner-Tompkins-Zhou conjecture is a consequence of these independent derivations rather than an input assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of r-uniform hypergraphs, matchings, and edge expansions; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard axioms of extremal set theory and hypergraph Turán problems.
Invoked throughout the definitions of M^r_{s+1} and K_{ℓ+1}^{(r)+}.

pith-pipeline@v0.9.0 · 5670 in / 1318 out tokens · 54344 ms · 2026-05-13T07:10:13.521639+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

[1]

Alon and P

N. Alon and P. Frankl. Tur´ an graphs with bounded matching number.Journal of Com- binatorial Theory, Series B, 165:223–229, 2024

work page 2024
[2]

Bollob´ as, D

B. Bollob´ as, D. Daykin, and P. Erd¨ os. Sets of independent edges of a hypergraph.The Quarterly Journal of Mathematics, 27(1):25–32, 1976

work page 1976
[3]

Bradaˇ c, M

D. Bradaˇ c, M. Buci´ c, and B. Sudakov. Tur´ an numbers of sunflowers.Proceedings of the American Mathematical Society, 151(03):961–975, 2023

work page 2023
[4]

Chakraborti, J

D. Chakraborti, J. Kim, H. Lee, H. Liu, and J. Seo. On a rainbow extremal problem for color-critical graphs.Random Structures&Algorithms, 64(2):460–489, 2024. doi: 10.1002/rsa.21189. Also available as arXiv:2204.02575. 32

work page doi:10.1002/rsa.21189 2024
[5]

P. Erdos. A problem on independentr-tuples.Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math, 8(93-95):2, 1965

work page 1965
[6]

P. Erd˝ os. Topics in combinatorial analysis. InProceedings of the Second Louisiana Con- ference on Combinatorics, Graph Theory and Computing, pages 2–20. 1971

work page 1971
[7]

Erd¨ os and T

P. Erd¨ os and T. Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar, 10:337–356, 1959

work page 1959
[8]

Erdos and M

P. Erdos and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar, 1(51-57):51, 1966

work page 1966
[9]

Erd¨ os and A

P. Erd¨ os and A. Stone. On the structure of linear graphs.Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946

work page 1946
[10]

P. Frankl. Improved bounds for Erd˝ os’ matching conjecture.Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013

work page 2013
[11]

P. Frankl. On the maximum number of edges in a hypergraph with given matching number. Discrete Applied Mathematics, 216:562–581, 2017

work page 2017
[12]

P. Frankl. Proof of the Erd˝ os matching conjecture in a new range.Israel Journal of Mathematics, 222(1):421–430, 2017

work page 2017
[13]

Frankl and A

P. Frankl and A. Kupavskii. The Erd˝ os matching conjecture and concentration inequalities. Journal of Combinatorial Theory, Series B, 157:366–400, 2022

work page 2022
[14]

D. Gerbner. On Tur´ an problems with bounded matching number.Journal of Graph Theory, 106(1):23–29, 2024

work page 2024
[15]

Gerbner and S

D. Gerbner and S. Miao. Rainbow Tur´ an problems for a matching and any other graph. arXiv preprint arXiv:2505.14386, 2025

work page arXiv 2025
[16]

Gerbner, C

D. Gerbner, C. Tompkins, and J. Zhou. On hypergraph Tur´ an problems with bounded matching number.European Journal of Combinatorics, 127:104155, 2025

work page 2025
[17]

Huang, P.-S

H. Huang, P.-S. Loh, and B. Sudakov. The size of a hypergraph and its matching number. Combinatorics, Probability and Computing, 21(3):442–450, 2012

work page 2012
[18]

Keevash, D

P. Keevash, D. Mubayi, B. Sudakov, and J. Verstra¨ ete. Rainbow Tur´ an problems.Com- binatorics, Probability and Computing, 16(1):109–126, 2007

work page 2007
[19]

Keevash, M

P. Keevash, M. Saks, B. Sudakov, and J. Verstra¨ ete. Multicolour Tur´ an problems.Advances in Applied Mathematics, 33(2):238–262, 2004

work page 2004
[20]

Kolupaev and A

D. Kolupaev and A. Kupavskii. Erd˝ os matching conjecture for almost perfect matchings. Discrete Mathematics, 346(4):113304, 2023. 33

work page 2023
[21]

Kupavskii and G

A. Kupavskii and G. Sokolov. A complete solution of the Erd˝ os-Kleitman matching prob- lem forn≤3s.arXiv preprint arXiv:2511.21628, 2025

work page arXiv 2025
[22]

X. Li, J. Ma, and Z. Zheng. On the multicolor Tur´ an conjecture for color-critical graphs. Canadian Journal of Mathematics, 2025. Advance online publication. Also available as arXiv:2407.14905

work page arXiv 2025
[23]

Luczak and K

T. Luczak and K. Mieczkowska. On Erd˝ os’ extremal problem on matchings in hypergraphs. Journal of Combinatorial Theory, Series A, 124:178–194, 2014

work page 2014
[24]

D. Mubayi. A hypergraph extension of Tur´ an’s theorem.Journal of Combinatorial Theory, Series B, 96(1):122–134, 2006

work page 2006
[25]

Mubayi and J

D. Mubayi and J. Verstra¨ ete. Proof of a conjecture of Erd˝ os on triangles in set-systems. Combinatorica, 25(5):599–614, 2005

work page 2005
[26]

Mubayi and J

D. Mubayi and J. Verstra¨ ete. A survey of Tur´ an problems for expansions. InRecent trends in combinatorics, pages 117–143. Springer, 2016

work page 2016
[27]

Pikhurko

O. Pikhurko. Exact computation of the hypergraph Tur´ an function for expanded complete 2-graphs.Journal of Combinatorial Theory, Series B, 103(2):220–225, 2013

work page 2013
[28]

P. Tur´ an. Egy gr´ afelm´ eleti sz´ elso´ ert´ ekfeladatr´ ol.Mat. Fiz. Lapok, 48(3):436, 1941

work page 1941
[29]

C. Yang, J. Zeng, and X.-D. Zhang. A hypergraph analogue of Alon-Frankl theorem.arXiv preprint arXiv:2511.21096, 2025

work page arXiv 2025
[30]

Zhou and X

J. Zhou and X. Yuan. Linear Tur´ an problems with bounded matching number in hyper- graphs.Discrete Mathematics349 (2026) 114772. 34

work page 2026