op_258_forces_iff
For every decay profile a and k, "a forces a monochromatic K_k" holds if and only if the raw statement "for all sufficiently large n, every a-bounded colouring of K_n has a k-element vertex set all of whose edges share a colour" holds.
Statement
theorem op_258_forces_iff (a : ℕ+ → ℝ) (k : ℕ) : op_258_forces a k ↔ ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i
- 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…
The proof, explained
The predicate `op_258_forces a k` asserts that for all sufficiently large n, every a-bounded colouring of K_n contains a monochromatic k-clique. By unfolding the definitions of `op_258_forces`, `op_258_bounded`, and `op_258_has_mono_clique`, the left-hand side reduces definitionally to the expanded statement on the right-hand side. Within the statement, an inline simplification using `SimpleGraph.completeGraph_eq_top` confirms that any pair of distinct vertices in K_n spans an edge. The bi-implication is therefore an identity and is closed by reflexivity (`Iff.rfl`).
The forcing predicate `op_258_forces a k` is definitionally equivalent to the explicit quantifier formula on the right-hand side.
The forcing property `op_258_forces a k` is defined directly as the conjunction of the boundedness condition `op_258_bounded` and the monochromatic clique condition `op_258_has_mono_clique`. Expanding these definitions yields the exact formula on the right-hand side. Within that formula, the edge membership for two distinct vertices `u ≠ v` in the complete graph is settled by simplifying with `SimpleGraph.completeGraph_eq_top` and the inequality hypothesis `h : u ≠ v`. Because both sides of the bi-implication are definitionally identical, the equivalence holds by reflexivity (`Iff.rfl`).
uses
SimpleGraph.completeGraph_eq_top,Iff.rflc ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := Iff.rfl
SimpleGraph.completeGraph_eq_top- The complete graph on a vertex set V is the top element ⊤ of the graph lattice, meaning every pair of distinct vertices forms an edge.
Iff.rfl- Logical equivalence is reflexive: any proposition P is equivalent to itself (P ↔ P).
- The theorem statement itself contains an inline tactic proof (`by simp [...]`) to establish that any distinct pair of vertices forms an edge in the complete graph, while the theorem itself is proven definitionally by `Iff.rfl`.
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.
/-- The forcing predicate unfolds definitionally to the raw statement used in the target, so the two are interchangeable. -/theorem op_258_forces_iff (a : ℕ+ → ℝ) (k : ℕ) : op_258_forces a k ↔ ∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+, (∀ i : ℕ+, ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card ≤ a i * (n.choose 2 : ℝ)) → ∃ (s : Finset (Fin n)) (i : ℕ+), s.card = k ∧ ∀ ⦃u v : Fin n⦄, u ∈ s → v ∈ s → (h : u ≠ v) → c ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, h]⟩ = i := Iff.rfl