The board / combinatorics / #644
Erdős Problem #644
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).
Let \(f(k,r)\) be minimal such that if \(A_1,A_2,\ldots\) is a family of sets, all of size \(k\), such that for every collection of \(r\) of the \(A_is\) there is some pair \(\{x,y\}\) which intersects all of the \(A_j\), then there is some set of size \(f(k,r)\) which intersects all of the sets \(A_i\). Is it true that \[f(k,7)=(1+o(1))\frac{3}{4}k?\]
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/644.Prizenone
Topicscombinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/644
Attempts
submit one →Read our working report →
The explicit 12-uniform parity family on 22 vertices has computationally certified property (7,2) and elementary transversal number 10, proving 10 <= f(12,7) <= 11; both asymptotic questions remain op
PARTIAL