not_op_1406_weakened_cycle_ramsey_number_ge_self
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.
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.
uses
le_rflintro h have h1 : 3 ≤ weakened_cycle_ramsey_number 1 3 := h 1 3 le_rfl (by norm_num)
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.
uses
Set.mem_setOf_eq,Set.mem_empty_iff_false,iff_falsehave 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))
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 ⊥.
uses
SimpleGraph.fromEdgeSet_adj,Subsingleton.elimrw [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
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} = ∅.
have hadj := hom.map_adj (show (SimpleGraph.cycleGraph 3).Adj 0 1 by decide) simp at hadj
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.
uses
Nat.sInf_emptyrw [hset, Nat.sInf_empty]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.
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).
- In standard mathematical usage, the infimum of an empty set of natural numbers is often considered undefined or ∞. In Lean, the complete lattice structure on ℕ defines `sInf ∅ = 0` by convention (`Nat.sInf_empty`). This formal convention is essential to the counterexample: because no n satisfies the weakened Ramsey property when t = 1, the Ramsey number evaluates to 0, which directly contradicts the claim ℓ ≤ weakened_cycle_ramsey_number t ℓ.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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