Erdős Problem #1075 — Dense subgraphs above the hypergraph edge threshold
Fix an integer . An -uniform hypergraph is a pair with ; write . The question asks whether there is a constant , depending only on , such that for every , for all sufficiently large , every -uniform hypergraph on vertices satisfying
contains a subgraph on vertices with at least edges, where as . The threshold for sufficiently large may depend on and ; the required coefficient is independent of . 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 is the edge count of the complete balanced -partite -uniform hypergraph when divides : its classes each have size , and each edge chooses one vertex from every class. On vertices, the same construction has edges, explaining the baseline coefficient in the problem. Erdős (1974)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
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.