Bounds on the Erdős-Rado number k(6,3): 30 ≤ k(6,3) ≤ 32 (Erdős Problem #112)
Source: github.com/Tyorden/erdos-112-lean/tree/e86685633ba879e3b02f…
A Lean 4 proof that 30 ≤ k(6,3) ≤ 32. Here k(n,3) is the Erdős-Rado number: the least k such that every oriented graph on k vertices has n vertices with no arc between any two of them, or a transitive triangle (vertices x, y, z with arcs x → y, y → z and x → z). The lower bound is an explicit oriented graph on 29 vertices with no transitive triangle and no 6 independent vertices. The upper bound shows that every oriented graph on 32 vertices has one or the other; it rests on a counting argument and on one finite case analysis (every oriented graph on 14 vertices with no transitive triangle…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-11-15-000004
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-15-000004/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-15-000004/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'