AFTD Auto-Formalizing Theoretical Domains

simple_graph_edit_cost_permutation_decomposition_le_two_mul

theoremverified

For any simple graphs $G$ and $H$ on $n$ vertices and any doubly stochastic matrix $Q$ with a convex decomposition into permutation matrices $\sum_{i \in \iota} w_i P_{\pi_i}$, the weighted edit cost between the adjacency matrices satisfies $\sum_{i \in \iota} w_i \mathcal{C}_{\mathsf{ed}}(\pi_i) \le 2 \mathcal{C}_{\mathsf{ed}}(Q)$.

Statement

theorem simple_graph_edit_cost_permutation_decomposition_le_two_mul
    {n : ℕ} {ι : Type*} [Fintype ι]
    (Q : Matrix (Fin n) (Fin n) ℝ) (hQ_ds : is_doubly_stochastic Q)
    (w : ι → ℝ) (hw_nonneg : ∀ i, 0 ≤ w i) (hw_sum : ∑ i, w i = 1)
    (π : ι → Equiv.Perm (Fin n))
    (hQ : ∑ i, w i • (π i).permMatrix ℝ = Q)
    (G H : SimpleGraph (Fin n)) [DecidableRel G.Adj] [DecidableRel H.Adj] :
    ∑ i, w i * perm_edit_cost (G.adjMatrix ℝ) (H.adjMatrix ℝ) (π i) ≤
      2 * graph_edit_cost (G.adjMatrix ℝ) (H.adjMatrix ℝ) Q
Source
arXiv:2611.05048 Theorem 6
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • graph_edit_cost_permutation_decomposition_le_two_mulLet $Q$ be an $n \times n$ doubly stochastic matrix with a convex decomposition $Q = \sum_{i \in \iota} w_i P_{\pi_i}$, where $w_i \ge 0$,…
  • perm_edit_costThe edit cost $\mathcal{C}_{\mathsf{ed}}(\pi)$ of a permutation $\pi$ between two $n \times n$ matrices $A$ and $B$ is the sum over all…
  • graph_edit_costThe edit cost $\mathcal{C}_{\mathsf{ed}}(Q)$ of a fractional alignment matrix $Q$ between two $n \times n$ matrices $A$ and $B$ is the sum…
  • is_doubly_stochasticA real matrix Q on a finite set V is doubly stochastic if all entries are nonnegative and all row and column sums equal 1.

Read back from the Lean

For any natural number $n$, finite type $\iota$, matrix $Q \in \mathbb{R}^{n \times n}$, weights $w : \iota \to \mathbb{R}$, permutations $\pi : \iota \to S_n$, and simple graphs $G, H$ on vertex set $\mathrm{Fin}(n)$ (with decidable adjacency): If: 1. $Q$ is doubly stochastic (all entries are non-negative, and every row and column sums to 1), 2. each weight $w_i \ge 0$, 3. the weights sum to 1 ($\sum_{i \in \iota} w_i = 1$), 4. $Q$ is expressed as the convex combination of the permutation matrices of $\pi_i$ with weights $w_i$, i.e., $\sum_{i \in \iota} w_i \cdot P_{\pi_i} = Q$, Then the weighted sum of the permutation edit costs between the adjacency matrices of $G$ and $H$ under $\pi_i$, $$\sum_{i \in \iota} w_i \cdot \mathrm{perm\_edit\_cost}(A_G, A_H, \pi_i),$$ is less than or equal to twice the graph edit cost with matrix $Q$, $$2 \cdot \mathrm{graph\_edit\_cost}(A_G, A_H, Q),$$ where $A_G$ and $A_H$ are the adjacency matrices of $G$ and $H$ over $\mathbb{R}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem specializes a general factor-2 upper bound for {0, 1}-matrices to the adjacency matrices of simple graphs. The proof invokes graph_edit_cost_permutation_decomposition_le_two_mul, which reduces the problem to showing that every entry of both adjacency matrices is either 0 or 1. It then verifies this binary-entry property for G and H by unfolding the definition of adjacency matrix and splitting on edge existence.

  1. The inequality reduces to showing that all entries of the adjacency matrices of G and H are in {0, 1}.

    We apply the general theorem graph_edit_cost_permutation_decomposition_le_two_mul, which establishes the factor-2 edit cost bound for any pair of matrices with entries in {0, 1}. All hypotheses on the doubly stochastic matrix Q and its convex decomposition into permutations match directly, leaving two subgoals: proving that every entry of the adjacency matrix of G is 0 or 1, and likewise for H.

    line 11

    uses graph_edit_cost_permutation_decomposition_le_two_mul

      apply graph_edit_cost_permutation_decomposition_le_two_mul Q hQ_ds w hw_nonneg hw_sum π hQ
  2. Every entry of the adjacency matrix of G is either 0 or 1.

    For arbitrary vertices i and j, unfolding the definition of the adjacency matrix shows that the entry is 1 if G has an edge between i and j, and 0 otherwise. Splitting on whether the edge exists reduces the goal to the tautologies 1 = 0 ∨ 1 = 1 and 0 = 0 ∨ 0 = 1, both of which simplify immediately to true.

    lines 12–14

    uses SimpleGraph.adjMatrix, Matrix.of_apply

      · intro i j
        simp only [SimpleGraph.adjMatrix, Matrix.of_apply]
        split_ifs <;> simp
  3. Every entry of the adjacency matrix of H is either 0 or 1.

    The same argument applies to graph H: unfolding its adjacency matrix and splitting on whether i and j are adjacent in H yields the same trivial disjunctions.

    lines 15–17

    uses SimpleGraph.adjMatrix, Matrix.of_apply

      · intro i j
        simp only [SimpleGraph.adjMatrix, Matrix.of_apply]
        split_ifs <;> simp
graph_edit_cost_permutation_decomposition_le_two_mul
For any matrices A and B with entries in {0, 1}, and any doubly stochastic matrix Q decomposed as a convex combination of permutation matrices ∑ᵢ wᵢ P_{πᵢ}, the weighted edit cost satisfies ∑ᵢ wᵢ 𝒞_{ed}(πᵢ) ≤ 2 𝒞_{ed}(Q).
SimpleGraph.adjMatrix
The adjacency matrix of a simple graph G, whose (i, j)-th entry is 1 if i and j are adjacent, and 0 otherwise.
Matrix.of_apply
Evaluating a matrix constructed from a function f at row i and column j gives f(i, j).

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

/-- The factor-2 upper bound specialized to the adjacency matrices of simple graphs. -/theorem simple_graph_edit_cost_permutation_decomposition_le_two_mul    {n : ℕ} {ι : Type*} [Fintype ι]    (Q : Matrix (Fin n) (Fin n) ℝ) (hQ_ds : is_doubly_stochastic Q)    (w : ι → ℝ) (hw_nonneg : ∀ i, 0 ≤ w i) (hw_sum : ∑ i, w i = 1)    (π : ι → Equiv.Perm (Fin n))    (hQ : ∑ i, w i • (π i).permMatrix ℝ = Q)    (G H : SimpleGraph (Fin n)) [DecidableRel G.Adj] [DecidableRel H.Adj] :    ∑ i, w i * perm_edit_cost (G.adjMatrix ℝ) (H.adjMatrix ℝ) (π i) ≤      2 * graph_edit_cost (G.adjMatrix ℝ) (H.adjMatrix ℝ) Q := by  apply graph_edit_cost_permutation_decomposition_le_two_mul Q hQ_ds w hw_nonneg hw_sum π hQ  · intro i j    simp only [SimpleGraph.adjMatrix, Matrix.of_apply]    split_ifs <;> simp  · intro i j    simp only [SimpleGraph.adjMatrix, Matrix.of_apply]    split_ifs <;> simp
See it in the graphDiscuss this resultChallenge it