An Improved Lower Bound for the Erdős–Lovász Cover Number Problem

Varun Sivashankar · 2026

Read An Improved Lower Bound for the Erdős–Lovász Cover Number Problem by Varun Sivashankar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24878.txt.

Introduction

Varun Sivashankar improves a lower bound in a combinatorics problem Erdős himself counted among his favourites. The setting is intersecting hypergraphs, where every two edges share a vertex. For a given uniformity and the largest possible cover number, one asks the fewest edges such a hypergraph can have. Erdős and Lovász bounded that minimum below by roughly eight thirds of the parameter, minus a constant. That bound stood for about fifty years. Sivashankar's attack stays elementary at first.

A first argument gives a clean bound of three times the parameter minus four. Building on the same approach, he then applies Kahn's edge colouring theorem for hypergraphs of small codegree. The result lifts the lower bound to about sixty one twentieths of the parameter, for large cases. To his knowledge this is the first improvement on the Erdős Lovász bound in half a century.

Catalog record

CREATORVarun Sivashankar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24878

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Improved Lower Bound for the Erdős–Lovász Cover Number Problem Varun Sivashankar Abstract . Let g ⁡ ( r ) g(r) be the minimum number of edges in an r r -uniform intersecting hypergraph with cover number r r . Erdős and Lovász proved the lower bound g ⁡ ( r ) ≥ 8 ​ r / 3 − 3 g(r)\geq 8r/3-3 . We first give a completely elementary proof that g ⁡ ( r ) ≥ 3 ​ r − 4 g(r)\geq 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 ) ≥ ( 61 / 20 − o ⁡ ( 1 ) ) ​ r g(r)\geq(61/20-o(1))r . To the best of our knowledge, this is the first improvement over the Erdős–Lovász lower bound in about fifty years. 1. Introduction A hypergraph is intersecting if every two of its edges meet. A cover , or transversal , of a hypergraph \mathcal{H} is a set of vertices meeting every edge; its minimum size is denoted \tau(\mathcal{H}) . Following Erdős and Lovász [ 6 ] , let g(r) be the minimum number of edges in an r -uniform intersecting hypergraph \mathcal{H} with \tau(\mathcal{H})=r . The condition \tau(\mathcal{H})=r is the largest possible cover number for an intersecting r -uniform hypergraph, since any edge of \mathcal{H} is itself a cover. Erdős and Lovász proved g(r)\geq\frac{8r}{3}-3. Erdős later called this one of his three favorite combinatorial problems and offered $500 for a proof or disproof of g(r)\leq Cr . He also observed that he and Lovász could not even decide whether g(r)<3r [ 7 ] . The problem is listed as Erdős Problem #21 in Bloom’s collection [ 4 ] . Kahn answered the linearity question affirmatively, first up to a logarithmic factor [ 10 ] , and then in full [ 11 ] . For small values, Tripathi proved g(4)=9 and gave a short proof that g(3)=6 [ 16 ] , while Barát proved g(5)=13 and studied related 2 -intersecting examples [ 2 ] . On the lower-bound side, the constant 8/3 remained unchanged for decades; Barát observed in 2020 that this lower bound had seen no improvement for 45 years [ 2 ] . Frankl and Tokushige later described determining the exact value of this function as “hopelessly difficult” [ 9 ] . A recent line of work studies a vertex-constrained version of the same problem. Motivated by Bollobás’ “power of many colours” problem, Alon, Bucić, Christoph, and Krivelevich introduced the variant in which the hypergraph is required to have a prescribed number of vertices [ 1 ] ; Bucić, Jain, and Sivashankar studied this vertex-constrained problem across the full range [ 3 ] . This paper returns to the original, unconstrained Erdős–Lovász problem and gives the following explicit lower bound. Theorem 1 . The following bounds hold. (i) For every positive integer r , g(r)\geq 3r-4. (ii) For every \varepsilon>0 , there is r_{0} such that, for every r\geq r_{0} , g(r)\geq\left(\frac{61}{20}-\varepsilon\right)r. Since 61/20>3 , part (ii) implies g(r)>3r for all sufficiently large r , crossing the threshold that Erdős explicitly noted was unresolved. A closely related problem of Meyer [ 14 ] asks for the minimum number M(r) of edges in a maximal r -uniform intersecting hypergraph, where maximal means that no further r -edge can be added while preserving the intersecting property. Every maximal r -uniform intersecting hypergraph has cover number exactly r : otherwise a cover of size at most r-1 could be extended, using fresh vertices if necessary, to a new r -edge meeting every existing edge, contradicting maximality. Hence M(r)\geq g(r) . Dow, Drake, Füredi, and Larson proved the lower bound M(r)\geq 3r for r\geq 4 [ 5 ] . Consequently, Theorem 1 (ii) also gives the asymptotic improvement M(r)\geq(61/20-o(1))r . The proof of part (i) peels off all vertices of degree at least 4 , leaving an r -uniform intersecting hypergraph \mathcal{J} of maximum degree at most 3 , and then proves a sharp cover bound for \mathcal{J} . This bound is obtained by taking a maximum matching in the auxiliary triple system formed by the degree-three vertices of \mathcal{J} and counting around the unmatched edges. The matching argument follows a standard maximum-matching augmentation philosophy. After fixing a maximum matching, one studies the link graphs on the uncovered vertices associated with a matched edge; maximality forces the relevant link graphs to be pairwise cross-intersecting, since two disjoint link edges of different types would replace one matched edge by two. Closely related link-graph arguments appear in work of Zhang, Zhao, and Lu on degree-sum conditions for perfect matchings in 3 -uniform hypergraphs [ 17 ] , especially Lemma 7, where three pairwise cross-intersecting graphs control local degree sums. A similar structural case analysis appears in Frankl and Wang’s work on sunflower-free families [ 8 ] , Lemma 5.1, where two disjoint edges in one graph force the other two graphs into a small star-like support. Part (ii) uses the same high-level approach, but peels at degree 5 rather than degree 4 and then applies Kahn’s small-codegree edge-colouring theorem to find a large matching in the auxiliary 4 -uniform hypergraph formed by the degree-four vertices. 2. The Peeling Reduction We may restrict attention to simple hypergraphs, since deleting repeated edge-copies does not change uniformity, the intersecting property, or the cover number, and can only decrease the number of edges. Let \mathcal{H} be an r -uniform intersecting hypergraph with \tau(\mathcal{H})=r , and put m=|E(\mathcal{H})| . Starting from \mathcal{H} , repeatedly choose a vertex of current degree at least 4 , put it into a set S , and delete all current edges containing it. Stop when the remaining hypergraph has maximum degree at most 3 . Denote the remaining hypergraph by \mathcal{J} , and put k:=|S|,\qquad q:=|E(\mathcal{J})|. The hypergraph \mathcal{J} is still r -uniform and intersecting unless it is empty. If \mathcal{J} is empty, then q=0 and \tau(\mathcal{J})=0 . Each selected vertex deletes at least four previously undeleted edges, so (1) m-q\geq 4k. Moreover, S together with any cover of \mathcal{J} covers all of \mathcal{H} . Hence r=\tau(\mathcal{H})\leq k+\tau(\mathcal{J}), and therefore (2) m\geq q+4\bigl(r-\tau(\mathcal{J})\bigr). Lemma 1 . Let \mathcal{J} be an r -uniform intersecting hypergraph with q edges and \Delta(\mathcal{J})\leq 3 . Then q\leq 2r+1. Proof. If q=0 , the result is immediate. Otherwise fix an edge E\in E(\mathcal{J}) . Since every other edge meets E , q-1\leq\sum_{v\in E}\bigl(\mathrm{d}_{\mathcal{J}}(v)-1\bigr). Each summand is at most 2 , because \Delta(\mathcal{J})\leq 3 . Thus q-1\leq 2r . ∎ We can already obtain the Erdős–Lovász bound by finding a greedy cover of \mathcal{J} of size at most q/3+r/6+2/3 . Indeed, while the current residual family has h\geq r+2 edges, a fixed edge sees total degree at least r+h-1\geq 2r+1 , so some vertex has degree 3 ; choose it and delete its three edges. Once h\leq r+1 , pair the remaining edges. This gives \tau(\mathcal{J})\leq\frac{q}{3}+\frac{r}{6}+\frac{2}{3}. Substituting this into ( 2 ) and then using Lemma 1 gives m\geq\frac{10r}{3}-\frac{q}{3}-\frac{8}{3}\geq\frac{8r}{3}-3. If we had the stronger residual estimate 4\tau(\mathcal{J})\leq q+r+4, then ( 2 ) would immediately give m\geq q+4r-(q+r+4)=3r-4. Thus Theorem 1 (i) is reduced to this residual cover bound.

Read the complete text