Problem 21

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?

Source: erdosproblems.com/21

Combinatorics
Intersecting families

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (LEAN), crediting Kahn [Ka94]; the Lean behind the qualifier is described below. The accepted claim is Kahn's linear bound.

BaWa21: J. Barát and I. M. Wanless, Intersecting and 2-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited. J. Combin. Des. (2021), 260-286. This is the site's entry; the print names J. Barát alone, J. Combin. Des. 29 (2021), no. 3, 193-209.
ErLo75: Erdős, P. and Lovász, L., Problems and results on $3$ -chromatic hypergraphs and some related questions. (1975), 609-627.
Ka92b: Kahn, Jeff, On a problem of Erdős and Lovász: random lines in a projective plane. Combinatorica (1992), 417-423.
Ka94: Kahn, Jeff, On a problem of Erdős and Lovász. II. $n(r)=O(r)$ . J. Amer. Math. Soc. (1994), 125-143.
Tr14: A. Tripathi, A result on intersecting families with maximum transversal size. arXiv:1409.4610 (2014).

Problem 21

Status

Proof claims

Discussion