Erdős Problems

Tags Prizes

OPEN

Let $n=p^2+p+1$ for some prime power $p$, and let $A_1,\ldots,A_t\subseteq \{1,\ldots,n\}$ be a block design (so that every pair $x,y\in \{1,\ldots,n\}$ is contained in exactly one $A_i$).

Is it true that if $t>n$ then $t\geq n+p$?

#903: [Er82e]

combinatorics

A conjecture of Erdős and Sós. The classic finite geometry construction shows that $t=n$ is possible. A theorem of Erdős and de Bruijn [dBEr48] states that $t\geq n$.

In [Er82e] Erdős writes that he and Sós proved some special cases of this and the full conjecture was proved by Wilson, but I cannot find either reference.

In general, one can ask what the possible values of $t$ are, for a given $n$.