AFTD Auto-Formalizing Theoretical Domains

not_op_1406_weakened_cycle_ramsey_number_ge_self

theoremverifiedoriginal

The statement op_1406_weakened_cycle_ramsey_number_ge_self is false: The case t = 1 makes it false. weakened_cycle_ramsey_property t ℓ n demands that for every colouring c : (K_n).edgeSet → Fin t there is a colour j such that C_ℓ embeds in the subgraph of edges whose colour is ≠ j. When t = 1 (so the codomain is Fin 1), for every colouring c and every j : Fin 1 we have c e = j for all e (Subsingleton.elim), hence color_avoiding_subgraph (completeGraph (Fin n)) c j has no edges at all, i.e. equals ⊥. But for ℓ ≥ 3 the cycle graph C_ℓ has an edge (e.g. cycleGraph 3 has Adj 0 1), and a graph with an edge admits no homomorphism into ⊥ (map_adj gives an edge in ⊥, contradiction). Therefore weakened_cycle_ramsey_property 1 3 n is false for every n, so {n | weakened_cycle_ramsey_property 1 3 n} = ∅ and weakened_cycle_ramsey_number 1 3 = sInf ∅ = 0. Taking t = 1, ℓ = 3 (which satisfy 1 ≤ t and 3 ≤ ℓ) gives 3 ≤ 0, a contradiction. Hence the universally quantified statement is false; the paper's theorem needs t ≥ 2 (one needs at least two colours in order to avoid one of them).

Statement

theorem not_op_1406_weakened_cycle_ramsey_number_ge_self : ¬ (∀ (t ℓ : ℕ) (ht : 1 ≤ t) (hℓ : 3 ≤ ℓ), ℓ ≤ weakened_cycle_ramsey_number t ℓ)
Related work
refutes `op_1406_weakened_cycle_ramsey_number_ge_self`
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • weakened_cycle_ramsey_numberThe weakened multicolour Ramsey number weakened_cycle_ramsey_number t ℓ of a cycle C_ℓ is the least integer n such that every…
  • color_avoiding_subgraphFor a simple graph G and an edge colouring c with colours in C, the j-avoiding subgraph color_avoiding_subgraph G c j is the spanning…
  • weakened_cycle_ramsey_propertyThe weakened cycle Ramsey property weakened_cycle_ramsey_property t ℓ n holds if every t-edge-colouring of the complete graph K_n contains…

The proof, explained

The proof proceeds by contradiction: assuming the universal inequality holds for all t ≥ 1 and ℓ ≥ 3, specializing to t = 1 and ℓ = 3 gives 3 ≤ weakened_cycle_ramsey_number 1 3. However, when t = 1, any edge colouring uses only the single colour in Fin 1, so the subgraph of edges avoiding that colour contains no edges at all (it is the empty graph ⊥). Since the 3-cycle C₃ contains edges, it cannot embed into ⊥, meaning no n satisfies the weakened Ramsey property; the set of witnesses is empty, so its infimum in ℕ is 0, giving 3 ≤ 0.

  1. Assuming the universal statement, specializing to t = 1 and ℓ = 3 yields 3 ≤ weakened_cycle_ramsey_number 1 3.

    We assume for contradiction the universal statement that ℓ ≤ weakened_cycle_ramsey_number t ℓ for all t ≥ 1 and ℓ ≥ 3. Specializing to t = 1 and ℓ = 3—with the hypothesis 1 ≤ 1 discharged by reflexivity (`le_rfl`) and 3 ≤ 3 by numerical evaluation—gives 3 ≤ weakened_cycle_ramsey_number 1 3.

    lines 2–3

    uses le_rfl

      intro h
      have h1 : 3 ≤ weakened_cycle_ramsey_number 1 3 := h 1 3 le_rfl (by norm_num)
  2. To show weakened_cycle_ramsey_number 1 3 = 0, we aim to show no natural number n satisfies the weakened Ramsey property; assuming an arbitrary n does, the constant colouring yields a colour j and an embedding of C₃ into the j-avoiding subgraph.

    By definition, the weakened Ramsey number is the infimum of the set of integers n satisfying the property. To show this number is 0, we aim to show the set is empty (`hset`). For an arbitrary n, we assume the property holds and test it on the constant colouring assigning 0 : Fin 1 to every edge. This yields a colour j : Fin 1 and an injective graph homomorphism `hom` from C₃ into the subgraph of edges whose colour is not j.

    lines 4–10

    uses Set.mem_setOf_eq, Set.mem_empty_iff_false, iff_false

      have h0 : weakened_cycle_ramsey_number 1 3 = 0 := by
        unfold weakened_cycle_ramsey_number
        have hset : {n : ℕ | weakened_cycle_ramsey_property 1 3 n} = ∅ := by
          ext n
          simp only [Set.mem_setOf_eq, Set.mem_empty_iff_false, iff_false]
          intro hp
          obtain ⟨j, hom, hinj⟩ := hp (fun _ => (0 : Fin 1))
  3. In a single-colour colouring, the subgraph of edges avoiding colour j has no edges (it equals ⊥), so the embedding is a homomorphism from C₃ into ⊥.

    The j-avoiding subgraph consists of edges whose colour differs from j. But every edge has colour 0, and because Fin 1 is a subsingleton, j must equal 0 (`Subsingleton.elim`). Thus no edge satisfies 0 ≠ j, meaning the edge set is empty and the graph is ⊥ (`SimpleGraph.fromEdgeSet_adj`). Rewriting by this equality updates the embedding to a homomorphism from C₃ to ⊥.

    lines 11–18

    uses SimpleGraph.fromEdgeSet_adj, Subsingleton.elim

          rw [show color_avoiding_subgraph (SimpleGraph.completeGraph (Fin n)) (fun _ => (0 : Fin 1)) j = ⊥ from by
            ext a b
            rw [color_avoiding_subgraph, SimpleGraph.fromEdgeSet_adj]
            constructor
            · rintro ⟨⟨_, hne⟩, _⟩
              exact absurd (Subsingleton.elim _ j) hne
            · intro hh
              exact absurd hh (by simp)] at hom
  4. No n can satisfy the weakened Ramsey property for t = 1 and ℓ = 3, so the set of witnesses is empty.

    The cycle C₃ contains an edge between vertices 0 and 1 (verified by finite decision procedure). Graph homomorphisms preserve adjacency (`map_adj`), so this edge must map to an edge in ⊥. But ⊥ has no edges, which simplifies to False and closes the goal, proving that {n | weakened_cycle_ramsey_property 1 3 n} = ∅.

    lines 19–20

          have hadj := hom.map_adj (show (SimpleGraph.cycleGraph 3).Adj 0 1 by decide)
          simp at hadj
  5. weakened_cycle_ramsey_number 1 3 = 0.

    Rewriting with the empty set of witnesses and using the fact that the infimum of the empty set in ℕ is 0 (`Nat.sInf_empty`) establishes that weakened_cycle_ramsey_number 1 3 = 0.

    line 21

    uses Nat.sInf_empty

        rw [hset, Nat.sInf_empty]
  6. Contradiction. automation

    We have derived both 3 ≤ weakened_cycle_ramsey_number 1 3 and weakened_cycle_ramsey_number 1 3 = 0, which implies 3 ≤ 0. Linear integer arithmetic (`omega`) detects this contradiction and closes the proof.

    line 22

      omega
le_rfl
In any preorder, every element is less than or equal to itself (a ≤ a).
Set.mem_setOf_eq
An element x belongs to {y | p y} if and only if p x holds.
Set.mem_empty_iff_false
No element belongs to the empty set: x ∈ ∅ is equivalent to False.
iff_false
A proposition p is equivalent to False if and only if ¬p holds.
SimpleGraph.fromEdgeSet_adj
In a graph built from an edge set s, vertices v and w are adjacent if and only if the unordered pair {v, w} is in s and v ≠ w.
Subsingleton.elim
In a subsingleton type (a type with at most one element), any two elements are equal (a = b).
Nat.sInf_empty
The infimum of the empty set of natural numbers is 0 (sInf ∅ = 0).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem not_op_1406_weakened_cycle_ramsey_number_ge_self : ¬ (∀ (t ℓ : ℕ) (ht : 1 ≤ t) (hℓ : 3 ≤ ℓ), ℓ ≤ weakened_cycle_ramsey_number t ℓ) := by  intro h  have h1 : 3 ≤ weakened_cycle_ramsey_number 1 3 := h 1 3 le_rfl (by norm_num)  have h0 : weakened_cycle_ramsey_number 1 3 = 0 := by    unfold weakened_cycle_ramsey_number    have hset : {n : ℕ | weakened_cycle_ramsey_property 1 3 n} = ∅ := by      ext n      simp only [Set.mem_setOf_eq, Set.mem_empty_iff_false, iff_false]      intro hp      obtain ⟨j, hom, hinj⟩ := hp (fun _ => (0 : Fin 1))      rw [show color_avoiding_subgraph (SimpleGraph.completeGraph (Fin n)) (fun _ => (0 : Fin 1)) j = ⊥ from by        ext a b        rw [color_avoiding_subgraph, SimpleGraph.fromEdgeSet_adj]        constructor        · rintro ⟨⟨_, hne⟩, _⟩          exact absurd (Subsingleton.elim _ j) hne        · intro hh          exact absurd hh (by simp)] at hom      have hadj := hom.map_adj (show (SimpleGraph.cycleGraph 3).Adj 0 1 by decide)      simp at hadj    rw [hset, Nat.sInf_empty]  omega
See it in the graphDiscuss this resultChallenge it