Id: palomar/PALOMAR-2026-11-15-000004 Url: https://github.com/Tyorden/erdos-112-lean/tree/e86685633ba879e3b02f31281dc2c7a8ce996bcc Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-15-000004-v1.json Repo: https://github.com/Tyorden/erdos-112-lean Tags: math.CO, msc:05C55, msc:05C20 Score: 0 Title: Bounds on the Erdős-Rado number k(6,3): 30 ≤ k(6,3) ≤ 32 (Erdős Problem #112) Trust: high Domain: math.CO Source: palomar Authors: Tyler Satchel Orden Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-15 Formalized: true Formalizes: title=New bounds on the Erdős-Rado number k(6,3) identifier=https://doi.org/10.5281/zenodo.24064871 relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-15-000004 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…