OFFSET
1,2
COMMENTS
a(n) is the smallest integer k such that there exists a family F of k sets, each of size n, with the properties: (1) any two sets in F have nonempty intersection, and (2) for every set S with |S| <= n-1, there exists some A in F with A intersect S = empty.
Conjectured by Erdős and Lovász to satisfy a(n) << n. Proved by Kahn who showed a(n) = O(n), and it has been speculated that a(n) = 3*n + O(1).
The lower bound (8/3)*n - O(1) <= a(n) was proved by Erdős and Lovász (1975) and has not been improved.
REFERENCES
P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609-627.
LINKS
J. Barát and I. M. Wanless, Intersecting and 2-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited, arXiv:2011.04444 [math.CO], 2020; J. Combin. Des. 29 (2021), 193-209.
T. F. Bloom, Erdős Problem #21, Erdős Problems.
J. Kahn, On a problem of Erdős and Lovász II: n(r) = O(r), J. Amer. Math. Soc. 7 (1994), 125-143.
A. Tripathi, A result on intersecting families with maximum transversal size, arXiv:1409.4610 [math.CO], 2014.
FORMULA
(8/3)*n - O(1) <= a(n) <= C*n for some constant C and all sufficiently large n.
Conjectured: a(n) = 3*n + O(1).
EXAMPLE
a(1) = 1: Any single 1-set {x} works trivially.
a(2) = 3: The family {{1,2}, {1,3}, {2,3}} is intersecting and for any singleton {x}, one of the 2-sets avoids x. No smaller family works.
a(3) = 6: A minimal family is {{1,2,3}, {1,2,4}, {1,5,6}, {2,5,6}, {3,4,5}, {3,4,6}}.
a(4) = 9: The unique extremal example (Tripathi 2014) on 11 vertices is {{1,2,3,4}, {1,5,6,7}, {2,5,8,9}, {3,6,8,10}, {4,7,9,10}, {1,8,9,11}, {2,6,7,11}, {3,4,5,11}, {1,2,5,10}}.
a(5) = 13: Three non-isomorphic extremal examples on 17 vertices were found by Barát and Wanless (2021).
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Iddo Drori, Jan 12 2026
STATUS
approved