/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
Local copy of the binary ordinal Ramsey predicate $\alpha \to (\beta, \gamma)^2$:
every 2-coloring of pairs from $\alpha$ admits a red clique of order type $\beta$ or a
blue clique of order type $\gamma$.
Will be replaced by OrdinalRamsey from FormalConjecturesForMathlib/SetTheory/Ordinal/ PartitionRelation.lean once that lands (see PR #4195).
Erdős Problem 118 (problem of Erdős and Hajnal). Let $\alpha$ be such that
$\alpha \to (\alpha, 3)^2$. For every $n \ge 3$, must $\alpha \to (\alpha, n)^2$?
The original question is asked for cardinals, ordinals, and order types; we state the
ordinal version, which is the standard reading: ordinals $\alpha$ with
$\alpha \to (\alpha, 3)^2$ are called partition ordinals.
The answer is no, shown independently by Schipperus [Sc99, Sc10] and Darby [Da99].
Larson [La00] gave the concrete counterexample $\alpha = \omega^{\omega^2}$, for which
$\alpha \to (\alpha, 3)^2$ holds yet $\alpha \not\to (\alpha, 5)^2$. See Chapter 2.9 of
[HST10] for further background.
@[categoryresearchsolved,question,AMS3]theoremerdos_118:¬∀α:Ordinal.{0},OrdinalRamseyαα3→∀n:ℕ,3≤n→OrdinalRamseyααn:=⊢ ¬∀(α:Ordinal.{0}),OrdinalRamseyαα3→∀(n:ℕ),3≤n→OrdinalRamseyαα↑nAll goals completed! 🐙/- ### Known results -/namespaceerdos_118.variants
Larson (2000). The ordinal $\alpha = \omega^{\omega^2}$ is a partition ordinal,
$\omega^{\omega^2} \to (\omega^{\omega^2}, 3)^2$, yet
$\omega^{\omega^2} \not\to (\omega^{\omega^2}, 5)^2$ [La00], so the answer to the
Erdős–Hajnal question is negative already at $n = 5$.
Monotonicity in the blue side. If the ordinal Ramsey relation holds with blue
target $\gamma$, it holds with any smaller blue target $\gamma' \le \gamma$. In
particular, a failure of $\alpha \to (\alpha, 3)^2$ implies a failure of
$\alpha \to (\alpha, n)^2$ for every $n \ge 3$.
inrα:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γ⊢ (∃s,red.IsCliques∧typeLT↑s=β)∨∃s,blue.IsCliques∧typeLT↑s=γ'obtain⟨g⟩:=Ordinal.type_le_iff'.mp(htype▸hγ)inrα:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2⊢ (∃s,red.IsCliques∧typeLT↑s=β)∨∃s,blue.IsCliques∧typeLT↑s=γ'lett:Setα.ToType:=Set.range(Subtype.val∘g)inrα:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)⊢ (∃s,red.IsCliques∧typeLT↑s=β)∨∃s,blue.IsCliques∧typeLT↑s=γ'refineOr.inr⟨t,?_,?_⟩inr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)⊢ blue.IsCliquetinr.refine_2α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)⊢ typeLT↑t=γ'·inr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)⊢ blue.IsCliquet-- t is a blue cliquerintro_⟨a,rfl⟩_⟨b,rfl⟩hneinr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val∘⇑g)a≠(Subtype.val∘⇑g)b⊢ blue.Adj((Subtype.val∘⇑g)a)((Subtype.val∘⇑g)b)applyhblue(ga).2(gb).2inr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val∘⇑g)a≠(Subtype.val∘⇑g)b⊢ ↑(ga)≠↑(gb)introhinr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh✝:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val∘⇑g)a≠(Subtype.val∘⇑g)bh:↑(ga)=↑(gb)⊢ Falseapplyhneinr.refine_1α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh✝:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val∘⇑g)a≠(Subtype.val∘⇑g)bh:↑(ga)=↑(gb)⊢ (Subtype.val∘⇑g)a=(Subtype.val∘⇑g)bsimp[h]All goals completed! 🐙·inr.refine_2α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)⊢ typeLT↑t=γ'-- typeLT t = γ'letemb:(·<·:γ'.ToType→γ'.ToType→Prop)↪r(·<·:↑t→↑t→Prop):={toFun:=funa=>⟨(ga).val,a,rfl⟩inj':=funabheq=>g.injective(Subtype.ext(congr_arg(funx:↑t=>x.val)heq))map_rel_iff':=g.map_rel_iff}inr.refine_2α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)emb:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2:={toFun:=funa↦⟨↑(ga),⋯⟩,inj':=⋯,map_rel_iff':=⋯}⊢ typeLT↑t=γ'havehsurj:Function.Surjectiveemb:=fun⟨_,hy⟩=>⟨hy.choose,Subtype.exthy.choose_spec⟩inr.refine_2α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLTγ'.ToType≤γh:OrdinalRamseyαβγred:SimpleGraphα.ToTypeblue:SimpleGraphα.ToTypehCompl:IsComplredblues:Setα.ToTypehblue:blue.IsCliqueshtype:typeLT↑s=γg:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2t:Setα.ToType:=Set.range(Subtype.val∘⇑g)emb:(funx1x2↦x1<x2)↪rfunx1x2↦x1<x2:={toFun:=funa↦⟨↑(ga),⋯⟩,inj':=⋯,map_rel_iff':=⋯}hsurj:Function.Surjective⇑emb⊢ typeLT↑t=γ'exact(Ordinal.type_eq.mpr⟨RelIso.ofSurjectiveembhsurj|>.symm⟩).trans(Ordinal.type_toTypeγ')All goals completed! 🐙endErdos118