Extremal edge count forcing two disjoint edge-pairs with equal union in a $t$-uniform hypergraph (Erdős #643)
Statement
For $t\geq 2$, let $f(n;t)$ be the least integer such that every $t$-uniform hypergraph on $n$ vertices with at least $f(n;t)$ edges must contain four distinct edges $A,B,C,D$ satisfying $$A\cup B=C\cup D\quad\text{and}\quad A\cap B=C\cap D=\emptyset$$ (that is, two disjoint pairs of edges having the same union). Estimate $f(n;t)$. In particular, is it true that for every $t\geq 3$ $$f(n;t)=(1+o(1))\binom{n}{t-1}?$$
Acceptance. FULLY RESOLVES: a complete proof determining the asymptotics of $f(n;t)$ for $t\geq 3$ — in particular a proof or disproof of $f(n;t)=(1+o(1))\binom{n}{t-1}$ — machine-checkable (Lean/Coq) preferred, otherwise a full written proof. ADVANCES (each independently checkable): (a) prove that $\lim_{n\to\infty} f(n;t)/\binom{n}{t-1}$ exists for some $t\geq 4$ (open); (b) improve the constant bounds stated in the background — a $\limsup$ upper bound strictly below $\min(7/4,1+2/\sqrt t)$ for some $t$, or a lower bound strictly above $1$, with proof; (c) improve the $t=3$ upper bound below the best value stated in the background (currently $\tfrac{13}{9}\binom{n}{2}$), with proof; or (d) determine exact values of $f(n;3)$ for new small $n$ via verified exhaustive computation, with the search code and an exhaustiveness certificate. Deliver the proof, the improved bound with proof, or the search code plus exact small-case values.
Background
A problem of Erdős [Er77b], [Er97d]; listed as open on erdosproblems.com/643 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs'). For $t=2$ the forbidden configuration is exactly a $4$-cycle $C_4$ (four vertices carrying two disjoint edges each of two colours), so $f(n;2)$ is the Zarankiewicz/Kővári–Sós–Turán threshold and $f(n;2)=(\tfrac12+o(1))n^{3/2}$. For $t\geq 3$ the frontier is: Füredi [Fu84] proved $f(n;3)\ll n^2$ and $f(n;3)>\binom{n}{2}$ for infinitely many $n$, and more generally $$\binom{n-1}{t-1}+\left\lfloor\tfrac{n-1}{t}\right\rfloor\leq f(n;t)<\tfrac{7}{2}\binom{n}{t-1},$$ conjecturing the lower bound is sharp for $t\geq 4$. Pikhurko and Verstraëte [PiVe09] proved $f(n;3)\leq \tfrac{13}{9}\binom{n}{2}$ for all $n$, and that $$1\leq \limsup_{n\to\infty}\frac{f(n;t)}{\binom{n}{t-1}}\leq \min\!\left(\tfrac74,\,1+\tfrac{2}{\sqrt t}\right)$$ for all $t\geq 3$. Füredi also proved $f(n;3)/\binom{n}{2}$ converges as $n\to\infty$, but the existence of the limit for $t\geq 4$ is unknown. The conjectured $(1+o(1))\binom{n}{t-1}$ asserts the limiting ratio is exactly $1$. No Erdős prize is attached. Attacker's tool: exact extremal computation (ILP / exhaustive construction search) of $f(n;3)$ for small $n$ to bracket the limiting constant, plus explicit hypergraph constructions to push the lower bound toward $\binom{n}{t-1}$ and improved counting to lower the upper constant.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #643 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.