op223_local_principal_maxima_not_sufficient
theoremverified
There is a tree on exactly three vertices with an edge uv that can be replaced by a nonedge so that the result remains a tree and has adjacency spectral radius at least as large, and a positive eigenvector of its adjacency matrix such that u and v each uniquely maximize that eigenvector within their respective components after deleting the edge.
Statement
theorem op223_local_principal_maxima_not_sufficient : ∃ (T : SimpleGraph (Fin 3)) (u v : Fin 3) (r : ℝ) (p : Fin 3 → ℝ), T.IsTree ∧ T.Adj u v ∧ is_sustainable_edge T s(u,v) ∧ (∀ x, 0 < p x) ∧ (T.adjMatrix ℝ).mulVec p = r • p ∧ (∀ x, (T.deleteEdges {s(u,v)}).Reachable u x → x ≠ u → p x < p u) ∧ (∀ x, (T.deleteEdges {s(u,v)}).Reachable v x → x ≠ v → p x < p v)- Source
- arXiv:2610.17078 Open Problem 6.1; counterexample to an auxiliary eigenvector criterion
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- is_sustainable_edgeAn edge e in a tree T is sustainable if there exists a non-edge f such that T - e + f is a tree and the adjacency spectral radius of T - e…
- op223_nonsustainable_tree_fin_fourEvery non-sustainable tree on four vertices is isomorphic to the star graph K_{1,3}.
- adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - Arena.Reachable.transReachability is transitive.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open SimpleGraphopen scoped Classicalopen SimpleGraph Matrixopen scoped Classical/-- The three-vertex star with centre 0 and leaves 1, 2. -/def op223_lpm_T : SimpleGraph (Fin 3) := SimpleGraph.fromEdgeSet {s(0, 1), s(0, 2)}/-- The star `op223_lpm_T` with edge 01 replaced by the non-edge 12 (path 0-2-1). -/def op223_lpm_T' : SimpleGraph (Fin 3) := op223_lpm_T.deleteEdges {s(0, 1)} ⊔ SimpleGraph.fromEdgeSet {s(1, 2)}/-- Candidate positive eigenvector `[sqrt 2, 1, 1]`. -/noncomputable def op223_lpm_p : Fin 3 → ℝ := fun i => if i = 0 then Real.sqrt 2 else 1lemma op223_lpm_T_edgeSet : op223_lpm_T.edgeSet = (↑({s(0,1), s(0,2)} : Finset (Sym2 (Fin 3))) : Set (Sym2 (Fin 3))) := by ext e induction e using Sym2.ind with | h a b => fin_cases a <;> fin_cases b <;> simp [op223_lpm_T, Sym2.eq, Fin.ext_iff]lemma op223_lpm_T'_edgeSet : op223_lpm_T'.edgeSet = (↑({s(0,2), s(1,2)} : Finset (Sym2 (Fin 3))) : Set (Sym2 (Fin 3))) := by ext e induction e using Sym2.ind with | h a b => simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff, SimpleGraph.mem_edgeSet, op223_lpm_T', op223_lpm_T, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj] fin_cases a <;> fin_cases b <;> simp [Sym2.eq, Fin.ext_iff]lemma op223_lpm_T_isTree : op223_lpm_T.IsTree := by rw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩ · rw [SimpleGraph.connected_iff_exists_forall_reachable] refine ⟨0, ?_⟩ intro x; fin_cases x · exact SimpleGraph.Reachable.rfl · exact (by simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] : op223_lpm_T.Adj 0 1).reachable · exact (by simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] : op223_lpm_T.Adj 0 2).reachable · rw [op223_lpm_T_edgeSet, Nat.card_coe_set_eq, Set.ncard_coe_finset] norm_num [Sym2.eq, Fin.ext_iff]lemma op223_lpm_T'_isTree : op223_lpm_T'.IsTree := by rw [SimpleGraph.isTree_iff_connected_and_card] refine ⟨?_, ?_⟩ · rw [SimpleGraph.connected_iff_exists_forall_reachable] refine ⟨0, ?_⟩ intro x; fin_cases x · exact SimpleGraph.Reachable.rfl · exact (by simp [op223_lpm_T', op223_lpm_T, SimpleGraph.sup_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] : op223_lpm_T'.Adj 0 2).reachable.trans (by simp [op223_lpm_T', op223_lpm_T, SimpleGraph.sup_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] : op223_lpm_T'.Adj 2 1).reachable · exact (by simp [op223_lpm_T', op223_lpm_T, SimpleGraph.sup_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] : op223_lpm_T'.Adj 0 2).reachable · rw [op223_lpm_T'_edgeSet, Nat.card_coe_set_eq, Set.ncard_coe_finset] norm_num [Sym2.eq, Fin.ext_iff]/-- Reindexing a real square matrix by a permutation preserves the spectral radius. -/lemma op223_lpm_spectral_reindex {n m : Type*} [Fintype n] [DecidableEq n] [Fintype m] [DecidableEq m] (M : Matrix n n ℝ) (e : n ≃ m) : spectralRadius ℝ ((Matrix.reindex e e) M) = spectralRadius ℝ M := by have h := AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℝ ℝ e) M rw [Matrix.reindexAlgEquiv_apply] at h simp only [spectralRadius] rw [h]/-- The star and the three-vertex path are isomorphic (swap 0 and 2). -/noncomputable def op223_lpm_iso : op223_lpm_T ≃g op223_lpm_T' := RelIso.mk (Equiv.swap 0 2) (by intro a b fin_cases a <;> fin_cases b <;> simp only [op223_lpm_T', op223_lpm_T, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Equiv.swap_apply_def] all_goals simp [Sym2.eq, Fin.ext_iff])/-- The star and the path have the same adjacency spectral radius. -/lemma op223_lpm_radius_eq : adjacency_spectral_radius op223_lpm_T = adjacency_spectral_radius op223_lpm_T' := by have hmat := Iso.reindex_adjMatrix (α := ℝ) op223_lpm_iso have key : spectralRadius ℝ (op223_lpm_T'.adjMatrix ℝ) = spectralRadius ℝ (op223_lpm_T.adjMatrix ℝ) := by rw [← hmat] exact op223_lpm_spectral_reindex (op223_lpm_T.adjMatrix ℝ) (op223_lpm_iso : Fin 3 ≃ Fin 3) simp only [adjacency_spectral_radius] exact key.symmlemma op223_lpm_p_pos (x : Fin 3) : 0 < op223_lpm_p x := by fin_cases x · simp only [op223_lpm_p, Fin.isValue, Fin.reduceEq, if_true] exact Real.sqrt_pos.2 (by norm_num) · simp [op223_lpm_p] · simp [op223_lpm_p]lemma op223_lpm_p_eigen : (op223_lpm_T.adjMatrix ℝ).mulVec op223_lpm_p = Real.sqrt 2 • op223_lpm_p := by have hp0 : op223_lpm_p 0 = Real.sqrt 2 := by simp [op223_lpm_p] have hp1 : op223_lpm_p 1 = 1 := by simp [op223_lpm_p] have hp2 : op223_lpm_p 2 = 1 := by simp [op223_lpm_p] have h0 : op223_lpm_T.neighborFinset 0 = {1, 2} := by ext w; rw [SimpleGraph.mem_neighborFinset]; fin_cases w <;> simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] have h1 : op223_lpm_T.neighborFinset 1 = {0} := by ext w; rw [SimpleGraph.mem_neighborFinset]; fin_cases w <;> simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] have h2 : op223_lpm_T.neighborFinset 2 = {0} := by ext w; rw [SimpleGraph.mem_neighborFinset]; fin_cases w <;> simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] funext i fin_cases i · show (op223_lpm_T.adjMatrix ℝ *ᵥ op223_lpm_p) 0 = Real.sqrt 2 • op223_lpm_p 0 rw [SimpleGraph.adjMatrix_mulVec_apply, h0, Finset.sum_pair (by decide), hp1, hp2, hp0, smul_eq_mul] nlinarith [Real.sq_sqrt (show (0:ℝ) ≤ 2 by norm_num)] · show (op223_lpm_T.adjMatrix ℝ *ᵥ op223_lpm_p) 1 = Real.sqrt 2 • op223_lpm_p 1 rw [SimpleGraph.adjMatrix_mulVec_apply, h1, Finset.sum_singleton, hp0, hp1, smul_eq_mul] ring · show (op223_lpm_T.adjMatrix ℝ *ᵥ op223_lpm_p) 2 = Real.sqrt 2 • op223_lpm_p 2 rw [SimpleGraph.adjMatrix_mulVec_apply, h2, Finset.sum_singleton, hp0, hp2, smul_eq_mul] ringlemma op223_lpm_del_adj_right {a b : Fin 3} (h : (op223_lpm_T.deleteEdges {s(0,1)}).Adj a b) : b = 0 ∨ b = 2 := by fin_cases a <;> fin_cases b <;> simp_all [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff]lemma op223_lpm_del_adj_left {a b : Fin 3} (h : (op223_lpm_T.deleteEdges {s(0,1)}).Adj a b) : a = 0 ∨ a = 2 := by fin_cases a <;> fin_cases b <;> simp_all [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff]lemma op223_lpm_del_not_adj_one (b : Fin 3) : ¬ (op223_lpm_T.deleteEdges {s(0,1)}).Adj 1 b := by intro h rcases op223_lpm_del_adj_left h with h0 | h2 · exact absurd h0 (by decide) · exact absurd h2 (by decide)lemma op223_lpm_del_reach_zero (x : Fin 3) (h : (op223_lpm_T.deleteEdges {s(0,1)}).Reachable 0 x) : x = 0 ∨ x = 2 := by obtain ⟨w⟩ := h refine w.rec (motive := fun a b _ => (a = 0 ∨ a = 2) → (b = 0 ∨ b = 2)) ?_ ?_ (Or.inl rfl) · intro u hu; exact hu · intro u v w' hadj p ih hu exact ih (op223_lpm_del_adj_right hadj)lemma op223_lpm_del_reach_one (x : Fin 3) (h : (op223_lpm_T.deleteEdges {s(0,1)}).Reachable 1 x) : x = 1 := by obtain ⟨w⟩ := h refine w.rec (motive := fun a b _ => a = 1 → b = 1) ?_ ?_ rfl · intro u hu; exact hu · intro u v w' hadj p ih hu subst hu exact absurd hadj (op223_lpm_del_not_adj_one v)theorem op223_local_principal_maxima_not_sufficient : ∃ (T : SimpleGraph (Fin 3)) (u v : Fin 3) (r : ℝ) (p : Fin 3 → ℝ), T.IsTree ∧ T.Adj u v ∧ is_sustainable_edge T s(u,v) ∧ (∀ x, 0 < p x) ∧ (T.adjMatrix ℝ).mulVec p = r • p ∧ (∀ x, (T.deleteEdges {s(u,v)}).Reachable u x → x ≠ u → p x < p u) ∧ (∀ x, (T.deleteEdges {s(u,v)}).Reachable v x → x ≠ v → p x < p v) := by have hedge : (s(0,1) : Sym2 (Fin 3)) ∈ op223_lpm_T.edgeSet := by rw [SimpleGraph.mem_edgeSet] simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] have hf : (s(1,2) : Sym2 (Fin 3)) ∈ op223_lpm_Tᶜ.edgeSet := by rw [SimpleGraph.mem_edgeSet, SimpleGraph.compl_adj] exact ⟨by decide, by simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff]⟩ refine ⟨op223_lpm_T, 0, 1, Real.sqrt 2, op223_lpm_p, op223_lpm_T_isTree, ?_, ⟨hedge, s(1,2), hf, op223_lpm_T'_isTree, ?_⟩, op223_lpm_p_pos, op223_lpm_p_eigen, ?_, ?_⟩ · simp [op223_lpm_T, SimpleGraph.fromEdgeSet_adj, Sym2.eq, Fin.ext_iff] · change adjacency_spectral_radius op223_lpm_T ≤ adjacency_spectral_radius op223_lpm_T' exact le_of_eq op223_lpm_radius_eq · intro x hx hxne rcases op223_lpm_del_reach_zero x hx with h | h · exact absurd h hxne · subst h have h2 : op223_lpm_p 2 = 1 := by simp [op223_lpm_p] have h0 : op223_lpm_p 0 = Real.sqrt 2 := by simp [op223_lpm_p] rw [h2, h0] exact Real.one_lt_sqrt_two · intro x hx hxne exact absurd (op223_lpm_del_reach_one x hx) hxne