REVIEW 4 major objections 4 minor 2 cited by
The Hajnal--Rothschild problem
T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read For n sufficiently large relative to k, t, and s, the largest k-uniform family with ν(F,t)≤s is exactly a union of s t-intersecting cliques, with size h(n,k,t,s).
desk verdict A serious, likely-true structural result for the Hajnal–Rothschild problem, but the written proof has a load-bearing gap in Lemma 24/25 that should be fixed before the main theorem is accepted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is spread approximation. A family is r-spread when, for every set X, the subfamily of members containing X has size at most $r^{{-|X|}}$ times the whole family; the spread lemma says that a sufficiently spread family is found inside random subsets with high probability. The paper's new twist is an iterative scheme: Theorem 20 locates a dense set X inside a large subfamily, Theorem 23 peels off a spread piece on top of X, and Lemma 24 relaxes the condition ν(F,t)≤s to ν(S,t')≤s for a smaller t' while keeping the peeled pieces spread. Alternating these steps shrinks the uniformity of the approximating family S from k down to t+O((t/s)^{1/5}+log(st)), at which point Theorems 27 and 28 force S to be a union of s t-intersecting cliques, and a final spread argument shows the leftover remainder is empty.
What would settle it
Check the equality case by exhaustive search for small parameters that satisfy the theorem's inequalities, e.g. k=4, t=2, s=2 and n just above 2k+C(k−t)($t^{{4/5}}$$s^{{1/5}}$$log^{2}$ n + s $log_2^{4}$ n) for a chosen large absolute C: if any extremal family contains a member that does not contain some (t+x_i)-subset of the corresponding clique's support, the claimed structural uniqueness fails, and if |F|>h(n,k,t,s) the size statement fails.
Extended reading notes
Core claim
The central claim is Theorem 7: there is an absolute constant C such that whenever n>2k+C(k−t)$t^{{4/5}}$$s^{{1/5}}$$log^{2}$ n and n>2k+C(k−t)s $log_2^{4}$ n, any family F⊂binom([n],k) with ν(F,t)≤s satisfies |F|≤h(n,k,t,s), and equality forces F=A[K] for a family K that is a union of s t-intersecting cliques binom(Y_i,t+x_i) with |Y_i|=t+2x_i, as in Construction 4. Here h(n,k,t,s) is the maximum size of A[K] over all choices of nonnegative x_i≤k−t with pairwise disjoint supports Y_i. Thus the extremal families coincide with the upper shadows of such clique unions, exactly the shape predicted by the Complete t-Intersection Theorem when generalized from one clique to s cliques. The theorem improves the original 1973 result, whose n0 was enormous, to polynomial thresholds, and it applies in a regime where the extremal family is not shifted.
Load-bearing premise
The proof depends on being able to keep the spread pieces of the family so evenly distributed that, after removing the members that nearly intersect the already-chosen pieces, a large r-spread subfamily survives; the lower bounds on n in Theorem 7 exist precisely to make this survival step work, and if those inequalities fail the iterative approximation never reaches the clique structure.
Editorial extensions
If this is right
- The 1973 problem is reduced in this range to choosing s clique sizes x_i; the extremal family is always some A[K].
- For s=1, the theorem recovers the Complete t-Intersection Theorem structure in the covered large-n range, with the unique extremal family being a single t-intersecting clique D_i.
- The earlier 1973 bound required n0 roughly k^{t^2}s^t; the new thresholds are polynomial in s^{1/5}t^{4/5} and logarithmic factors, so the theorem is meaningful for fixed t,s as k grows.
- Because the extremal example is non-shifted, any attempt to prove the full problem by shifting alone must fail in this range; the spread-approximation route is essential.
- The empty-remainder conclusion means the approximation is exact for extremal families, not merely within a small additive error of the maximum.
Reading between the lines
- Editorial inference: the same iterative spread-approximation loop — find a dense piece, peel it, relax the matching parameter — is likely transferable to neighbouring forbidden-intersection problems where the ambient family is not the full binomial family.
- Editorial inference: the paper leaves open the exact transition value of n where the optimal clique size changes; its own remarks suggest that near the transition only two consecutive clique sizes appear, a statement that could be checked computationally for small k,t,s.
- Editorial inference: the proof's dependence on large n is real — Proposition 11 shows that for k=3,t=2,n=6 the extremal families are not clique unions — so extending the structural conclusion down to n close to 2k would require a genuinely different mechanism.
- Editorial inference: h(n,k,t,s) itself is not given in closed form; a practical consequence is that a separate finite optimization problem for the clique sizes remains, and solving it would give explicit extremal sizes in the covered range.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Hajnal–Rothschild problem: for a family F of k-subsets of [n], bound |F| when ν(F,t) ≤ s, i.e., when one cannot find s+1 members with pairwise intersections of size < t. The authors propose an extremal bound h(n,k,t,s) given by unions of s t-intersecting cliques on disjoint supports and characterize the extremal families as A[K] for such a clique union, for n exceeding two explicit lower bounds. The proof develops an iterative version of the spread approximation method: Theorem 26 provides a coarse approximation by a low-uniformity family S with ν(S,t)≤s; Theorems 27 and 28 give a fine-grained structural description of S; Section 7 combines these with a remainder-emptiness argument to deduce Theorem 7. The manuscript also contains a simpler bound in the spirit of Hajnal–Rothschild with polynomial n-dependence (Theorem 16/Corollary 17) and an analysis of the small cases k=3 and t=k-1.
Significance. If the proof is completed, this would be a substantial advance in extremal set theory: it gives not only an asymptotic size bound but a full structural description of extremal families in a range where the extremal construction is not shifted, and it introduces a potentially powerful iterative spread approximation technique. The paper is built on credible external tools (spread lemma, prior EMC bounds, the KLLM hypercontractivity result) and does not assume the main theorem. The claimed result is falsifiable and precise, and the structural conclusion is significantly stronger than earlier bounds for the Hajnal–Rothschild problem. However, the current manuscript contains a load-bearing gap in the use of Lemma 25 and several compressed or inconsistent statements, so the result cannot be considered established as written.
major comments (4)
- [Section 5.2, Lemma 25 and its use in Lemma 24] Lemma 25 is stated with the hypothesis μ_{p_i}(Q_i) ≥ 3(s+1)p_i, but in the application in Lemma 24 the probabilities are set to p_i = 1/(2(s+1)). The required lower bound is then 3(s+1)/(2(s+1)) = 3/2, which no probability can satisfy. The proof of Lemma 24 only establishes μ_{1/(2(s+1))}(Q_i) ≥ 3/4. Consequently, the invoked lemma cannot produce the disjoint rainbow sets Q_i, and the contradiction that proves ν(S,t') ≤ s is unsupported. This step is load-bearing: it is exactly the mechanism that converts r-spread decompositions of F_A(A) into the bound ν(S,t') ≤ s used in the iterative bootstrap of Theorem 26. The gap must be fixed, either by correcting Lemma 25 (for example, if the intended threshold is (3/2)(s+1)p_i or similar) or by providing a different argument for the rainbow matching step.
- [Section 1, Lemma 5] Lemma 5 is stated as a lemma but its proof is only a sketch. The claim that any family K of s cliques of prescribed sizes can be transformed by shifts into a family K' with pairwise disjoint supports without increasing the upper shadow is not obvious and is essential: it justifies the definition of h(n,k,t,s) as a maximum over disjoint supports and is used in Corollary 17 to lower-bound |A[U]|. A complete proof of the shift argument, or a reference to a known statement, is required.
- [Abstract and Theorem 7] The abstract states the two n-thresholds both with a factor log_2^4 n, while Theorem 7 states the first threshold with log^2 n (with unspecified base) and the second with log_2^4 n. Since these inequalities are the hypotheses of the main theorem, this inconsistency must be resolved. The proof in Section 7 at several points uses bounds such as n ≥ C s(k-t) log^4 n and n ≥ C t^{4/5} s^{1/5}(k-t) log^2 n; the exact logarithmic power in the first threshold of Theorem 7 needs to match what the proof actually yields.
- [Section 6.4, Theorem 28] Theorem 28 is presented as a compressed analogue of Theorem 27, but it covers a substantial parameter range (t ≤ C s log^3(st)) needed for the second case in the proof of Theorem 7. The proof says only 'We use a similar, albeit simpler, proof strategy' and then gives a short sketch. In particular, the argument that m = 0, the verification that the induction hypothesis applies to S^{(1)}, and the analogue of Lemma 32 for t-element sets are not written out in full. Since Theorem 28 is load-bearing for a whole branch of the main proof, this should be expanded to a complete proof or supplied as a supplementary file.
minor comments (4)
- [Section 5.2, Lemma 25 statement] The lemma statement begins 'Fix p_1,...,p_s' but the family is indexed as Q_1,...,Q_{s+1}. It should read p_1,...,p_{s+1}.
- [Section 5.3, Step B(i)] The sentence 'It is easy to that (13) is satisfied' is missing the verb 'see' or 'check'.
- [Section 6.3, Lemma 34] In Lemma 34(2), the final displayed chain of inequalities has an inconsistency: it starts with |U_1| ≥ h(n,k,s,t) - (3/2 + 1/(10s)) h(n,k,1,t) and later concludes |U_1| ≥ h(n,k,s,t) - (1/2 + 1/(10(s-1))) h(n,k,1,t), but the intermediate line uses h(n,k,s-1,t) - (1/2 + 1/(10s) + 1/(10s^3)) h(n,k,1,t). The notation is confusing and should be cleaned up.
- [Section 4, proof outline] The outline refers to the 'remainder R' and says it will be shown empty, but the statement of Theorem 7 reserves the equality case for F = A[K]. It would help to state explicitly how the empty-remainder conclusion implies the equality statement, since the argument in Section 7 is somewhat implicit.
Circularity Check
No circularity: the main theorem is derived from spread-approximation and structural theorems proved in the paper; internal references to Theorem 7 for s-1 are ordinary induction.
full rationale
The derivation chain is self-contained in the relevant sense. Theorem 7 is proved by combining Theorem 26 (iterative spread approximation, proved in Section 5) with Theorems 27/28 (fine-grained structure, proved in Section 6) and then showing the remainder is empty in Section 7. The structural theorem is proved by induction on s, and the paper explicitly flags the only self-reference: "We prove the statement by induction on s, in which we use both the statement of Theorem 27 for s−1 and also the statement of Theorem 7 for s−1... Thus, this creates no problem." This is legitimate induction, not circularity. The spread-approximation framework from the authors' prior work is cited as background, but the paper states and proves the specific spread lemmas it needs (Observations 9-10, Theorems 8, 20, 23, 24, 26); citations to [22], [20], [21] are not used to bypass the proof. The use of [12] in Lemma 34 is an external published bound, independent of the present argument. Also, h(n,k,t,s) is defined as the maximum over explicit Construction 4 families, not fitted to F, so the upper bound |F| <= h is not a definitional rearrangement. The Skeptic's Lemma 25 concern is a potential correctness gap (with p_i = 1/(2(s+1)), the required measure 3(s+1)p_i = 3/2 exceeds 1), but a failed hypothesis of an external lemma is not circularity: it does not make any asserted prediction equal to an input or any fit renamed as a conclusion. No circular step is exhibited, so the score is 0.
Assumptions & free parameters
free parameters (3)
- absolute constant C =
unspecified, chosen sufficiently large
- sigma =
100(t/s)^(1/2) in the main regime, 100 log_2(st) in the small-t regime
- exponents alpha and beta =
alpha=0.5, beta=0.5 for small t; alpha=4/5-3/(10y), beta=1/2 when t=s^y
assumptions (6)
- standard math Erdos-Ko-Rado theorem with exact threshold n0(k,t), due to Frankl and Wilson
- standard math Ahlswede-Khachatrian Complete t-Intersection Theorem
- standard math Spread lemma due to Alweiss, Lovett, Wu, Zhang, with sharpenings by Tao and Stoeckl
- standard math Keevash-Lifshitz-Long-Minzer rainbow matching lemma
- standard math Turan's theorem
- standard math Prior Erdos Matching Conjecture bounds by Frankl and Kupavskii
Cite this review
Pith. "Pith review of The Hajnal--Rothschild problem." pith.science (2026). https://pith.science/paper/XWW4N5QC
@misc{pith2026250206699,
author = {Pith},
title = {Pith review of: The Hajnal--Rothschild problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/XWW4N5QC}},
note = {Machine review of arXiv:2502.06699}
}
abstract
For a family $\mathcal F$ define $\nu(\mathcal F,t)$ as the largest $s$ for which there exist $A_1,\ldots, A_{s}\in \mathcal F$ such that for $i\ne j$ we have $|A_i\cap A_j|< t$. What is the largest family $\mathcal F\subset{[n]\choose k}$ with $\nu(\mathcal F,t)\le s$? This question goes back to a paper Hajnal and Rothschild from 1973. We show that, for some absolute $C$ and $n>2k+Ct^{4/5}s^{1/5}(k-t)\log_2^4n$, $n>2k+Cs(k-t)\log_2^4 n$ the largest family with $\nu(\mathcal F,t)\le s$ has the following structure: there are sets $X_1,\ldots, X_s$ of sizes $t+2x_1,\ldots, t+2x_s$, such that for any $A\in \mathcal F$ there is $i\in [s]$ such that $|A\cap X_i|\ge t+x_i$. That is, the extremal constructions are unions of the extremal constructions in the Complete $t$-Intersection Theorem. For the proof, we enhance the spread approximation technique of Zakharov and the second author. In particular, we introduce the idea of iterative spread approximation.
Forward citations
Cited by 2 Pith papers
-
A unified approach to cross-intersection problems with applications to Hilton--Milner type theorems and stability
A fingerprint/t-cover iteration determines extremal and stable cross t-intersecting k-uniform families for large n, including product EKR for spread systems and t-diversity bounds.
-
A complete $t$-intersection theorem for families of spanning trees
For n large and 2≤t≤n−2, every t-intersecting family of spanning trees of K_n has size at most c_{n,t} n^{n−2−t}, with equality exactly for the trivial family containing a balanced fixed forest.
Reference graph
Works this paper leans on
-
[1]
Ahlswede and L.H
R. Ahlswede and L.H. Khachatrian,The Complete Intersection Theorem for Systems of Finite Sets, European Journal of Combinatorics. 18 (1997), 125–136
1997
-
[2]
R. Alweiss, S. Lovett, K. Wu, and J. Zhang,Improved bounds for the sunflower lemma, arXiv:1908.08483 (2019)
arXiv 2019
-
[3]
B. Bollob´ as, D.E. Daykin and P. Erd˝ os,Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. 27 (1976), N2, 25–32
work page 1976
- [4]
-
[5]
Erd˝ os,A problem on independent r-tuples, Ann
P. Erd˝ os,A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8 (1965) 93–95
1965
-
[6]
P. Erd˝ os and T. Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356
work page 1959
-
[7]
Erd˝ os, C
P. Erd˝ os, C. Ko, and R. Rado,Intersection theorems for systems of finite sets, The Quart. J. Math. 12 (1961), N1, 313–320
1961
-
[8]
Frankl, The Erd˝ os-Ko-Rado theorem is true for n=ckt, Combinatorics (Proc
P. Frankl, The Erd˝ os-Ko-Rado theorem is true for n=ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, 365–375, Colloq. Math. Soc. J´ anos Bolyai, 18, North-Holland
work page 1976
Show all 25 references
-
[9]
Frankl,Improved bounds for Erd˝ os’ Matching Conjecture, J
P. Frankl,Improved bounds for Erd˝ os’ Matching Conjecture, J. Comb. Theory Ser. A 120 (2013), 1068–1072
2013
-
[10]
Frankl,On the maximum number of edges in a hypergraph with a given matching number, Disc
P. Frankl,On the maximum number of edges in a hypergraph with a given matching number, Disc. Appl. Math. 216 (2017), N3, 562–581
2017
-
[11]
Frankl,Proof of the Erd˝ os matching conjecture in a new range, Isr
P. Frankl,Proof of the Erd˝ os matching conjecture in a new range, Isr. J. Math. 222 (2017), N1, 421–430
2017
-
[12]
P.Frankl, An improved universal bound for𝑡-intersecting families, EuropeanJ.Com- binatorics 87 (2020), 103134
2020
-
[13]
Frankl, A
P. Frankl, A. Kupavskii,The Erd˝ os Matching Conjecture and Concentration Inequal- ities, Journal of Comb. Theory Ser B. 157 (2022), 366–400
2022
-
[14]
Frankl, N
P. Frankl, N. Tokushige,Extremal problems for finite sets, American Mathematical Society, Providence, Rhode Island, 2018
2018
-
[15]
Gerbner, B
D. Gerbner, B. Patk´ os,Extremal finite set theory, CRC Press, New York, 2019
2019
-
[16]
Hajnal, B
A. Hajnal, B. Rothschild,A Generalization of the Erd˝ os–Ko–Rado Theorem on Fi- nite Set Systems, J. Combin. Theory Ser. A 15 (1973), 359–362
1973
-
[17]
Huang, P.-S
H. Huang, P.-S. Loh and B. Sudakov,The Size of a Hypergraph and its Matching Number, Comb. Probab. Comput. 21 (2012), N3, 442–450
2012
-
[18]
Keevash, N
P. Keevash, N. Lifshitz, E. Long, and D. Minzer,Hypercontractivity for global func- tions and sharp thresholds, arXiv:1906.05568 (2019)
2019 arXiv
-
[19]
346 (2023), N4
D.Kolupaev, A.Kupavskii, Erd˝ os Matching Conjecture for almost perfect matchings, Discrete Math. 346 (2023), N4
2023
-
[20]
Kupavskii,Erd˝ os–Ko–Rado type results for partitions via spread approximations (2023), arXiv.2309.00097
A. Kupavskii,Erd˝ os–Ko–Rado type results for partitions via spread approximations (2023), arXiv.2309.00097
2023
-
[21]
Kupavskii, Intersection theorems for uniform subfamilies of hereditary families (2023), arXiv.2311.02246
A. Kupavskii, Intersection theorems for uniform subfamilies of hereditary families (2023), arXiv.2311.02246
2023 arXiv
-
[22]
Kupavskii and D
A. Kupavskii and D. Zakharov,Spread approximations for forbidden intersections problems, to appear in Advances in Mathematics, available at arxiv:2203.13379
-
[23]
Stoeckl,Lecture notes on recent improvements for the sunflower lemmahttps: //mstoeckl.com/notes/research/sunflower_notes.html
M. Stoeckl,Lecture notes on recent improvements for the sunflower lemmahttps: //mstoeckl.com/notes/research/sunflower_notes.html
-
[24]
Tao,The sunflower lemma via shannon entropy, https://terrytao.wordpress
T. Tao,The sunflower lemma via shannon entropy, https://terrytao.wordpress. com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/
2020
-
[25]
Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984), 247–257
R.M. Wilson, The exact bound in the Erd˝ os–Ko–Rado theorem, Combinatorica 4 (1984), 247–257. R´enyi Institute, Budapest, Hungary; Email:peter.frankl@gmail.com Moscow Institute of Physics and Technology, Russia, St. Petersburg State University; Email:kupavskii@ya.ru
1984
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.