/- 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. -/ module public import FormalConjecturesUtil

Erdős Problem 118

Reference: erdosproblems.com/118

References:

    [Sc99] Schipperus, R. Countable partition ordinals. Thesis, University of Colorado (1999).

    [Sc10] Schipperus, R. Countable partition ordinals. Ann. Pure Appl. Logic 161 (2010), 1195–1215.

    [Da99] Darby, C. Negative partition relations for ordinals $\omega^{\omega^\delta}$. J. Combin. Theory Ser. B 76 (1999), 205–222.

    [La00] Larson, J. A. An ordinal partition avoiding pentagrams. J. Symbolic Logic 65 (2000), 969–978.

    [HST10] Hajnal, A.; Larson, J. A. Partition relations. Handbook of set theory, Springer (2010), 129–213.

@[expose] public sectionopen Cardinal Ordinalopen scoped Cardinalnamespace Erdos118universe u

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).

def OrdinalRamsey (α β γ : Ordinal.{u}) : Prop := ∀ red blue : SimpleGraph α.ToType, IsCompl red blue → (∃ s, red.IsClique s ∧ typeLT s = β) ∨ (∃ s, blue.IsClique s ∧ typeLT s = γ)

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.

@[category research solved, question, AMS 3] theorem erdos_118 : ¬ ∀ α : Ordinal.{0}, OrdinalRamsey α α 3 → ∀ n : ℕ, 3 ≤ n → OrdinalRamsey α α n := ⊢ ¬∀ (α : Ordinal.{0}), OrdinalRamsey α α 3 → ∀ (n : ℕ), 3 ≤ n → OrdinalRamsey α α ↑n All goals completed! 🐙/- ### Known results -/ namespace erdos_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$.

@[category research solved, AMS 3] theorem larson : OrdinalRamsey (ω ^ ω ^ (2 : Ordinal)) (ω ^ ω ^ (2 : Ordinal)) 3 ∧ ¬ OrdinalRamsey (ω ^ ω ^ (2 : Ordinal)) (ω ^ ω ^ (2 : Ordinal)) 5 := ⊢ OrdinalRamsey (ω ^ ω ^ 2) (ω ^ ω ^ 2) 3 ∧ ¬OrdinalRamsey (ω ^ ω ^ 2) (ω ^ ω ^ 2) 5 All goals completed! 🐙end erdos_118.variants

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$.

α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γ⊢ (∃ s, red.IsClique s ∧ typeLT ↑s = β) ∨ ∃ s, blue.IsClique s ∧ typeLT ↑s = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2⊢ (∃ s, red.IsClique s ∧ typeLT ↑s = β) ∨ ∃ s, blue.IsClique s ∧ typeLT ↑s = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)⊢ (∃ s, red.IsClique s ∧ typeLT ↑s = β) ∨ ∃ s, blue.IsClique s ∧ typeLT ↑s = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)⊢ blue.IsClique tα:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)⊢ typeLT ↑t = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)⊢ blue.IsClique t -- t is a blue clique α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ 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) α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val ∘ ⇑g) a ≠ (Subtype.val ∘ ⇑g) b⊢ ↑(g a) ≠ ↑(g b) α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh✝:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val ∘ ⇑g) a ≠ (Subtype.val ∘ ⇑g) bh:↑(g a) = ↑(g b)⊢ False α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh✝:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)a:γ'.ToTypeb:γ'.ToTypehne:(Subtype.val ∘ ⇑g) a ≠ (Subtype.val ∘ ⇑g) bh:↑(g a) = ↑(g b)⊢ (Subtype.val ∘ ⇑g) a = (Subtype.val ∘ ⇑g) b All goals completed! 🐙 α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)⊢ typeLT ↑t = γ' -- typeLT t = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)emb:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2 := { toFun := fun a ↦ ⟨↑(g a), ⋯⟩, inj' := ⋯, map_rel_iff' := ⋯ }⊢ typeLT ↑t = γ' α:Ordinal.{u}β:Ordinal.{u}γ:Ordinal.{u}γ':Ordinal.{u}hγ:typeLT γ'.ToType ≤ γh:OrdinalRamsey α β γred:SimpleGraph α.ToTypeblue:SimpleGraph α.ToTypehCompl:IsCompl red blues:Set α.ToTypehblue:blue.IsClique shtype:typeLT ↑s = γg:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2t:Set α.ToType := Set.range (Subtype.val ∘ ⇑g)emb:(fun x1 x2 ↦ x1 < x2) ↪r fun x1 x2 ↦ x1 < x2 := { toFun := fun a ↦ ⟨↑(g a), ⋯⟩, inj' := ⋯, map_rel_iff' := ⋯ }hsurj:Function.Surjective ⇑emb⊢ typeLT ↑t = γ' All goals completed! 🐙end Erdos118