Pith. sign in

REVIEW 2 major objections 4 minor 8 references

Combining the theorems of Tur\'an and de Bruijn-Erd\H os

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every fixed s and all large n, the minimum size of an s-cover with bounded line size is exactly (n-1)/(s-1)+s-1 in the divisible case.

desk verdict A real generalization of de Bruijn-Erdős with a solid proof skeleton, but the explicit constant choices in Case 2.2 contradict the stated hierarchy and break the key inequality. read the letter →

arxiv 2411.14634 v1 pith:EBQQXUDS submitted 2024-11-21 math.CO

Sayok Chakravarty , Dhruv Mubayi This is my paper · ORCID
classification math.CO MSC 05D0505C3505B25
keywords s-coverslinearspaceshypergraphsdeBruijn–ErdőstheoremTurán'sextremalcombinatoricsprojectiveplanesnearpencils
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper determines, for every fixed $s\ge 2$ and all sufficiently large $n$, the minimum number of lines in an $s$-cover: a family of subsets of an $n$-point set in which two lines share at most one point and every $s$-set of points contains a pair lying on one line. Under the natural cap that each line has size at most $(n-1)/(s-1)$, the minimum is shown to be $(n-1)/(s-1)+s-1$, with equality attainable by an explicit grid construction when $s-1$ divides $n-1$ and asymptotic equality otherwise. This generalizes the classical de Bruijn–Erdős theorem, which is the case $s=2$, and combines a Turán-type pair-counting argument with induction on $s$.

What carries the argument

The argument is carried by three interacting components. First, induction on $s$, with the de Bruijn–Erdős theorem as the base case and the strengthened Theorem 2 as the inductive hypothesis. Second, Turán's theorem: the pairs of points not contained in any line form a $K_s$-free graph, so the number of such pairs is bounded above, giving the global pair-counting inequality in Lemma 1.4. Third, a sequence of counting lemmas that convert minimum-degree bounds, the number of points outside the neighborhood of a vertex, and elementary symmetric polynomial estimates into inequalities that rule out every configuration except the extremal one. The extremal construction is a $t\times(s-1)$ grid with one added point, whose lines are the grid columns together with the rows each completed by the added point.

What would settle it

Construct, for some fixed $s\ge 3$ and arbitrarily large $n$ with $s-1$ dividing $n-1$, an $s$-cover whose lines all have size at most $(n-1)/(s-1)$ but whose line count is less than $(n-1)/(s-1)+s-1$; such a family would refute Theorem 1. A direct check of whether the five error constants can be reassigned to satisfy the stated hierarchy would test only the written proof, not the theorem itself.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for fixed $s\ge 2$ and $n$ large enough, if $\mathcal{L}$ is an $s$-cover on $n$ points with every line of size at most $(n-1)/(s-1)$, then $|\mathcal{L}|\ge (n-1)/(s-1)+s-1$. When $s-1$ divides $n-1$ the bound is tight; when it does not, the bound is asymptotically tight as $n\to\infty$. To support the induction, the paper also proves a stronger statement, Theorem 2: for $s\ge 3$, lowering the line-size cap to $(n-1)/(s-1)-1$ forces the strict inequality $|\mathcal{L}|>(n-1)/(s-1)+s-1$. The proof is carried out for linear hypergraphs, and the planar formulation for point sets and lines follows as Corollary 1.

Load-bearing premise

The proof depends on choosing five tiny error constants in a strict order, and the explicit values assigned in the subcase where the largest line has size close to the square root of n contradict that order, so the contradiction in that subcase does not currently go through as written.

Editorial extensions

If this is right

  • For $s-1$ dividing $n-1$ and $n$ large, the grid construction achieves the claimed bound, so the minimum number of lines is exactly $(n-1)/(s-1)+s-1$.
  • When $s-1$ does not divide $n-1$, the same formula is asymptotically sharp: the minimum is $(1+o(1))n/(s-1)$.
  • For a planar configuration of points and lines, any set of lines that puts a collinear pair in every $s$-set and uses no line with more than $(n-1)/(s-1)$ of the points must contain at least $(n-1)/(s-1)+s-1$ lines for large $n$.
  • The strengthened inductive form means that lowering the line-size cap by one forces strictly more than the extremal number of lines, which is exactly what keeps the induction from losing the strict inequality at intermediate steps.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The asymptotic construction uses a prime in a short interval near $n^{1/2}$; any improvement in such prime-gap estimates would only shrink the $o(n)$ error term, while the leading coefficient $n/(s-1)$ would remain the same.
  • The extremal value coincides with the Turán density threshold for $K_s$-free graphs, suggesting that the covering problem is limited by the same pairwise-density ceiling; stability versions of Turán's theorem might yield a simpler proof or help in the small-$n$ regime.
  • A direct next question is to pin down the exact minimum for all small $n$, which the paper leaves open; the grid, near-pencil, and projective-plane examples indicate several candidate extremal families there.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proves a generalization of the de Bruijn-Erdős theorem. For a fixed s ≥ 2, an s-cover is a family of subsets (lines) of an n-point set such that any two lines meet in at most one point and every s-set of points contains a pair lying in some line. The main result (Theorem 1) states that if every line has size at most (n−1)/(s−1), then for sufficiently large n the number of lines is at least (n−1)/(s−1)+s−1, with equality when (s−1) divides (n−1) and asymptotic tightness otherwise. The proof proceeds by induction on s, using Turán's theorem to count covered pairs, the de Bruijn-Erdős theorem as the base case, and a case analysis according to the size a1 of the largest line. The paper also gives a construction showing tightness, relying on a prime gap result of Baker, Harman, and Pintz for the non-divisible case.

Significance. If the theorem is correct, it is a natural and attractive combination of two classical extremal results, with a clean statement and a construction that is tight up to the stated divisibility condition. The paper is self-contained, clearly written, and includes an honest discussion of the large-n hypothesis and the open small-n case. The proof strategy is plausible, and the internal lemmas (degree bounds, pair counting, induction on s) are mostly standard. However, the proof as written contains a load-bearing inconsistency in the choice of constants in Case 2.2, so the lower bound is not fully established in the current form.

major comments (2)
  1. [§2 (constant hierarchy and Case 2.2, around (13))] The hierarchy displayed before Lemma 1 requires δ2 ≪ δ1 ≪ δ ≪ δ4 ≪ δ3 ≪ 1/s^2, but the explicit choices δ3 = δ1/4 and δ4 = δ1/2 violate this order: δ4 = 2δ3, so δ4 ≪ δ3 fails, and δ4 = δ1/2, so δ1 ≪ δ4 fails. The subsequent computation after (13) states that δ3δ4 = δ1/4 · δ1/2 = δ3/4 ≫ δ; this is arithmetically incorrect, since δ3δ4 = δ1^2/8, and because δ1 ≪ δ, this product is ≪ δ, not ≫ δ. The needed conclusion 1 − δ3δ4(s−1)/2 + δ2 < 1 therefore does not follow, and the contradiction excluding the range a1 < (1+δ1)√n is not established as written. This is a central gap in the lower-bound proof.
  2. [§2 (inequality (16) and surrounding display)] The proof of inequality (16) relies on the assertion 'as δ3 ≫ δ4 ≫ δ1', but with the stated assignments δ3 = δ1/4 and δ4 = δ1/2 we have δ4 = 2δ3, so δ3 ≫ δ4 is false. Moreover, the displayed chain leading to (16) is not algebraically justified: the step yielding the term −δ3/(3s) requires δ3 to dominate δ1 and δ4, which is precisely what the chosen constants fail to do. Since (16) is the key comparison showing that the upper bound for covered pairs in Q is smaller than the Turán lower bound, this part of the proof also needs to be redone with a consistent choice of parameters.
minor comments (4)
  1. [§2, end of Case 2.2] The sentence 'so it is not possible that (1−δ)√n ≤ a1 < (1+δ2)√n' should refer to the upper endpoint (1+δ1)√n, since that is the case under discussion; the use of δ2 here appears to be a typo.
  2. [§1, hierarchy before (1)] The constant C1 appears in the hierarchy and in inequality (1) but is not defined anywhere; please state its definition or explain that it is an absolute constant introduced implicitly (e.g., via the Baker–Harman–Pintz theorem).
  3. [§2, Lemma 1.2 proof] The line '|Q| > (s−2)/(s−1) n ≥ (s−2)/(s−1) n0(s) ≥ n0(s−1)' implicitly assumes n0(s) is chosen so that (s−2)/(s−1)n0(s) ≥ n0(s−1); this should be stated explicitly when n0(s) is introduced.
  4. [§2, Case 4] In the paragraph beginning 'Suppose all the (s−1)-sets in [n]\A1 are covered', the definition of L′ and the subsequent application of induction are clear, but the text 'a1 ≤ (|Q|−1)/(s−2) by the same inequality used in the proof of Lemma by 1.2' contains the awkward phrase 'Lemma by 1.2'; this should read 'Lemma 1.2'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a self-contained induction using de Bruijn–Erdős, Turán, and Baker–Harman–Pintz as external inputs; no fitted parameter or author self-citation is load-bearing.

full rationale

The claimed derivation is not circular. The lower bound is proved by induction on s with base case s=2 from the de Bruijn–Erdős theorem, an external classical result. Each induction step uses Turán's theorem to count covered pairs in P (Lemma 1.4 and the arguments around equations (3) and (13)) and applies the induction hypothesis to (s−1)-covers on Q or Q2; these are genuine external or inductive inputs, not restatements of the target bound. The constants δ, δ1, δ2, δ3, δ4 are small parameters chosen to satisfy inequalities; if the assignments δ3=δ1/4 and δ4=δ1/2 conflict with the stated hierarchy and with the asserted identity δ3δ4=δ3/4, that is an arithmetic or inequality error in the Case 2.2 parameter handling, not a circular reduction: the theorem's conclusion is not assumed among the hypotheses, and no fitted quantity is later renamed as a prediction. The tightness construction uses the classical near-pencil and projective-plane structures and the Baker–Harman–Pintz prime-gap theorem as external inputs. The only self-citation, [1] Alon–Mellinger–Mubayi–Verstraëte, appears in the introduction as background on a hypergraph formulation and is not used to justify any proof step. The paper explicitly states that n must be large and that small n remains open; this is a stated limitation and does not make the derivation circular. Overall score 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The theorem statement has no free parameters; the δ constants are internal proof tools and are not part of the result. The proof relies on standard external theorems: the de Bruijn-Erdős theorem (base case and several s=3 cases), Turán's theorem (bounding uncovered pairs), the existence of finite projective planes of prime order (asymptotic construction), and the Baker-Harman-Pintz prime gap theorem (asymptotic construction).

assumptions (4)
  • domain assumption de Bruijn-Erdős theorem
    Used as the base case s=2 and in several s=3 subcases (Section 2, base case and Case 5).
  • domain assumption Turán's theorem
    Used in Lemma 1.4 and Case 2 to bound the number of uncovered pairs in a K_s-free graph.
  • domain assumption Baker-Harman-Pintz prime gap theorem
    Used in the asymptotic tightness construction to guarantee a prime q in [√(n/(s−1)), √(n/(s−1)) + (n/(s−1))^{0.2625}].
  • standard math Existence of finite projective planes of prime order
    Used in the asymptotic tightness construction: a projective plane on q^2+q+1 points with lines of size q+1 exists when q is prime.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Combining the theorems of Tur\'an and de Bruijn-Erd\H os." pith.science (2026). https://pith.science/paper/EBQQXUDS

@misc{pith2026241114634,
  author       = {Pith},
  title        = {Pith review of: Combining the theorems of Tur\'an and de Bruijn-Erd\H os},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBQQXUDS}},
  note         = {Machine review of arXiv:2411.14634}
}
abstract

Fix an integer $s \ge 2$. Let $\mathcal{P}$ be a set of $n$ points and let $\mathcal{L}$ be a set of lines in a linear space such that no line in $\mathcal{L}$ contains more than $(n-1)/(s-1)$ points of $\mathcal{P}$. Suppose that for every $s$-set $S$ in $\mathcal{P}$, there is a pair of points in $S$ that lies in a line from $\mathcal{L}$. We prove that $|\mathcal{L}| \ge (n-1)/(s-1)+s-1$ for $n$ large, and this is sharp when $n-1$ is a multiple of $s-1$. This generalizes the de Bruijn-Erd\H os theorem which is the case $s=2$. Our result is proved in the more general setting of linear hypergraphs.

Figures

Figures reproduced from arXiv: 2411.14634 by the authors.

Figure 1
Figure 1. The construction of L when t = 5 and s = 4. Corollary 1. Fix an integer s ≥ 2. Let P be a set of n points and let L be a set of m lines in the plane such that no line in L contains more than (n − 1)/(s − 1) points of P. Suppose that for every s-set S of points from P, there is a pair of points in S lies in some line from L. Then m ≥ (n − 1)/(s − 1) + s − 1 for n large and if n − 1 is a multiple of s − 1, this is tig… view at source ↗
Figure 2
Figure 2. Setup for Lemma 1. We first prove a lemma giving various bounds on m depending on d, the ai ’s, and |Q|. We will assume below that Theorem 2 holds for all s ′ ≤ s − 1 by induction on s and that n is sufficiently large in terms of s to apply induction and any further inequalities that require this. More explicitly, we will show that if n ≥ n0(s) where n0(s) is large enough for the inequalities we use in the proof to … view at source ↗
Figure 3
Figure 3. Q2 and B′ x1 Let Q2 = [n] \ (A1 ∪ {x1}) (see [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Iterative Procedure Let us now suppose that r = 0. Assume j < s − 2. If |Ai ∩ Qj+1| ≤ ℓ − 1 for all i, then |Ai ∩ Qj+1| ≤ ⌊(|Qj+1 − 1)/(s − j − 1)⌋ due to |Qj+1| − 1 s − j − 1 = ℓ − 1 s − j − 1 . Since |Qj+1| = (s − j − 1)ℓ = (s − j − 1) · n − 1 s − 1 ≥ n0(s − j), we m…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 7 canonical work pages

  1. [1]

    Mellinger, Dhruv Mubayi, and Jacques Verstra ¨ ete

    Noga Alon, Keith E. Mellinger, Dhruv Mubayi, and Jacques Verstra ¨ ete. The de Bruijn- Erd˝ os theorem for hypergraphs. Des. Codes Cryptogr. , 65(3):233–245, 2012

    work page 2012

  2. [2]

    R. C. Baker, G. Harman, and J. Pintz. The difference between co nsecutive primes. II. Proc. London Math. Soc. (3) , 83(3):532–562, 2001

    2001

  3. [3]

    R. C. Bose. A note on Fisher’s inequality for balanced incomplete blo ck designs. Ann. Math. Statistics , 20:619–620, 1949

    work page 1949

  4. [4]

    A de Bruijn-Erd˝ ostheorem and metric spaces

    Ehsan Chiniforooshan and Vaˇ sek Chv´ atal. A de Bruijn-Erd˝ ostheorem and metric spaces. Discrete Math. Theor. Comput. Sci. , 13(1):67–74, 2011

    work page 2011

  5. [5]

    N. G. de Bruijn and P. Erd¨ os. On a combinatorial problem. Nederl. Akad. Wetensch., Proc., 51:1277–1279 = Indagationes Math. 10, 421–423, 1948

    work page 1948

  6. [6]

    Doleˇ zal, T

    M. Doleˇ zal, T. Mitsis, and Ch. Pelekis. The de Bruijn–Erd˝ os theo rem from a Hausdorff measure point of view. Acta Math. Hungar. , 159(2):400–413, 2019

    work page 2019

  7. [7]

    R. A. Fisher. An examination of the different possible solutions of a problem in incomplete blocks. Ann. Eugenics , 10:52–75, 1940

    work page 1940

  8. [8]

    Ray-Chaudhuri and Richard M

    Dijen K. Ray-Chaudhuri and Richard M. Wilson. On t-designs. Osaka Math. J. , 12(3):737–744, 1975. 21

    work page 1975

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.