← All problems

Duke–Erdős question on intersecting hypergraphs

For integers k≥2k\geq 2 and b≥1b\geq 1, let m(k,b)m(k,b) be the minimum number of edges in an intersecting kk-uniform hypergraph H=(V,E)H=(V,E) such that every (k−1)(k-1)-element subset S⊆VS\subseteq V is disjoint from at least bb edges of HH, with m(k,b)=+∞m(k,b)=+\infty if no such hypergraph exists. The Duke–Erdős question asks whether m(k,k)=o(k4)m(k,k)=o(k^4) as k→∞k\to\infty; equivalently, whether lim⁡k→∞m(k,k)/k4=0\lim_{k\to\infty}m(k,k)/k^4=0.

References

Progress summary

Refreshed
Open · progress reported

A new unrefereed preprint gives matching quadratic bounds in the main case, but leaves other parameter ranges open.

The Duke–Erdős question asks for the asymptotic growth of the relevant intersecting-hypergraph parameter, especially in the central case m(k,k)m(k,k). A new preprint claims to determine that order, while not settling the full parameter space.

November 2026 quadratic-order bounds

Guoqing Wang, Linlin Wang, and Jun Yue claim that, for all sufficiently large kk, k2+1≤m(k,k)≤Ck2k^2+1\le m(k,k)\le Ck^2, and more generally that m(k,b)=Θ(kb)m(k,b)=\Theta(kb) over a broad odd-kk range. This establishes quadratic order in the central case if correct, but the unrefereed preprint does not settle parameters outside its stated regime.

Current status (as of November 2026): The central case is claimed to have quadratic-order bounds, but the claim is unverified and the general parameter range remains open.

Sources

Solutions 0

No solutions have been posted yet.