arxiv: 2604.10928 · v1 · submitted 2026-04-13 · 🧮 math.CO

Matching and intersection problems for non-trivial r-partite r-uniform hypergraphs

Peter Frankl , Jiaxi Nie This is my paper

Pith reviewed 2026-05-10 15:59 UTC · model grok-4.3

classification 🧮 math.CO

keywords extremal combinatoricsmatching numbert-intersecting familiesr-partite hypergraphsErdős matching conjectureintersection theoremshypergraph extremal problems

0 comments

The pith

Non-trivial r-partite r-uniform hypergraphs have exact maximum sizes for bounded matchings and t-intersections when part size n is large.

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

The paper studies r-uniform hypergraphs that are r-partite with equal part sizes n but exclude the usual trivial constructions that maximize edges under matching or intersection limits. It establishes the precise maximum number of edges such a hypergraph can have while keeping its matching number at most s, and the maximum while ensuring every pair of edges shares at least t vertices. These exact values are given when n is sufficiently large. For the intersection version it solves the cases t=1 and t=r-2 completely for every n at least 2. A reader would care because the central problems of extremal combinatorics behave differently once the hypergraph is forced to be non-trivial and partite.

Core claim

For non-trivial r-partite r-uniform hypergraphs with equal part sizes n, the exact maximum number of edges with matching number at most s is determined when n is large enough, and the same holds for the maximum size of a family where every two edges intersect in at least t vertices. The cases t=1 and t=r-2 are settled for all n at least 2. These results partially confirm a conjecture of Lu and Ma.

What carries the argument

The non-trivial r-partite r-uniform hypergraph with equal part sizes n, which by definition excludes the constructions of all edges through a fixed small set of vertices.

If this is right

The maximum for matchings is strictly smaller than the bound from the Erdős matching conjecture in the unrestricted setting.
The t-intersection problem has closed-form answers in the non-trivial partite case for all n when t equals 1 or r-2.
Balanced constructions that respect the partite partition achieve the new maxima rather than the standard starring constructions.
The Lu-Ma conjecture holds at least for large n in this restricted family of hypergraphs.

Where Pith is reading between the lines

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

If the exact formulas extend to all n rather than only large n, the matching and intersection problems would be fully solved in the non-trivial partite setting.
The same partite restriction may tighten bounds in related extremal questions such as hypergraph Turán problems.
Checking moderate values of n by computer search could test whether the large-n threshold can be removed.

Load-bearing premise

The hypergraphs are non-trivial r-partite r-uniform with equal part sizes n, and n is large enough for the asymptotic statements to hold.

What would settle it

A non-trivial r-partite r-uniform hypergraph on r equal parts of large size n that contains more edges than the stated maximum while still having matching number at most s or all pairs intersecting in at least t vertices.

read the original abstract

A central theme in extremal combinatorics is the study of the maximum number of edges in an $r$-uniform hypergraph ($r$-graph) with matching number at most $s$ (the Erd\H{o}s Matching Conjecture) or with pairwise intersection at least $t$ (the $t$-intersection problem). The maximum sizes for these problems are typically achieved by trivial constructions: for the matching problem, the extremal construction consists of all edges intersecting a fixed set of $s$ vertices, while for the intersection problem, it consists of all edges containing a fixed set of $t$ vertices. In this paper, we investigate the \emph{non-trivial} $r$-partite $r$-graphs where each part is of size $n$. We determine the exact bounds for both the matching problem and the intersection problem when $n$ is sufficiently large. Furthermore, for the intersection problem, we resolve the cases $t=1$ and $t=r-2$ for all $n \ge 2$. Our results partially confirm a conjecture of Lu and Ma.

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

Frankl and Nie settle exact values for the matching and t-intersection problems in non-trivial balanced r-partite r-graphs for large n, plus two full cases for all n.

read the letter

The core advance is that they pin down the exact maximum edges for both the matching problem (matching number at most s) and the t-intersection problem inside the restricted class of non-trivial balanced complete r-partite r-uniform hypergraphs. For large n they get the precise numbers in both problems, and for the intersection side they close t=1 and t=r-2 completely for every n at least 2. This gives a partial confirmation of the Lu-Ma conjecture in a setting where the usual trivial constructions (all edges through a small fixed vertex set) are excluded by the non-triviality condition. That is genuinely new content relative to what was known before. The work is careful about the partite balanced setup and uses the large-n regime to apply stability-type arguments that are standard in this area but adapted here to avoid the trivial extremal examples. The constructions that achieve the bounds appear to be the natural partite analogues, and the fact that they handle the small-t cases uniformly is a nice bonus. The main limitation is that everything is confined to this non-trivial partite subclass, so it does not resolve the full conjecture or the unrestricted hypergraph versions. Within the stated scope the claims line up consistently with the abstract and the stress-test outline, with no visible internal gaps in the argument structure. Readers who already work on the Erdős matching conjecture or t-intersection theorems will find the most value here, especially those tracking progress on Lu-Ma. The paper is solid enough on its own terms to merit a serious referee; the results are specific and the scope is clearly delimited, so it should go through review rather than a desk rejection.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the maximum number of edges in non-trivial balanced r-partite r-uniform hypergraphs (equal part sizes n) under two constraints: matching number at most s, and t-intersecting families. It claims exact determinations of the extremal numbers for both problems when n is sufficiently large, and complete resolutions of the t-intersection problem for the cases t=1 and t=r-2 holding for every n≥2. These results are presented as a partial confirmation of the Lu-Ma conjecture, with the non-triviality condition excluding the standard trivial extremal constructions (stars or fixed t-sets).

Significance. If the claims hold, the work supplies precise extremal values in a restricted but natural class of hypergraphs that avoids the usual trivial examples, thereby advancing the matching and intersection problems beyond the classical Erdős and Erdős–Ko–Rado settings. The full resolution for t=1 and t=r-2 across all n, together with the large-n asymptotic statements, constitutes concrete progress on the Lu-Ma conjecture and demonstrates the applicability of stability or supersaturation techniques in the partite setting.

minor comments (3)

Abstract: the phrase 'non-trivial r-partite r-graphs' is introduced without a one-sentence definition or pointer to the formal definition in §2; a brief parenthetical clarification would help readers unfamiliar with the Lu-Ma setting.
The manuscript should state explicitly, perhaps in the introduction or after the main theorems, the dependence of the 'sufficiently large n' threshold on the parameters r, s and t; this would make the asymptotic claims easier to apply.
Notation: the symbols used for the extremal functions (e.g., ex or m(n,r,s)) should be introduced once in §1 and used consistently; occasional switches between descriptive phrases and symbols reduce readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, including the recognition of our exact bounds for the matching and t-intersection problems in non-trivial balanced r-partite r-graphs, the full resolutions for t=1 and t=r-2, and the partial confirmation of the Lu-Ma conjecture. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper determines exact extremal bounds for the matching number and t-intersection problems restricted to non-trivial balanced complete r-partite r-uniform hypergraphs, using stability and supersaturation arguments for the large-n regime and direct verification for t=1 and t=r-2. These steps rely on standard extremal combinatorics techniques and an external Lu-Ma conjecture rather than any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks with no reductions to the paper's own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on the standard definitions and axioms of extremal hypergraph theory with no free parameters, invented entities, or ad-hoc assumptions visible in the abstract.

axioms (1)

standard math Standard definitions of r-uniform hypergraphs, matchings, and t-intersections in the r-partite setting.
The paper invokes the usual combinatorial objects without additional justification.

pith-pipeline@v0.9.0 · 5491 in / 1124 out tokens · 54564 ms · 2026-05-10T15:59:22.230573+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

2, 125–136

Rudolf Ahlswede and Levon H Khachatrian,The complete intersection theorem for systems of finite sets, European journal of combinatorics18(1997), no. 2, 125–136

work page 1997
[2]

4, 419–431

M Deza and P Frankl,Erd¨ os–ko–rado theorem—22 years later, SIAM Journal on Algebraic Discrete Methods4(1983), no. 4, 419–431

work page 1983
[3]

1, 85–90

Paul Erd¨ os and Richard Rado,Intersection theorems for systems of sets, Journal of the London Math- ematical Society1(1960), no. 1, 85–90

work page 1960
[4]

Paul Erd˝ os,A problem on independentr-tuples, Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math.8(1965), 93–95

work page 1965
[5]

Paul Erd˝ os, Chao Ko, and Richard Rado,Intersection theorems for systems of finite sets, Quarterly Journal of Mathematics, Oxford Series (2)12(1961), 313–320

work page 1961
[6]

Fifth Hungarian Colloq., Keszthely, 1976), vol

Peter Frankl,The erdos-ko-rado theorem is true for n= ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. 1, 1978, pp. 365–375

work page 1976
[7]

Peter Frankl,The shifting technique in extremal set theory, Surveys in combinatorics 1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 81–

work page 1987
[8]

Peter Frankl,Disjoint edges in separated hypergraphs, Mosc. J. Comb. Number Theory2(2012), no. 4, 19–26. MR 3065278

work page 2012
[9]

4, 376–381

Peter Frankl and Zolt´ an F¨ uredi,The erd¨ os-ko-rado theorem for integer sequences, SIAM Journal on Algebraic Discrete Methods1(1980), no. 4, 376–381

work page 1980
[10]

1, 55–64

Peter Frankl and Norihide Tokushige,The erdos-ko-rado theorem for integer sequences, Combinatorica 19(1999), no. 1, 55–64

work page 1999
[11]

A. J. W. Hilton and E. C. Milner,Some intersection theorems for systems of finite sets, Quarterly Journal of Mathematics, Oxford Series (2)18(1967), 369–384

work page 1967
[12]

D´ enes K˝ onig,Gr´ afok ´ es m´ atrixok, Matematikai ´ es Fizikai Lapok38(1931), 116–119 (Hungarian)

work page 1931
[13]

Hongliang Lu and Xinxin Ma,Matching stability for 3-partite 3-uniform hypergraphs, arXiv preprint arXiv:2410.15673 (2024)

work page arXiv 2024
[14]

J Meyer,Quelques problemes concernant les cliques des hypergraphes h-complets et q-parti h-complets, Hypergraph Seminar, Springer, 1974, pp. 127–139. 15

work page 1974