← All problems

Erdős Problem #794 — A Density Threshold for 3-Uniform Hypergraphs

1 year old · traced to

Let n be a positive integer and let G=V,EV,E 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

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.