---

Jeff Kahn proves, in On a problem of Erdős and Lovász. II: $n(r)=O(r)$ (card), that the function $f$ of Problem 21, written $n(r)$ in the paper, satisfies $n(r)=O(r)$: the least size of an intersecting family of $r$-sets such that every set of at most $r-1$ elements is disjoint from some member is at most a constant times $r$, which is the inequality $f(n)\ll n$ the problem asks for. The theorem is stated through a fixed prime power $K$: for all sufficiently large $t$ and prime powers $q\equiv3\pmod4$ with $q<t\leq(1+K^{-2})q$, the value $r=Kq+t$ has $n(r)\leq5(K^2+K)t$, and every sufficiently large $r$ has this form. The constant is about $5K$ and is not evaluated. The construction is given in dual form, an $r$-regular hypergraph on $5(K^2+K)t$ vertices in which every two vertices share an edge and whose edge cover number is $r$, built from $5$-regular bipartite expander-like graphs and transversal designs $\mathrm{TD}(K,t)$, whose existence for large $t$ is the transversal-design form of the Chowla–Erdős–Straus theorem on mutually orthogonal Latin squares (Kahn cites Wilson 1974 for the equivalence). Erdős and Lovász had posed the problem with the bounds $\frac83n-3\leq f(n)\ll n^{3/2}\log n$ (card), and Kahn had earlier lowered the upper bound to $O(n\log n)$ [Ka92b]; both upper bounds take random lines of a projective plane of order $n-1$, so they assume such a plane exists, as it does when $n-1$ is a prime power. Kahn's 1994 paper calls the lower bound $\frac83n-O(1)$ still unimproved. The site's commentary reports that the truth has been speculated to be $3n+O(1)$ and cites [Ka94], but the paper makes no such conjecture: its remark that a constant is probably $3$ (p. 126) concerns the number $Cr\log r$ of random lines of a projective plane needed in its Theorem 1.2, not $f(n)$. A 2026 preprint of Sivashankar (arXiv:2606.24878) claims the lower bound $f(n)\geq3n-4$ and, through Kahn's hypergraph edge-coloring theorem, $f(n)\geq(\frac{41-\sqrt{19}}{12}-o(1))n$, which would refute that speculation; it is unrefereed and is recorded on the problem page, since it does not bear on whether $f(n)\ll n$. Exact small values: $f(1)=1$ and $f(2)=3$ are trivial, $f(3)=6$ was known and is reproved, and $f(4)=9$ is proved, by Tripathi (the site credits both $f(3)$ and $f(4)$ to him), and $f(5)=13$ with $13\leq f(6)\leq18$ by Barát; these bound the function at single arguments and are not part of the claim.

Acceptance. Refereed: J. Amer. Math. Soc. 7 (1994), no. 1, 125–143, received 15 April 1992; the publisher's record dates the issue January 1994 without a day, and the page's date is the first of that month. Reviewed: Thomas Bloom, the site's curator, marks the problem proved and credits the solution to Kahn [Ka94]. The site's label adds a Lean qualification. The formal-conjectures statement file for the problem states the question with the answer true, leaves its proof as sorry and points, through its formal_proof attribute, at the Lean file in Boris Alexeev's lean-proofs collection linked above at its pinned commit, which declares itself a formalization of Kahn's solution with Codex and GPT-5.6 Sol as formal authors. This corpus has not built or audited that file, so the page lists no formalized evidence. The library card does not verify the proof and is not acceptance evidence.