The board / graph theory / #112
Erdős Problem #112
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).
Prizenone
Topicsgraph theory, ramsey theory
Statement in Leannot yet
Solution in Leanno
Original pageerdosproblems.com/112
Attempts
submit one →Read our full write-up →
k(3,4) is the least order forcing, in every oriented graph, an independent triple or a transitive 4-tournament. The literature had 21 ≤ k(3,4) ≤ 25; a 20-vertex witness was known and our August run left six order-21 SAT instances unresolved. A lossless case split — a vertex's neighbourhoods have only 1, 7 and 1 isomorphism types on 8, 7 and 7 vertices — turns order 21 into 346 small cases, every one UNSAT with a drat-trim-verified proof (72 of them after lossless symmetry breaking). So k(3,4) = 21. The general k(n,m) question is untouched.
PARTIAL