← All problems

Erdős Problem #500 — What is ex3(n,K43)\mathrm{ex}_3(n,K_4^3)?

64 years old · documented by

For an integer n≥0n\ge 0, let a 33-uniform hypergraph on an nn-element vertex set VV have an edge set E⊆(V3)E\subseteq\binom{V}{3}. A copy of K4(3)K_4^{(3)} is a four-element set Q⊆VQ\subseteq V for which all four triples are edges. The question is to determine, for each nn, the Turán number

ex3(n,K4(3))=max⁡{∣E∣:E⊆(V3),(Q3)⊈E for every Q∈(V4)}.\mathrm{ex}_3(n,K_4^{(3)})=\max\left\{|E|: E\subseteq\binom{V}{3},\quad \binom{Q}{3}\nsubseteq E\text{ for every }Q\in\binom{V}{4}\right\}.

In particular, ex3(n,K4(3))=0\mathrm{ex}_3(n,K_4^{(3)})=0 for n<4n<4. This is a non-induced forbidden-subhypergraph problem: it excludes four vertices carrying all four triples, without imposing conditions on the other triples among those vertices. Erdős Problems #500 Keevash, Hypergraph Turán Problems

Background

This is the tetrahedron case of the hypergraph Turán problem: for a fixed forbidden uniform hypergraph, maximize the number of edges while avoiding a copy of it. Turán posed the complete-uniform-hypergraph problem in 1941. The contrast with ordinary graph theory is striking: Turán’s theorem determines the extremal numbers for complete graphs, while even the asymptotic density for the 3-uniform tetrahedron problem remains undetermined in the cited accounts. Erdős offered prizes for solutions to particular cases and for a general solution. Keevash, Hypergraph Turán Problems

Turán’s proposed construction partitions the vertices into three nearly equal classes X1,X2,X3X_1,X_2,X_3, with indices taken cyclically. It includes triples meeting all three classes and triples with two vertices in XiX_i and one in Xi+1X_{i+1}. This construction motivates the conjectured asymptotic density 5/95/9. The normalized extremal numbers have a limit, the Turán density

π(K4(3))=lim⁡n→∞ex3(n,K4(3))(n3),\pi(K_4^{(3)})=\lim_{n\to\infty}\frac{\mathrm{ex}_3(n,K_4^{(3)})}{\binom{n}{3}},

so determining this density would give the leading asymptotic term, though not by itself all finite values of ex3(n,K4(3))\mathrm{ex}_3(n,K_4^{(3)}). Erdős Problems #500 Keevash, Hypergraph Turán Problems

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.