Submit progress

on Erdős #719 · graph theory / hypergraphs

The 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 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$ ?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.