pith. sign in

arxiv: 2606.24878 · v1 · pith:B56BPLM3new · submitted 2026-06-23 · 🧮 math.CO

An Improved Lower Bound for the ErdH{o}s-Lov\'asz Cover Number Problem

Varun Sivashankar This is my paper

Pith reviewed 2026-06-25 22:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords intersecting hypergraphcover numberlower boundedge coloringErdős-Lovász problemuniform hypergraphKahn's theorem
0
0 comments X

The pith

An r-uniform intersecting hypergraph with cover number r has at least (61/20 - o(1))r edges.

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

The paper improves the known lower bound on g(r), the fewest edges possible in an r-uniform hypergraph that intersects in every pair of edges yet needs r vertices to cover them all. Erdős and Lovász had established g(r) ≥ 8r/3 - 3 roughly fifty years ago; the new argument first reaches 3r - 4 by direct counting and then lifts the coefficient to 61/20 using an auxiliary construction and an edge-coloring theorem. A reader cares because the result narrows the gap between the best explicit constructions and the proven minimum size for these hypergraphs, tightening constraints on how intersection and covering properties interact in uniform set systems.

Core claim

The paper proves that g(r) ≥ (61/20 − o(1))r. It first supplies an elementary counting argument establishing the weaker bound g(r) ≥ 3r − 4, then constructs auxiliary hypergraphs from any purported minimal example and invokes Kahn's small-codegree hypergraph edge-colouring theorem on those auxiliaries to obtain the improved asymptotic coefficient.

What carries the argument

Auxiliary hypergraphs derived from the original intersecting family, to which Kahn's small-codegree edge-colouring theorem is applied after an elementary 3r-4 counting step.

If this is right

  • The new coefficient 61/20 exceeds the classical 8/3 for all sufficiently large r.
  • The o(1) error term tends to zero with growing r.
  • Any family achieving the bound must force the auxiliary hypergraphs to meet the hypotheses of the coloring theorem.
  • The elementary 3r-4 bound stands alone as an unconditional improvement valid for every r.

Where Pith is reading between the lines

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

  • Tighter codegree control or stronger coloring results could push the constant above 61/20.
  • The same auxiliary-construction technique might extend to related parameters such as the minimum size of intersecting hypergraphs with bounded matching number.
  • Exact determination of the limit superior of g(r)/r would now require either matching constructions or further improvements to the lower bound.

Load-bearing premise

The auxiliary hypergraphs constructed from a minimal example satisfy the small-codegree condition required by Kahn's theorem.

What would settle it

An explicit r-uniform intersecting hypergraph with cover number r and fewer than (61/20)r edges for infinitely many r would disprove the claimed lower bound.

read the original abstract

Let $g(r)$ be the minimum number of edges in an $r$-uniform intersecting hypergraph with cover number $r$. Erd\H{o}s and Lov\'asz proved the lower bound $g(r)\ge 8r/3-3$. We first give a completely elementary proof that $g(r)\ge 3r-4$. We then build on the same approach and apply Kahn's small-codegree hypergraph edge-colouring theorem to improve this to $g(r)\ge (61/20-o(1))r$. To the best of our knowledge, this is the first improvement over the Erd\H{o}s-Lov\'asz lower bound in about fifty years.

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.

Referee Report

0 major / 0 minor

Summary. The manuscript claims to improve the lower bound on the Erdős-Lovász function g(r), the minimum number of edges in an r-uniform intersecting hypergraph with cover number r. It first gives a self-contained elementary argument establishing g(r) ≥ 3r − 4 (improving the classical Erdős-Lovász bound of 8r/3 − 3), then constructs auxiliary hypergraphs to which Kahn’s small-codegree edge-colouring theorem is applied, yielding the stronger asymptotic lower bound g(r) ≥ (61/20 − o(1))r.

Significance. If correct, the result is significant: it supplies the first improvement to the lower bound on g(r) in roughly fifty years. The elementary 3r − 4 bound is accessible and may be of independent interest, while the asymptotic improvement rests on a standard application of Kahn’s theorem whose key step—the verification that the auxiliary hypergraphs satisfy the o(Δ) codegree hypothesis—is carried out explicitly in the construction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, including the recognition that the elementary bound and the asymptotic improvement via Kahn's theorem represent the first progress on g(r) in fifty years. We appreciate the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation consists of an elementary counting argument establishing g(r) ≥ 3r-4, followed by construction of auxiliary hypergraphs whose codegrees are o(Δ) and an application of the external Kahn small-codegree edge-colouring theorem. No step reduces by definition or by self-citation to the target bound; the 61/20 factor arises from combining the elementary lower bound with the colouring guarantee under the stated o(1) regime. The cited theorem is independent (different author, externally established) and the argument contains no fitted parameters or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the validity of Kahn's small-codegree edge-colouring theorem and on the elementary counting argument for the weaker bound; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Kahn's small-codegree hypergraph edge-colouring theorem applies to the hypergraphs arising in the construction
    Invoked to obtain the (61/20 - o(1))r improvement after the elementary 3r-4 step

pith-pipeline@v0.9.1-grok · 5642 in / 1192 out tokens · 33847 ms · 2026-06-25T22:31:44.441673+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 5 canonical work pages · 2 internal anchors

  1. [1]

    N. Alon, M. Buci´ c, M. Christoph, and M. Krivelevich,The power of many colours, Forum Math. Sigma 12 (2024), Paper No. e118, 23 pp

    2024

  2. [2]

    Bar´ at,Intersecting and2-intersecting hypergraphs with maximal covering number: the Erd˝ os–Lov´ asz theme revisited, J

    J. Bar´ at,Intersecting and2-intersecting hypergraphs with maximal covering number: the Erd˝ os–Lov´ asz theme revisited, J. Combin. Des. 29 (2021), no. 3, 193–209

    2021

  3. [3]

    Buci´ c, V

    M. Buci´ c, V. Jain, and V. Sivashankar,Intersecting hypergraphs with large cover number, arXiv:2503.14918, 2025

    work page arXiv 2025

  4. [4]

    T. F. Bloom,Erd˝ os Problem #21,https://www.erdosproblems.com/21, accessed June 18, 2026

    2026

  5. [5]

    S. J. Dow, D. A. Drake, Z. F¨ uredi, and J. A. Larson,A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size, Congr. Numer. 48 (1985), 47–48

    1985

  6. [6]

    Erd˝ os and L

    P. Erd˝ os and L. Lov´ asz,Problems and results on3-chromatic hypergraphs and some related questions, inInfinite and Finite Sets, Colloq. Math. Soc. J´ anos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627

    1975

  7. [7]

    Erd˝ os,On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no

    P. Erd˝ os,On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42

    1981

  8. [8]

    Frankl and J

    P. Frankl and J. Wang,New bounds on families without large sunflowers, Electron. J. Combin. 32 (2025), no. 2, Paper No. P2.43, doi:10.37236/13277

    work page doi:10.37236/13277 2025

  9. [9]

    Frankl and N

    P. Frankl and N. Tokushige,Invitation to intersection problems for finite sets, survey, 2016,https://www.renyi. hu/~pfrankl/F_T_Invitation.pdf

    2016

  10. [10]

    Kahn,On a problem of Erd˝ os and Lov´ asz: random lines in a projective plane, Combinatorica 12 (1992), no

    J. Kahn,On a problem of Erd˝ os and Lov´ asz: random lines in a projective plane, Combinatorica 12 (1992), no. 4, 417–423

    1992

  11. [11]

    Kahn,On a problem of Erd˝ os and Lov´ asz

    J. Kahn,On a problem of Erd˝ os and Lov´ asz. II.n(r) =O(r), J. Amer. Math. Soc. 7 (1994), no. 1, 125–143

    1994

  12. [12]

    Kahn,Asymptotically good list-colorings, J

    J. Kahn,Asymptotically good list-colorings, J. Combin. Theory Ser. A 73 (1996), no. 1, 1–59

    1996

  13. [13]

    D. Y. Kang, T. Kelly, D. K¨ uhn, A. Methuku, and D. Osthus,Solution to a problem of Erd˝ os on the chromatic index of hypergraphs with bounded codegree, Proc. Lond. Math. Soc. 129 (2024), no. 6, e70011, arXiv:2110.06181

    work page arXiv 2024

  14. [14]

    Meyer, inHypergraph Seminar, Lecture Notes in Math., Vol

    J.-C. Meyer, inHypergraph Seminar, Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, pp. 285–286

    1974

  15. [15]

    Pippenger and J

    N. Pippenger and J. H. Spencer,Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A 51 (1989), no. 1, 24–42

    1989

  16. [16]

    A note on uniform intersecting families with maximum transversal size

    A. Tripathi,A note on uniform intersecting families with maximum transversal size, arXiv:1409.4610, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  17. [17]

    Vertex degree sums for perfect matchings in 3-uniform hypergraphs

    Y. Zhang, Y. Zhao, and M. Lu,Vertex degree sums for perfect matchings in3-uniform hypergraphs, Electron. J. Combin. 25 (2018), no. 3, Paper No. P3.45, arXiv:1710.04752, doi:10.37236/7658. Department of Mathematics, Princeton University, Princeton, New Jersey, USA Email address:varunsiva@princeton.edu

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.37236/7658 2018