Problem 747

How large should $\ell(n)$ be such that, almost surely, a random $3$ -uniform hypergraph on $3n$ vertices with $\ell(n)$ edges must contain $n$ vertex-disjoint edges?

Source: erdosproblems.com/747

Combinatorics
Hypergraphs

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved: the site labels the problem SOLVED, records that Shamir asked it of Erdős in 1979, so that it is known as Shamir's problem, and that Erdős saw no way to guess the answer, and credits Johansson, Kahn and Vu [JKV08] with the threshold $\ell(n)\asymp n\log n$ and Kahn [Ka23] with the asymptotic $\ell(n)\sim n\log n$ , for $r$ -uniform hypergraphs in general.

Problem 747

Status

Proof claims

Discussion