Problem #643: Let $f(n;t)$ be minimal such that if a $t$-uniform...

---

Progress

For $t=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1/2+o(1))n^{3/2}$.

Füredi [Fu84] proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. Pikhurko and Verstraëte [PiVe09] have proved $f(n;3)\leq \frac{13}{9}\binom{n}{2}$ for all $n$.

More generally, Füredi [Fu84] proved that\[\binom{n-1}{t-1}+\left\lfloor\frac{n-1}{t}\right\rfloor\leq f(n;t) < \frac{7}{2}\binom{n}{t-1},\]and conjectured the lower bound is sharp for $t\geq 4$. Pikhurko and Verstraëte [PiVe09] have proved that\[1 \leq \limsup_{n\to \infty} \frac{f(n;t)}{\binom{n}{t-1}}\leq \min\left(\frac{7}{4},1+\frac{2}{\sqrt{t}}\right)\]for all $t\geq 3$.

Füredi [Fu84] proved that $f(n;3)/\binom{n}{2}$ converges as $n\to \infty$, but the existence of the limit for $t\geq 4$ is unknown.