On a problem of Erdős and Lovász: random lines in a projective plane

../

---

Jeff Kahn, On a problem of Erdős and Lovász: random lines in a projective plane, Combinatorica 12 (1992), no. 4, 417–423, DOI 10.1007/BF01305234.

The edition read is the publisher's PDF of the journal article, seven pages with the journal pagination 417–423, obtained from the publisher's site for the DOI on 2026-10-16.

Let $n(k)$ be the least size of an intersecting family of $k$-sets whose cover number is $k$. Erdős and Lovász showed $n(k) \ge 8k/3 - 3$ and, when a projective plane of order $k-1$ exists, $n(k) \le 4k^{3/2} \log k$, and they conjectured $n(k) = O(k \log k)$. The paper proves the conjecture: there is a constant $A$ such that a uniformly random set of at least $A k \log k$ lines of a projective plane of order $k-1$ has cover number $k$ with probability tending to $1$ as $k \to \infty$, and Theorem 1 states this with the constant $22$. Hence $n(k) = O(k \log k)$ whenever such a plane exists.

Bears on. The theorem concerns random sets of lines in a finite projective plane and the point sets that meet all of them, the setting of [[../wiki/problems/set_systems/E1159/_index|Problem 1159's question on point sets meeting every line in between $1$ and $C$ points]]. No theorem from this source is used here to settle that question. Read status: claims checked for the abstract's Theorem and Corollary and for Theorem 1 and its Corollary in the introduction (p. 417), read clause by clause on the page image; the proofs on pp. 418–423 are unread, and no proof is verified on this card.

No file of this source is held: no license on record permits its redistribution. The article prints no license or usage notice on the pages read on 2026-10-16, and the Crossref record for the DOI, read 2026-10-16, names only the publisher's text-and-data-mining terms (http://www.springer.com/tdm) and no Creative Commons license, so every other right is reserved.