op_258_forces_mono_clique
If a forces a monochromatic K_k, then a forces a monochromatic K_j for every j ≤ k.
Statement
theorem op_258_forces_mono_clique (a : ℕ+ → ℝ) {j k : ℕ} (hjk : j ≤ k) (hk : op_258_forces a k) :
op_258_forces a j- Source
- step towards op_258_triangle_forcing_implies_decay_ramsey
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
- Used by 1
- op_258_forces_of_forces_smul_blowupFor γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.
The proof, explained
To show that forcing a monochromatic K_k implies forcing a monochromatic K_j for any j ≤ k, we reuse the vertex threshold n₀ given by the hypothesis for k. For any graph on n ≥ n₀ vertices with a bounded coloring, there is a monochromatic clique of size k in some color i. Choosing any j-element subset of this clique immediately yields a monochromatic K_j of the same color.
Fix the threshold n₀ and assume an arbitrary graph size n ≥ n₀ with a bounded coloring c.
By the definition of forcing a monochromatic K_k, there exists an integer n₀ such that every suitably bounded coloring of K_n for n ≥ n₀ contains a monochromatic K_k. We adopt this same n₀ as the threshold for j, and let n ≥ n₀ along with an a-bounded edge coloring c be given.
obtain ⟨n₀, hn⟩ := hk refine ⟨n₀, ?_⟩ intro n hn' c hc
Obtain a monochromatic clique s of size k, and extract a subset t ⊆ s of size j.
Applying the forcing hypothesis for k to n and c gives a monochromatic clique s of size k in some color i. Since j ≤ k = |s| (justified by linear arithmetic), Finset.exists_subset_card_eq provides a subset t ⊆ s of cardinality exactly j.
uses
Finset.exists_subset_card_eqobtain ⟨s, i, hcard, hmono⟩ := hn n hn' c hc obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq (by omega : j ≤ s.card)
The subset t is a monochromatic clique of size j.
We provide t as the vertex set and i as the color. Its cardinality is j by construction. For any two distinct vertices u, v ∈ t, the inclusion t ⊆ s implies that both u and v belong to s. Since all pairs in s have color i, the edge between u and v also has color i.
refine ⟨t, i, htcard, ?_⟩ intro u v hu hv huv have hu' : u ∈ s := hts hu have hv' : v ∈ s := hts hv have := hmono hu' hv' huv convert this
Finset.exists_subset_card_eq- A finite set of cardinality at least n contains a subset of cardinality n.
- Line 14 uses `convert` instead of `exact` because the subtype proofs that the pair `{u, v}` is an edge in the complete graph differ syntactically between the goal and the hypothesis, though they are definitionally equal by proof irrelevance.
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 hierarchy is downward closed in the clique size: a monochromatic `K_k` contains a monochromatic `K_j` for `j ≤ k`. -/theorem op_258_forces_mono_clique (a : ℕ+ → ℝ) {j k : ℕ} (hjk : j ≤ k) (hk : op_258_forces a k) : op_258_forces a j := by obtain ⟨n₀, hn⟩ := hk refine ⟨n₀, ?_⟩ intro n hn' c hc obtain ⟨s, i, hcard, hmono⟩ := hn n hn' c hc obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq (by omega : j ≤ s.card) refine ⟨t, i, htcard, ?_⟩ intro u v hu hv huv have hu' : u ∈ s := hts hu have hv' : v ∈ s := hts hv have := hmono hu' hv' huv convert this