← All problems

Erdős Problem #1075 — Dense subgraphs above the hypergraph edge threshold

52 years old · traced to

Fix an integer r≥3r\ge 3. An rr-uniform hypergraph is a pair H=(V,E)H=(V,E) with E⊆(Vr)E\subseteq\binom{V}{r}; write e(H)=∣E∣e(H)=|E|. The question asks whether there is a constant cr>r−rc_r>r^{-r}, depending only on rr, such that for every ϵ>0\epsilon>0, for all sufficiently large nn, every rr-uniform hypergraph HH on nn vertices satisfying

e(H)≥(1+ϵ)(nr)re(H)\ge (1+\epsilon)\left(\frac nr\right)^r

contains a subgraph on m=m(n)m=m(n) vertices with at least crmrc_rm^r edges, where m(n)→∞m(n)\to\infty as n→∞n\to\infty. The threshold for sufficiently large nn may depend on rr and ϵ\epsilon; the required coefficient crc_r is independent of ϵ\epsilon. Erdős Problem #1075 Erdős (1974)

Background

Erdős stated the question in his 1974 survey of extremal problems on graphs and hypergraphs. The benchmark (n/r)r(n/r)^r is the edge count of the complete balanced rr-partite rr-uniform hypergraph when rr divides nn: its rr classes each have size n/rn/r, and each edge chooses one vertex from every class. On m=rtm=rt vertices, the same construction has tr=mr/rrt^r=m^r/r^r edges, explaining the baseline coefficient in the problem. Erdős (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.