Problem 719

Let $\mathrm{ex}_r(n;K_{r+1}^r)$ be the maximum number of $r$ -edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$ (the $r$ -uniform complete graph on $r+1$ vertices).

Is every $r$ -hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$ , no two of which share a $K_r^r$ ?

Second statement

Let $\mathrm{ex}_r(n;K_{r+1}^r)$ be the maximum number of $r$ -edges that can be placed on $n$ vertices without forming a $K_{r+1}^r$ (the $r$ -uniform complete graph on $r+1$ vertices).

Is every $r$ -hypergraph $G$ on $n$ vertices, for $r\ge2$ , the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$ , no two of which share a $K_r^r$ ?

Source: erdosproblems.com/719

Graph theory
Hypergraphs

Wiki page

Status

Open

No claim settles this problem.

Open on erdosproblems.com (label OPEN; the site's notes call it a conjecture of Erdős and Sauer).

Notes

The site's wording, like Erdős's in [Er81] (Part IV, item 3), states no range for $r$ . With $r=1$ it fails trivially: the edges of a $1$ -uniform hypergraph are single vertices, $\mathrm{ex}_1(n;K_2^1)=1$ , and the hypergraph of all $n\ge3$ singletons needs at least $\lceil n/2\rceil\ge2$ copies of $K_1^1$ and $K_2^1$ . The corrected Statement adds only the range $r\ge2$ . Erdős poses the conjecture for $r$ -graphs as the generalization of the Erdős–Goodman–Pósa theorem on graphs, the case $r=2$ ([Er81], Part IV, item 3), and the formal-conjectures statement assumes $r\ge2$ .

Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25-42; Part IV, item 3, where the conjecture is stated after the Erdős–Goodman–Pósa theorem it generalizes.
EGP66: Erdős, P., Goodman, A. W. and Pósa, L., The representation of a graph by set intersections. Canad. J. Math. 18 (1966), 106-112; Theorem 4 is the case $r=2$ . Not cited by the site for this problem.

Problem 719

Second statement

Status

Notes

Proof claims

Discussion