Erdős Problems

Tags Prizes

All Random Solved Random Open

SOLVED

For any $g\geq 2$, if $n$ is sufficiently large and $\equiv 1,3\pmod{6}$ then there exists a 3-uniform hypergraph on $n$ vertices such that

every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner triple system) and
for any $2\leq j\leq g$ any collection of $j$ edges contains at least $j+3$ vertices.

combinatorics, hypergraphs

Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].