Erdős Problem #794 — A Density Threshold for 3-Uniform Hypergraphs
Let n be a positive integer and let G= be a 3-uniform hypergraph, meaning that E is a set of 3-element subsets of V. Is it true that for every such G with |V|=3n and |E|≥n^3+1, there is either a 4-element set supporting at least 3 edges of G, or a 5-element set supporting at least 7 edges? The first forbidden configuration is K_4^−, the 3-graph on four vertices with three edges; “supporting” allows the subgraph to be non-induced. Erdős Problems #794 arXiv:1201.4326
Background
The problem is recorded as Erdős [Er69, p. 81]. Its edge threshold is naturally compared with the Turán problem for K_4^−: on 3n vertices, n^3 edges have asymptotic density n^3/\binom{3n}{3}→2/9. But the known lower-bound construction of Frankl and Füredi gives K_4^−-free 3-graphs of asymptotic density at least 2/7, so the proposed threshold is below that construction’s density. Turán had earlier conjectured the value 1/4; the 2/7 construction disproved that conjecture. Erdős Problems #794 arXiv:1201.4326 Keevash, Hypergraph Turán Problems
The density comparison concerns ordinary, non-induced containment of K_4^−. In the general Turán framework, one asks for the maximum number of edges in an F-free r-uniform hypergraph on a given number of vertices; for K_4^−, determining the asymptotic maximum remains a distinct question from the specific finite-threshold assertion posed here. arXiv:1201.4326 Keevash, Hypergraph Turán Problems
Progress summary
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.