AFTD Auto-Formalizing Theoretical Domains

op223_first_replacement_spectral_lower

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    lines 17–21

    uses SimpleGraph.adjMatrix_apply, SimpleGraph.sup_adj, SimpleGraph.deleteEdges_adj, SimpleGraph.fromEdgeSet_adj, Sym2.eq

      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] <;> decide
  2. 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⁷).

    lines 26–29

      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]
  3. 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.

    lines 32–33

      change ENNReal.ofReal (209/100 : ℝ) < adjacency_spectral_radius example_witness_graph
      unfold adjacency_spectral_radius
  4. 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.

    lines 34–36

    uses op223_matrix_spectral_lower, Matrix.isHermitian_iff_isSymm.mpr, SimpleGraph.isSymm_adjMatrix, example_witness_hmat, example_witness_quad

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it