op_258_sum_ne_top_of_forces_three
If a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i in ENNReal is finite.
Statement
theorem op_258_sum_ne_top_of_forces_three (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a)
(h3 : op_258_forces a 3) : (∑' i : ℕ+, ENNReal.ofReal (a i)) ≠ ⊤- Source
- step towards op_258_forces_step
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_no_mono_triangle_of_layeringIf an edge colouring c of K_n is subordinate to a bipartite edge layering (so each colour lives in a layer whose endpoints have distinct…
- op_258_hypercube_bipartite_decompositionFor any l ≥ 1, the edge set of the complete graph on 2^l vertices can be partitioned into l bipartite layers (indexed by the first…
- op_258_exists_divergent_capacity_coveringIf a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise…
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The theorem is proved by contradiction: assuming that the infinite sum of the profile a diverges, we construct a profile-bounded edge coloring of a sufficiently large complete graph K_{2^l} that contains no monochromatic triangle, contradicting the forcing hypothesis. By a covering theorem for divergent profiles, K_{2^l} can be partitioned into l layers with disjoint color sets I_j whose capacities match the layer sizes. We decompose K_{2^l} into l bipartite layers using a hypercube decomposition and greedily color the edges within each layer to respect the capacities. Because each color is confined to a single bipartite layer, no monochromatic triangle can exist, completing the contradiction.
The greedy coloring theorem holds in the base case E = ∅.
We proceed by induction on the finite set E. When E is empty, assigning the constant color 1 to every element vacuously satisfies that all elements of E map to s, and every color fiber in E is empty with cardinality 0 ≤ cap(i).
uses
Finset.induction_onintro E induction E using Finset.induction_on with | empty => intro s cap h refine ⟨fun _ => 1, ?_, ?_⟩ · intro x hx; simp at hx · intro i; simp
By the induction hypothesis, there exists a valid coloring c of E respecting the capacities.
For the inductive step, consider an element a ∉ E and capacities cap with |E ∪ {a}| ≤ ∑_{i ∈ s} cap(i). Since |E ∪ {a}| = |E| + 1, we have |E| ≤ ∑_{i ∈ s} cap(i), so the induction hypothesis supplies a coloring c of E into s whose color fibers on E are bounded by cap.
uses
Finset.card_insert_of_notMem| insert a E ha ih => intro s cap h have hcard : (insert a E).card = E.card + 1 := Finset.card_insert_of_notMem ha have hE : E.card ≤ ∑ i ∈ s, cap i := by omega obtain ⟨c, hcs, hcf⟩ := ih s cap hEThere exists a color i₀ ∈ s whose fiber in E has cardinality strictly less than cap(i₀).
The cardinality of E decomposes as the sum of its fiber sizes over s. If every color i ∈ s were already saturated with fiber size at least cap(i), summing would yield ∑_{i ∈ s} cap(i) ≤ |E| < |E| + 1 ≤ ∑_{i ∈ s} cap(i), a contradiction. Hence some color i₀ ∈ s has slack: |c⁻¹(i₀) ∩ E| < cap(i₀).
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_le_sumhave hmaps : (E : Set X).MapsTo c (s : Set ℕ+) := fun x hx => hcs x hx have hfib := Finset.card_eq_sum_card_fiberwise hmaps have hslack : ∃ i ∈ s, (E.filter (fun x => c x = i)).card < cap i := by by_contra hcon simp only [not_exists, not_and, not_lt] at hcon have h1 : ∑ i ∈ s, cap i ≤ ∑ i ∈ s, (E.filter (fun x => c x = i)).card := Finset.sum_le_sum hcon omega obtain ⟨i₀, hi₀s, hi₀⟩ := hslack
The extended coloring c' colors a with i₀ and agrees with c on E.
We define c' by setting c'(a) = i₀ and c'(x) = c(x) for all x ≠ a. Because a ∉ E, c'(x) = c(x) for every x ∈ E.
uses
if_negset c' : X → ℕ+ := fun x => if x = a then i₀ else c x with hc' have hca : c' a = i₀ := by simp [hc'] have hon : ∀ x ∈ E, c' x = c x := by intro x hx have hxa : ¬ (x = a) := by rintro rfl; exact ha hx simp only [hc', if_neg hxa]
Every element of E ∪ {a} is mapped by c' into s.
Any element x ∈ E ∪ {a} either equals a (in which case c'(a) = i₀ ∈ s) or belongs to E (in which case c'(x) = c(x) ∈ s by the induction hypothesis).
uses
Finset.mem_insertrefine ⟨c', ?_, ?_⟩ · intro x hx rw [Finset.mem_insert] at hx rcases hx with hx | hx · rw [hx, hca]; exact hi₀s · rw [hon x hx]; exact hcs x hx
For every color i, the fiber of c' on E ∪ {a} has size at most cap(i).
We check the fiber size for each color i. If i = i₀, the fiber on E ∪ {a} is the fiber on E with a adjoined; its cardinality increases by 1 to |c⁻¹(i₀) ∩ E| + 1, which remains at most cap(i₀) because of the strict slack |c⁻¹(i₀) ∩ E| < cap(i₀). If i ≠ i₀, element a does not have color i, so the fiber is identical to the fiber on E, which is already bounded by cap(i).
uses
Finset.card_insert_of_notMem· intro i by_cases hii : i = i₀ · have hmem : (insert a E).filter (fun x => c' x = i) = insert a (E.filter (fun x => c x = i₀)) := by rw [hii] ext x simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hx, hcx⟩ rcases hx with hx | hx · exact Or.inl hx · exact Or.inr ⟨hx, hon x hx ▸ hcx⟩ · rintro (rfl | ⟨hx, hcx⟩) · exact ⟨Or.inl rfl, by simp [hc']⟩ · exact ⟨Or.inr hx, hon x hx ▸ hcx⟩ rw [hmem, Finset.card_insert_of_notMem (by simp [ha]), hii] omega · have hmem : (insert a E).filter (fun x => c' x = i) = E.filter (fun x => c x = i) := by ext x simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hx, hcx⟩ rcases hx with hx | hx · rw [hx, hca] at hcx exact absurd hcx (Ne.symm hii) · exact ⟨hx, hon x hx ▸ hcx⟩ · rintro ⟨hx, hcx⟩ exact ⟨Or.inr hx, (hon x hx).symm ▸ hcx⟩ rw [hmem] exact hcf i
The graph K_{2^l} admits a bipartite layering with edge counts bounded by layer capacities.
Suppose for contradiction that the infinite sum of the profile a diverges. Choosing the graph threshold n₀ from the forcing hypothesis, divergent capacity covering yields a dimension l ≥ 1 with 2^l ≥ n₀, pairwise disjoint color sets I_j for j < l, and integer capacities cap(i) ≤ a_i * (2^l choose 2) such that layer j has capacity sum at least 2^(2l - 2 - j). By hypercube bipartite decomposition, the edges of K_{2^l} decompose into l bipartite layers with layer j containing at most 2^(2l - 2 - j) edges.
uses
op_258_exists_divergent_capacity_covering,op_258_hypercube_bipartite_decompositionintro hsum obtain ⟨n₀, hn₀⟩ := h3 obtain ⟨l, hl, I, cap, h2l, hdisj, hcaple, hlayersum⟩ := op_258_exists_divergent_capacity_covering a hpos hanti hsum n₀ obtain ⟨layer, f, hbip, hlayercard⟩ := op_258_hypercube_bipartite_decomposition l hl
There is an edge coloring c of K_{2^l} assigning each edge e a color in I_{layer(e)}.
For each layer j < l, the number of edges in layer j is at most 2^(2l - 2 - j) ≤ ∑_{i ∈ I_j} cap(i). Applying the greedy coloring lemma to each layer produces an edge coloring cc(j, ·) of layer j using colors in I_j with fibers bounded by cap. We combine these into a global edge coloring c(e) = cc(layer(e), e), ensuring c(e) ∈ I_{layer(e)} for every edge e.
uses
op_258_sum_ne_top_of_forces_three_greedy_colouring,le_transhave hper : ∀ j : Fin l, ∃ c : ↥(SimpleGraph.completeGraph (Fin (2^l))).edgeSet → ℕ+, (∀ e ∈ Finset.univ.filter (fun e => layer e = j), c e ∈ I j) ∧ ∀ i, ((Finset.univ.filter (fun e => layer e = j)).filter (fun e => c e = i)).card ≤ cap i := by intro j exact op_258_sum_ne_top_of_forces_three_greedy_colouring _ (I j) cap (le_trans (hlayercard j) (hlayersum j)) choose cc hccmem hccfiber using hper let c : ↥(SimpleGraph.completeGraph (Fin (2^l))).edgeSet → ℕ+ := fun e => cc (layer e) e have hcmem : ∀ e, c e ∈ I (layer e) := by intro e exact hccmem (layer e) e (by simp)
Each color belongs to at most one layer, and unused colors have empty fibers.
Because the sets I_j are pairwise disjoint, no color can belong to two distinct sets I_j and I_{j'}. Consequently, any color i not in ⋃_j I_j never appears on any edge, so its fiber is empty.
uses
Finset.filter_false_of_memhave huniq : ∀ (i : ℕ+) (j j' : Fin l), i ∈ I j → i ∈ I j' → j = j' := by intro i j j' hj hj' by_contra hne exact absurd hj' (Finset.disjoint_left.mp (hdisj j j' hne) hj) have hemp : ∀ i : ℕ+, ¬ (∃ j : Fin l, i ∈ I j) → Finset.univ.filter (fun e => c e = i) = ∅ := by intro i hi apply Finset.filter_false_of_mem intro e _ he exact hi ⟨layer e, he ▸ hcmem e⟩
For every color i, the total number of edges of color i is at most cap(i).
If i belongs to I_j, uniqueness of the layer implies that all edges of color i must reside in layer j. Thus the global fiber of i equals its fiber in layer j, which is bounded by cap(i). If i belongs to no I_j, its fiber is empty and has size 0 ≤ cap(i).
have hcf : ∀ i : ℕ+, (Finset.univ.filter (fun e => c e = i)).card ≤ cap i := by intro i by_cases hi : ∃ j : Fin l, i ∈ I j · obtain ⟨j, hij⟩ := hi have hEq : Finset.univ.filter (fun e => c e = i) = (Finset.univ.filter (fun e => layer e = j)).filter (fun e => cc j e = i) := by ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro hci have h2 : layer e = j := huniq i (layer e) j (hci ▸ hcmem e) hij refine ⟨h2, ?_⟩ have h3 : cc j e = cc (layer e) e := by rw [h2] exact h3.trans hci · rintro ⟨h2, hci⟩ have h3 : cc j e = cc (layer e) e := by rw [h2] exact h3.symm.trans hci rw [hEq] exact hccfiber j i · rw [hemp i hi] simp
The layer of an edge is uniquely determined by its color.
We define col_layer(i) to send each color i ∈ I_j to the unique layer j containing it. Since each edge e has c(e) ∈ I_{layer(e)}, we obtain col_layer(c(e)) = layer(e) for all edges e.
uses
dif_poslet col_layer : ℕ+ → Fin l := fun i => if h : ∃ j : Fin l, i ∈ I j then h.choose else ⟨0, hl⟩ have hcol : ∀ e, col_layer (c e) = layer e := by intro e have hex : ∃ j : Fin l, c e ∈ I j := ⟨layer e, hcmem e⟩ simp only [col_layer, dif_pos hex] exact huniq (c e) hex.choose (layer e) hex.choose_spec (hcmem e)
The coloring c satisfies the profile bound for a on K_{2^l}.
For each color i ∈ I_j, the number of edges colored i is at most cap(i) ≤ a_i * (2^l choose 2). For any color i outside all I_j, the fiber is empty with cardinality 0 ≤ a_i * (2^l choose 2) since a_i > 0. Hence c is a profile-bounded coloring.
uses
le_trans,mul_nonneg,le_of_lthave hbound : op_258_bounded a (2^l) c := by intro i have h1 : ({e | c e = i} : Finset _).card ≤ cap i := hcf i by_cases hi : ∃ j : Fin l, i ∈ I j · obtain ⟨j, hij⟩ := hi have h2 : (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ) := hcaple j i hij have h3 : (({e | c e = i} : Finset _).card : ℝ) ≤ (cap i : ℝ) := by exact_mod_cast h1 exact le_trans h3 h2 · have h0 : ({e | c e = i} : Finset _) = ∅ := hemp i hi rw [h0] simp only [Finset.card_empty, Nat.cast_zero] exact mul_nonneg (le_of_lt (hpos i)) (by positivity)
A contradiction is reached between the forcing hypothesis and the bipartite layering.
Since 2^l ≥ n₀ and c is profile-bounded, the forcing hypothesis guarantees that c contains a monochromatic triangle K_3. However, every monochromatic subgraph of color i is entirely contained in the layer col_layer(i), which is bipartite and therefore contains no odd cycles. By op_258_no_mono_triangle_of_layering, c cannot contain a monochromatic triangle, yielding a contradiction.
uses
op_258_no_mono_triangle_of_layeringexact op_258_no_mono_triangle_of_layering (2^l) l layer f hbip c col_layer hcol (hn₀ (2^l) h2l c hbound)
Finset.induction_on- Principle of induction on finite sets: to prove a property holds for all finite sets, it suffices to prove it for the empty set and show that it is preserved under inserting an element not already present.
Finset.card_insert_of_notMem- Inserting an element into a finite set that does not already contain it increases the cardinality of the set by 1.
Finset.card_eq_sum_card_fiberwise- For a map f from a finite set s into a finite set t, the cardinality of s is the sum of the cardinalities of the fibers f⁻¹(b) ∩ s over all b ∈ t.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set s, then the sum of f over s is at most the sum of g over s.
if_neg- An if-then-else expression evaluates to the 'else' branch when the condition is false.
Finset.mem_insert- An element x belongs to {b} ∪ s if and only if x = b or x ∈ s.
op_258_exists_divergent_capacity_covering- For any positive antitone profile a whose infinite sum diverges and any threshold n₀, there exists an integer l ≥ 1 with 2^l ≥ n₀, pairwise disjoint sets of colors I_j for j < l, and integer capacities cap(i) ≤ a_i * (2^l choose 2) such that each layer j has total capacity at least 2^(2l - 2 - j).
op_258_hypercube_bipartite_decomposition- For l ≥ 1, the edge set of the complete graph K_{2^l} can be decomposed into l bipartite layers such that layer j contains at most 2^(2l - 2 - j) edges.
op_258_sum_ne_top_of_forces_three_greedy_colouring- Any finite set E with |E| ≤ ∑_{i ∈ s} cap(i) admits a coloring c : E → s such that each color i appears at most cap(i) times on E.
le_trans- Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Finset.filter_false_of_mem- Filtering a finite set by a predicate that is satisfied by none of its elements yields the empty set.
dif_pos- A dependent if-then-else expression evaluates to its 'then' branch when the condition holds.
mul_nonneg- The product of two non-negative real numbers is non-negative.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
op_258_no_mono_triangle_of_layering- If the complete graph K_n is partitioned into bipartite layers and an edge coloring c assigns each color exclusively to edges within a single layer, then c contains no monochromatic triangle K_3.
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.
lemma op_258_sum_ne_top_of_forces_three_greedy_colouring {X : Type*} [DecidableEq X] : ∀ (E : Finset X) (s : Finset ℕ+) (cap : ℕ+ → ℕ), E.card ≤ ∑ i ∈ s, cap i → ∃ c : X → ℕ+, (∀ e ∈ E, c e ∈ s) ∧ ∀ i, (E.filter (fun e => c e = i)).card ≤ cap i := by intro E induction E using Finset.induction_on with | empty => intro s cap h refine ⟨fun _ => 1, ?_, ?_⟩ · intro x hx; simp at hx · intro i; simp | insert a E ha ih => intro s cap h have hcard : (insert a E).card = E.card + 1 := Finset.card_insert_of_notMem ha have hE : E.card ≤ ∑ i ∈ s, cap i := by omega obtain ⟨c, hcs, hcf⟩ := ih s cap hE have hmaps : (E : Set X).MapsTo c (s : Set ℕ+) := fun x hx => hcs x hx have hfib := Finset.card_eq_sum_card_fiberwise hmaps have hslack : ∃ i ∈ s, (E.filter (fun x => c x = i)).card < cap i := by by_contra hcon simp only [not_exists, not_and, not_lt] at hcon have h1 : ∑ i ∈ s, cap i ≤ ∑ i ∈ s, (E.filter (fun x => c x = i)).card := Finset.sum_le_sum hcon omega obtain ⟨i₀, hi₀s, hi₀⟩ := hslack set c' : X → ℕ+ := fun x => if x = a then i₀ else c x with hc' have hca : c' a = i₀ := by simp [hc'] have hon : ∀ x ∈ E, c' x = c x := by intro x hx have hxa : ¬ (x = a) := by rintro rfl; exact ha hx simp only [hc', if_neg hxa] refine ⟨c', ?_, ?_⟩ · intro x hx rw [Finset.mem_insert] at hx rcases hx with hx | hx · rw [hx, hca]; exact hi₀s · rw [hon x hx]; exact hcs x hx · intro i by_cases hii : i = i₀ · have hmem : (insert a E).filter (fun x => c' x = i) = insert a (E.filter (fun x => c x = i₀)) := by rw [hii] ext x simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hx, hcx⟩ rcases hx with hx | hx · exact Or.inl hx · exact Or.inr ⟨hx, hon x hx ▸ hcx⟩ · rintro (rfl | ⟨hx, hcx⟩) · exact ⟨Or.inl rfl, by simp [hc']⟩ · exact ⟨Or.inr hx, hon x hx ▸ hcx⟩ rw [hmem, Finset.card_insert_of_notMem (by simp [ha]), hii] omega · have hmem : (insert a E).filter (fun x => c' x = i) = E.filter (fun x => c x = i) := by ext x simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨hx, hcx⟩ rcases hx with hx | hx · rw [hx, hca] at hcx exact absurd hcx (Ne.symm hii) · exact ⟨hx, hon x hx ▸ hcx⟩ · rintro ⟨hx, hcx⟩ exact ⟨Or.inr hx, (hon x hx).symm ▸ hcx⟩ rw [hmem] exact hcf i/-- Any positive antitone profile that forces a monochromatic triangle K_3 has finite ENNReal sum (Theorem 1.3 of Di Braccio et al.). -/theorem op_258_sum_ne_top_of_forces_three (a : ℕ+ → ℝ) (hpos : ∀ i, 0 < a i) (hanti : Antitone a) (h3 : op_258_forces a 3) : (∑' i : ℕ+, ENNReal.ofReal (a i)) ≠ ⊤ := by intro hsum obtain ⟨n₀, hn₀⟩ := h3 obtain ⟨l, hl, I, cap, h2l, hdisj, hcaple, hlayersum⟩ := op_258_exists_divergent_capacity_covering a hpos hanti hsum n₀ obtain ⟨layer, f, hbip, hlayercard⟩ := op_258_hypercube_bipartite_decomposition l hl have hper : ∀ j : Fin l, ∃ c : ↥(SimpleGraph.completeGraph (Fin (2^l))).edgeSet → ℕ+, (∀ e ∈ Finset.univ.filter (fun e => layer e = j), c e ∈ I j) ∧ ∀ i, ((Finset.univ.filter (fun e => layer e = j)).filter (fun e => c e = i)).card ≤ cap i := by intro j exact op_258_sum_ne_top_of_forces_three_greedy_colouring _ (I j) cap (le_trans (hlayercard j) (hlayersum j)) choose cc hccmem hccfiber using hper let c : ↥(SimpleGraph.completeGraph (Fin (2^l))).edgeSet → ℕ+ := fun e => cc (layer e) e have hcmem : ∀ e, c e ∈ I (layer e) := by intro e exact hccmem (layer e) e (by simp) have huniq : ∀ (i : ℕ+) (j j' : Fin l), i ∈ I j → i ∈ I j' → j = j' := by intro i j j' hj hj' by_contra hne exact absurd hj' (Finset.disjoint_left.mp (hdisj j j' hne) hj) have hemp : ∀ i : ℕ+, ¬ (∃ j : Fin l, i ∈ I j) → Finset.univ.filter (fun e => c e = i) = ∅ := by intro i hi apply Finset.filter_false_of_mem intro e _ he exact hi ⟨layer e, he ▸ hcmem e⟩ have hcf : ∀ i : ℕ+, (Finset.univ.filter (fun e => c e = i)).card ≤ cap i := by intro i by_cases hi : ∃ j : Fin l, i ∈ I j · obtain ⟨j, hij⟩ := hi have hEq : Finset.univ.filter (fun e => c e = i) = (Finset.univ.filter (fun e => layer e = j)).filter (fun e => cc j e = i) := by ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro hci have h2 : layer e = j := huniq i (layer e) j (hci ▸ hcmem e) hij refine ⟨h2, ?_⟩ have h3 : cc j e = cc (layer e) e := by rw [h2] exact h3.trans hci · rintro ⟨h2, hci⟩ have h3 : cc j e = cc (layer e) e := by rw [h2] exact h3.symm.trans hci rw [hEq] exact hccfiber j i · rw [hemp i hi] simp let col_layer : ℕ+ → Fin l := fun i => if h : ∃ j : Fin l, i ∈ I j then h.choose else ⟨0, hl⟩ have hcol : ∀ e, col_layer (c e) = layer e := by intro e have hex : ∃ j : Fin l, c e ∈ I j := ⟨layer e, hcmem e⟩ simp only [col_layer, dif_pos hex] exact huniq (c e) hex.choose (layer e) hex.choose_spec (hcmem e) have hbound : op_258_bounded a (2^l) c := by intro i have h1 : ({e | c e = i} : Finset _).card ≤ cap i := hcf i by_cases hi : ∃ j : Fin l, i ∈ I j · obtain ⟨j, hij⟩ := hi have h2 : (cap i : ℝ) ≤ a i * ((2^l).choose 2 : ℝ) := hcaple j i hij have h3 : (({e | c e = i} : Finset _).card : ℝ) ≤ (cap i : ℝ) := by exact_mod_cast h1 exact le_trans h3 h2 · have h0 : ({e | c e = i} : Finset _) = ∅ := hemp i hi rw [h0] simp only [Finset.card_empty, Nat.cast_zero] exact mul_nonneg (le_of_lt (hpos i)) (by positivity) exact op_258_no_mono_triangle_of_layering (2^l) l layer f hbip c col_layer hcol (hn₀ (2^l) h2l c hbound)