Erdős Problem #643

declared status 'open'. Formalized: no. Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that$$A\cup B= C\cup D$$and$$A\cap B=C\cap D=\emptyset.$$Estimate $f(n;t)$ - in particular, is it true that for $t\geq 3$$$f(n;t)=(1+o(1))\binom{n}{t-1}?$$ Current best: More generally, F\"{u}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\"{e}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\"{u}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. Prize: no. Tags: graph theory, hypergraphs.

Notation is rendered from the stored source. The pinned checkout remains the exact record.