op223_first_replacement_spectral_lower
Replacing edge 0-1 with 4-2 in the example tree yields a graph whose spectral radius is greater than 209/100.
Statement
theorem op223_first_replacement_spectral_lower : ENNReal.ofReal (209 / 100 : ℝ) < adjacency_spectral_radius (op223_example_graph.deleteEdges {s(0, 1)} ⊔ SimpleGraph.fromEdgeSet {s(4, 2)})- Source
- arXiv:2610.17078 Open Problem 6.1; experiments 22883 and 22914
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- op223_example_graphThe eight-vertex tree with edges 01, 04, 07, 12, 23, 45 and 46.
- 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.
- op223_matrix_spectral_lowerA negative quadratic form for tI minus a Hermitian real matrix certifies that its real spectral radius exceeds t.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- op223_example_graph_edge_01_sustainableEdge 0-1 in op223_example_graph is sustainable.
The proof, explained
The proof shows that replacing edge {0, 1} with edge {4, 2} in an 8-vertex tree produces a graph whose adjacency spectral radius is strictly greater than 209/100 = 2.09. By the Rayleigh quotient variational characterization for real symmetric matrices, it suffices to find a test vector v satisfying vᵀ(2.09 I - A)v < 0, where A is the adjacency matrix. The argument verifies entry-by-entry that the modified graph's adjacency matrix equals an explicit 8×8 matrix, evaluates the quadratic form with the integer test vector v = (3505, 2115, 4700, 2115, 6210, 2795, 2795, 1578) to confirm it is negative, and concludes via the spectral lower bound theorem.
The adjacency matrix of the modified graph matches the explicit 8×8 matrix example_witness_matrix. automation
Two matrices are equal if their corresponding entries agree. We rewrite the adjacency matrix entry as an indicator of graph adjacency and exhaustively check all 64 pairs of indices (i, j) on the 8 vertices. For each pair, the edge membership in the modified graph—formed by deleting edge {0, 1} and adding edge {4, 2}—is decided by arithmetic and boolean evaluation.
uses
SimpleGraph.adjMatrix_apply,SimpleGraph.sup_adj,SimpleGraph.deleteEdges_adj,SimpleGraph.fromEdgeSet_adj,Sym2.eqext i j simp only [SimpleGraph.adjMatrix_apply] fin_cases i <;> fin_cases j <;> norm_num [example_witness_matrix, example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decide
The quadratic form vᵀ((209/100)I - A)v is strictly negative for the witness vector v and the explicit 8×8 matrix A. automation
Expanding the dot product, matrix-vector product, scalar multiplication, and subtraction over the 8 coordinates produces a concrete rational expression. Direct arithmetic evaluation verifies that (209/100)‖v‖² - vᵀAv is negative (evaluating to approximately -1.3158 × 10⁷).
simp only [star_trivial, dotProduct, Matrix.mulVec, vecHead, vecTail, Fin.sum_univ_succ, Matrix.sub_apply, Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply] norm_num [example_witness_vector, example_witness_matrix, Matrix.cons_val_zero, Matrix.cons_val_succ, Matrix.sub_apply, Matrix.smul_apply, Matrix.one_apply, Fin.succ]
The target inequality reduces to showing that the spectral radius of the adjacency matrix of example_witness_graph is strictly greater than 209/100.
The graph described in the theorem statement is by definition example_witness_graph. We rewrite the statement using this definition and unfold the definition of the graph's adjacency spectral radius to the spectral radius of its real adjacency matrix.
change ENNReal.ofReal (209/100 : ℝ) < adjacency_spectral_radius example_witness_graph unfold adjacency_spectral_radius
The spectral radius of the adjacency matrix exceeds 209/100 by the Rayleigh quotient lower bound with test vector v.
We invoke op223_matrix_spectral_lower: the graph's adjacency matrix is symmetric, hence Hermitian, and the parameter 209/100 is non-negative. It therefore suffices to exhibit a vector v with vᵀ((209/100)I - A)v < 0. We rewrite the adjacency matrix with the explicit matrix verified in example_witness_hmat, and the remaining inequality is precisely example_witness_quad.
uses
op223_matrix_spectral_lower,Matrix.isHermitian_iff_isSymm.mpr,SimpleGraph.isSymm_adjMatrix,example_witness_hmat,example_witness_quadapply op223_matrix_spectral_lower _ (Matrix.isHermitian_iff_isSymm.mpr (SimpleGraph.isSymm_adjMatrix _)) _ (by norm_num) example_witness_vector rw [example_witness_hmat] exact example_witness_quad
SimpleGraph.adjMatrix_apply- The (i, j)-entry of a simple graph's adjacency matrix is 1 if vertices i and j are adjacent, and 0 otherwise.
SimpleGraph.sup_adj- Two vertices are adjacent in the union of two graphs if and only if they are adjacent in at least one of the graphs.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in a graph after deleting a set of edges if and only if they were adjacent originally and the edge between them is not in the deleted set.
SimpleGraph.fromEdgeSet_adj- Two distinct vertices are adjacent in the graph generated from an edge set if and only if the unordered pair between them belongs to that set.
Sym2.eq- Two unordered pairs are equal if and only if their endpoints match in the same or reverse order.
op223_matrix_spectral_lower- For a real Hermitian matrix A and any non-negative scalar t, if there exists a vector v such that vᵀ(tI - A)v < 0, then the spectral radius of A is strictly greater than t.
Matrix.isHermitian_iff_isSymm.mpr- A real matrix is Hermitian if it is symmetric.
SimpleGraph.isSymm_adjMatrix- The adjacency matrix of any simple graph is symmetric.
example_witness_hmat- The adjacency matrix of example_witness_graph equals the explicit 8×8 matrix example_witness_matrix.
example_witness_quad- For the witness vector v and witness matrix A, the quadratic form vᵀ((209/100)I - A)v is strictly negative.
- The entry-by-entry verification of the 8x8 adjacency matrix and the rational evaluation of the 8-dimensional quadratic form are carried out entirely by automation (fin_cases, norm_num, decide).
- In line 34, the precondition 0 ≤ 209/100 required by op223_matrix_spectral_lower is discharged inline by `by norm_num`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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 Matrixopen scoped ENNRealopen scoped Classicalnoncomputable def example_witness_graph : SimpleGraph (Fin 8) := op223_example_graph.deleteEdges {s(0, 1)} ⊔ SimpleGraph.fromEdgeSet {s(4, 2)}noncomputable def example_witness_vector : Fin 8 → ℝ := ![3505, 2115, 4700, 2115, 6210, 2795, 2795, 1578]noncomputable def example_witness_matrix : Matrix (Fin 8) (Fin 8) ℝ := ![![0, 0, 0, 0, 1, 0, 0, 1], ![0, 0, 1, 0, 0, 0, 0, 0], ![0, 1, 0, 1, 1, 0, 0, 0], ![0, 0, 1, 0, 0, 0, 0, 0], ![1, 0, 1, 0, 0, 1, 1, 0], ![0, 0, 0, 0, 1, 0, 0, 0], ![0, 0, 0, 0, 1, 0, 0, 0], ![1, 0, 0, 0, 0, 0, 0, 0]]set_option maxHeartbeats 3000000 inlemma example_witness_hmat : example_witness_graph.adjMatrix ℝ = example_witness_matrix := by ext i j simp only [SimpleGraph.adjMatrix_apply] fin_cases i <;> fin_cases j <;> norm_num [example_witness_matrix, example_witness_graph, op223_example_graph, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq] <;> decideset_option maxHeartbeats 3000000 inlemma example_witness_quad : star example_witness_vector ⬝ᵥ (((algebraMap ℝ (Matrix (Fin 8) (Fin 8) ℝ)) (209/100 : ℝ) - example_witness_matrix) *ᵥ example_witness_vector) < 0 := by simp only [star_trivial, dotProduct, Matrix.mulVec, vecHead, vecTail, Fin.sum_univ_succ, Matrix.sub_apply, Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply] norm_num [example_witness_vector, example_witness_matrix, Matrix.cons_val_zero, Matrix.cons_val_succ, Matrix.sub_apply, Matrix.smul_apply, Matrix.one_apply, Fin.succ]theorem op223_first_replacement_spectral_lower : ENNReal.ofReal (209 / 100 : ℝ) < adjacency_spectral_radius (op223_example_graph.deleteEdges {s(0, 1)} ⊔ SimpleGraph.fromEdgeSet {s(4, 2)}) := by change ENNReal.ofReal (209/100 : ℝ) < adjacency_spectral_radius example_witness_graph unfold adjacency_spectral_radius apply op223_matrix_spectral_lower _ (Matrix.isHermitian_iff_isSymm.mpr (SimpleGraph.isSymm_adjMatrix _)) _ (by norm_num) example_witness_vector rw [example_witness_hmat] exact example_witness_quad