simple_graph_edit_cost_permutation_decomposition_le_two_mul
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.
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.
uses
graph_edit_cost_permutation_decomposition_le_two_mulapply graph_edit_cost_permutation_decomposition_le_two_mul Q hQ_ds w hw_nonneg hw_sum π hQEvery 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.
uses
SimpleGraph.adjMatrix,Matrix.of_apply· intro i j simp only [SimpleGraph.adjMatrix, Matrix.of_apply] split_ifs <;> simp
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.
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
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.
/-- 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