← All problems

Erdős Problem #837 — Density-increment thresholds for 3-uniform hypergraphs

52 years old · traced to

For a finite kk-uniform hypergraph GG, let ∣G∣|G| denote its number of vertices and e(G)e(G) its number of edges. For k≥2k\geq 2, the question defines Ak⊆[0,1]A_k\subseteq[0,1] using the following density-increment property: an \alpha\in[[0](#reference-0),[1](#reference-1)] belongs to AkA_k if there is a number β=β(α)>α\beta=\beta(\alpha)>\alpha such that, for every sequence (Gn)n≥1(G_n)_{n\geq1} of kk-uniform hypergraphs satisfying

lim inf⁡n→∞e(Gn)(∣Gn∣k)>α,\liminf_{n\to\infty}\frac{e(G_n)}{\binom{|G_n|}{k}}>\alpha,

there are subgraphs Hn⊆GnH_n\subseteq G_n for which ∣Hn∣→∞|H_n|\to\infty and

lim inf⁡n→∞e(Hn)(∣Hn∣k)>β.\liminf_{n\to\infty}\frac{e(H_n)}{\binom{|H_n|}{k}}>\beta.

The definition also requires that this property need not hold when the premise >α>\alpha is replaced by ≥α\geq\alpha. The question is to determine A3A_3. Erdős Problems #837

Background

This is a problem of Erdős and Simonovits, cited to their 1974 item “Unsolved Problems.” It asks for thresholds at which a uniform positive excess in the density of large hypergraphs forces arbitrarily large subgraphs with density bounded away above the threshold. Erdős Problems #837 Erdős, “Unsolved Problems” (1974)

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.