AFTD Auto-Formalizing Theoretical Domains

op_258_forces_mono_bound

theoremverified

If b ≤ a pointwise and a forces a monochromatic K_k, then b forces a monochromatic K_k.

Statement

theorem op_258_forces_mono_bound {a b : ℕ+ → ℝ} (hba : ∀ i, b i ≤ a i) {k : ℕ}
    (hk : op_258_forces a k) : op_258_forces b k
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_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_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…

The proof, explained

Suppose $a$ forces a monochromatic $K_k$ with threshold $n_0$. Since $b_i \le a_i$ pointwise, any edge coloring whose color classes are bounded by $b_i \binom{n}{2}$ is also bounded by $a_i \binom{n}{2}$. Therefore, the same threshold $n_0$ witnesses that $b$ forces a monochromatic $K_k$.

  1. Using the threshold $n_0$ given by the forcing property of $a$, the goal reduces to showing that every $b$-bounded coloring is also $a$-bounded.

    Unpacking the assumption that $a$ forces a monochromatic $K_k$ yields a threshold $n_0$ such that every $a$-bounded coloring of $K_n$ for $n \ge n_0$ contains a monochromatic $K_k$. With the same threshold $n_0$, for any $n \ge n_0$ and any edge coloring $c$ bounded by $b$, it suffices to show that $c$ is bounded by $a$, meaning that for each color $i$, the number of edges of color $i$ is at most $a_i \binom{n}{2}$.

    lines 4–5

      rcases hk with ⟨n₀, hn₀⟩
      refine ⟨n₀, fun n hn c hc => hn₀ n hn c fun i => ?_⟩
  2. For every color $i$, the number of edges with color $i$ is at most $a_i \binom{n}{2}$.

    Since $c$ is $b$-bounded, the number of edges of color $i$ is at most $b_i \binom{n}{2}$. Because $b_i \le a_i$ by assumption and $\binom{n}{2}$ is non-negative, multiplying by $\binom{n}{2}$ gives $b_i \binom{n}{2} \le a_i \binom{n}{2}$. Transitivity of inequality (`le_trans`) then establishes that the number of edges of color $i$ is at most $a_i \binom{n}{2}$.

    lines 6–10

    uses le_trans

      have hbc := hc i
      have h_le : b i * (n.choose 2 : ℝ) ≤ a i * (n.choose 2 : ℝ) := by
        gcongr
        exact hba i
      exact le_trans hbc h_le
le_trans
Inequality is transitive: if $x \le y$ and $y \le z$, then $x \le z$.

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

/-- Forcing is antitone in the decay profile: shrinking the bound only removes colourings, so it cannot destroy forcing. -/theorem op_258_forces_mono_bound {a b : ℕ+ → ℝ} (hba : ∀ i, b i ≤ a i) {k : ℕ}    (hk : op_258_forces a k) : op_258_forces b k := by  rcases hk with ⟨n₀, hn₀⟩  refine ⟨n₀, fun n hn c hc => hn₀ n hn c fun i => ?_⟩  have hbc := hc i  have h_le : b i * (n.choose 2 : ℝ) ≤ a i * (n.choose 2 : ℝ) := by    gcongr    exact hba i  exact le_trans hbc h_le
See it in the graphDiscuss this resultChallenge it