{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-15","reactions":{},"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"}]}