Problem Statement
Let $f(n)$ be minimal such that there is an intersecting family $\mathcal{F}$ of sets of size $n$ (so $A\cap B\neq\emptyset$ for all $A,B\in \mathcal{F}$) with $\lvert \mathcal{F}\rvert=f(n)$ such that any set $S$ with $\lvert S\rvert \leq n-1$ is disjoint from at least one $A\in \mathcal{F}$.
Is it true that\[f(n) \ll n?\]
Is it true that\[f(n) \ll n?\]
Categories:
Combinatorics Intersecting Family
Progress
Conjectured by Erdős and Lovász [ErLo75], who proved that\[\frac{8}{3}n-3\leq f(n) \ll n^{3/2}\log n\]for all $n$. The upper bound was improved by Kahn [Ka92b] to\[f(n) \ll n\log n.\](The upper bound constructions in both cases are formed by taking a random set of lines from a projective plane of order $n-1$, assuming $n-1$ is a prime power.)This problem was solved by Kahn [Ka94] who proved the upper bound $f(n) \ll n$. The Erdős-Lovász lower bound of $\frac{8}{3}n-O(1)$ has not been improved, and it has been speculated (see e.g. [Ka94]) that the correct answer is $3n+O(1)$.
It is trivial that $f(1)=1$ and $f(2)=3$. The values $f(3)=6$ and $f(4)=9$ were established by Tripathi [Tr14]. Barát and Wanless [BaWa21] proved that $f(5)=13$, and that $13\leq f(6)\leq 18$.
Source: erdosproblems.com/21 | Last verified: January 13, 2026