op_258_forces_mono_bound
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$.
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}$.
rcases hk with ⟨n₀, hn₀⟩ refine ⟨n₀, fun n hn c hc => hn₀ n hn c fun i => ?_⟩
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}$.
uses
le_transhave 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$.
- On line 8, the `gcongr` tactic handles the monotonicity of multiplication and automatically verifies that $\binom{n}{2} \ge 0$.
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.
/-- 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