AFTD Auto-Formalizing Theoretical Domains

op_258_forces_two

theoremverified

For every decay profile a, a forces a monochromatic K_2.

Statement

theorem op_258_forces_two (a : ℕ+ → ℝ) : op_258_forces a 2
Source
step towards op_258_triangle_forcing_implies_decay_ramsey
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
  • op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
  • op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…
Used by 1
  • op_258_forces_of_capacity_lt_oneIf k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a…

The proof, explained

The theorem states that any decay profile a forces a monochromatic K_2. Choosing the threshold n₀ = 2, every complete graph K_n on n ≥ 2 vertices contains two distinct vertices, 0 and 1, which span an edge e. The two-vertex set {0, 1} and the color c(e) immediately provide a monochromatic K_2, as this single edge is the only edge between the two vertices, rendering the decay bound hypothesis unnecessary.

  1. To show that any decay profile a forces a monochromatic K_2, it suffices to show that every edge-colored complete graph on n ≥ 2 vertices contains a monochromatic K_2.

    We choose the threshold n₀ = 2. For an arbitrary n ≥ 2, an edge-coloring c of K_n, and assuming the bound hypothesis, we unfold the definition of having a monochromatic clique of size 2: we must find a 2-element vertex set s and a color i such that all edges between distinct vertices in s have color i.

    lines 3–5

      use 2
      intro n hn c hc
      unfold op_258_has_mono_clique
  2. The vertices v₀ = 0 and v₁ = 1 in Fin n are distinct and form an edge e in K_n.

    Since n ≥ 2, both 0 < n and 1 < n hold by arithmetic, yielding two well-defined vertices v₀ and v₁ in Fin n. They are distinct because equality in Fin n implies equality of the underlying numbers via `Fin.mk.inj`, which would mean 0 = 1. Since v₀ ≠ v₁, the unordered pair s(v₀, v₁) is an edge e of the complete graph K_n.

    lines 6–15

    uses Fin.mk.inj

      have h0 : 0 < n := by omega
      have h1 : 1 < n := by omega
      let v0 : Fin n := ⟨0, h0⟩
      let v1 : Fin n := ⟨1, h1⟩
      have hne : v0 ≠ v1 := by
        intro h
        have := Fin.mk.inj h
        omega
      have he : s(v0, v1) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by simp [hne]
      let e : (SimpleGraph.completeGraph (Fin n)).edgeSet := ⟨s(v0, v1), he⟩
  3. The candidate set {v₀, v₁} has cardinality 2, and we select it along with color c(e).

    We instantiate the existential witness with the vertex set s = {v₀, v₁} and the color i = c(e). Because v₀ ≠ v₁, the set has cardinality 2. It remains to verify that every edge spanned by this set has color c(e).

    lines 16–17

      use {v0, v1}, c e
      refine ⟨by simp [hne], ?_⟩
  4. Any two distinct vertices u, v ∈ {v₀, v₁} must be drawn from {v₀, v₁}, ruling out the case u = v = v₀.

    Let u, v ∈ {v₀, v₁} with u ≠ v. Applying `Finset.mem_insert` and `Finset.mem_singleton`, each of u and v must be either v₀ or v₁. Splitting into cases, the diagonal possibility u = v₀ and v = v₀ contradicts u ≠ v.

    lines 18–21

    uses Finset.mem_insert, Finset.mem_singleton

      intro u v hu hv huv
      simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv
      rcases hu with rfl | rfl <;> rcases hv with rfl | rfl
      · contradiction
  5. When u = v₀ and v = v₁, the edge has color c(e).

    The edge between v₀ and v₁ is definitionally identical to e as a subtype of unordered pairs via `Subtype.ext`. Rewriting with this equality shows that its color is c(e).

    lines 22–25

    uses Subtype.ext

      · have h_eq : (⟨s(v0, v1), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by
          apply Subtype.ext
          rfl
        rw [h_eq]
  6. When u = v₁ and v = v₀, the edge also has color c(e), and the diagonal case u = v = v₁ is contradictory.

    By symmetry of unordered pairs (`Sym2.eq_swap`), s(v₁, v₀) = s(v₀, v₁), so by `Subtype.ext` the edge s(v₁, v₀) is equal to e and has color c(e). Finally, the case u = v₁ and v = v₁ is ruled out directly by u ≠ v.

    lines 26–30

    uses Subtype.ext, Sym2.eq_swap

      · have h_eq : (⟨s(v1, v0), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by
          apply Subtype.ext
          exact Sym2.eq_swap
        rw [h_eq]
      · contradiction
Fin.mk.inj
If two elements of a finite type `Fin n` are equal, their underlying natural numbers are equal.
Finset.mem_insert
An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Finset.mem_singleton
An element belongs to the singleton `{a}` if and only if it equals `a`.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Sym2.eq_swap
The unordered pair `s(a, b)` is equal to `s(b, a)`.

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

/-- Sanity witness for the forcing predicate: every profile forces a monochromatic `K_2`, since two adjacent vertices always form one. The content of the target therefore starts at `k = 3`. -/theorem op_258_forces_two (a : ℕ+ → ℝ) : op_258_forces a 2 := by  use 2  intro n hn c hc  unfold op_258_has_mono_clique  have h0 : 0 < n := by omega  have h1 : 1 < n := by omega  let v0 : Fin n := ⟨0, h0⟩  let v1 : Fin n := ⟨1, h1⟩  have hne : v0 ≠ v1 := by    intro h    have := Fin.mk.inj h    omega  have he : s(v0, v1) ∈ (SimpleGraph.completeGraph (Fin n)).edgeSet := by simp [hne]  let e : (SimpleGraph.completeGraph (Fin n)).edgeSet := ⟨s(v0, v1), he⟩  use {v0, v1}, c e  refine ⟨by simp [hne], ?_⟩  intro u v hu hv huv  simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv  rcases hu with rfl | rfl <;> rcases hv with rfl | rfl  · contradiction  · have h_eq : (⟨s(v0, v1), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by      apply Subtype.ext      rfl    rw [h_eq]  · have h_eq : (⟨s(v1, v0), by simp [huv]⟩ : (SimpleGraph.completeGraph (Fin n)).edgeSet) = e := by      apply Subtype.ext      exact Sym2.eq_swap    rw [h_eq]  · contradiction
See it in the graphDiscuss this resultChallenge it