AFTD Auto-Formalizing Theoretical Domains

op_258_forces_mono_clique

theoremverified

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

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.

  1. 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.

    lines 4–6

      obtain ⟨n₀, hn⟩ := hk
      refine ⟨n₀, ?_⟩
      intro n hn' c hc
  2. 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.

    lines 7–8

    uses Finset.exists_subset_card_eq

      obtain ⟨s, i, hcard, hmono⟩ := hn n hn' c hc
      obtain ⟨t, hts, htcard⟩ := Finset.exists_subset_card_eq (by omega : j ≤ s.card)
  3. 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.

    lines 9–14

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it