The board / graph theory / #712
Erdős Problem #712
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there exists no set of \(k\) vertices which is covered by all \(\binom{k}{r}\) possible \(r\)-edges.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/712.Prize$500
Topicsgraph theory, turan number, hypergraphs
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/712
Attempts
submit one →Read our working report →
Proved the exact covering-design reduction, closed three near-diagonal finite regimes (including all ex_3(n,K_{n-2}^3)), and independently certified ex_3(n,K_4^3)=3,7,14,23,36,54 for n=4,...,9; no com
PARTIAL