petrial_nullity_poly_iso
Isomorphic finite simple graphs have the same partial Petrial nullity generating polynomial.
Statement
theorem petrial_nullity_poly_iso {V W : Type*} [Fintype V] [Fintype W] [DecidableEq V] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : petrial_nullity_poly G = petrial_nullity_poly H
- Source
- Graph reindexing helper for the OP-1239 counterexample.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- petrial_nullity_polyThe nullity generating polynomial of a finite graph G on V: the sum over all vertex subsets F of w raised to the nullity of the partial…
- petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
- Used by 6
- petrial_nullity_poly_card_one_finsetFor every finite vertex set of cardinality one, the partial Petrial nullity polynomial of the induced graph is one plus X.
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
- petrial_nullity_poly_induce_induceThe nullity polynomial obtained by inducing on s and then on vertices in t equals the polynomial of the graph induced on the intersection…
- petrial_nullity_poly_leaf_finsetIf v is a leaf with neighbor u in the subgraph induced by the finite set s, its nullity polynomial is that after deleting v plus twice…
- petrial_nullity_poly_empty_finsetThe partial Petrial nullity polynomial of the graph induced on the empty finite vertex set is one.
- petrial_nullity_poly_disjoint_finset_unionIf disjoint finite vertex sets have no edges between them, the nullity polynomial on their union is the product of the nullity polynomials…
The proof, explained
The theorem is proved by showing that the sums defining the Petrial nullity polynomials of G and H match term by term under the bijection between vertex subsets induced by the graph isomorphism e : G ≃g H. For each subset F ⊆ V, simultaneous row and column reindexing by e transforms the Petrial matrix of G at F into the Petrial matrix of H at e(F). Because reindexing preserves matrix rank and isomorphic graphs have the same vertex count, the exponents |V| - rank(M_F) match for every subset, establishing equality of the polynomials.
To show the polynomials are equal, it suffices to show that the summand for each vertex subset F ⊆ V equals the summand for its image under e in W.
Unfolding the definition of the Petrial nullity polynomial expresses both sides as sums over all vertex subsets of X^(|V| - rank(M_F)) and X^(|W| - rank(M_F')), respectively. The graph isomorphism e : V ≃ W induces a bijection on finite subsets via Equiv.finsetCongr. Reindexing the sum on the right-hand side using Fintype.sum_equiv reduces the equality of the two sums to verifying that the corresponding terms match for an arbitrary subset F ⊆ V.
uses
Fintype.sum_equiv,Equiv.finsetCongrdsimp [petrial_nullity_poly] rw [Fintype.sum_equiv (Equiv.finsetCongr (e : V ≃ W))] intro F
The vertex sets V and W have the same cardinality: |V| = |W|.
Because e : V ≃ W is a bijection between the finite types V and W, their cardinalities are equal by Fintype.card_congr.
uses
Fintype.card_congrhave hcard : Fintype.card V = Fintype.card W := Fintype.card_congr (e : V ≃ W)The Petrial matrix of G at F, when reindexed by the vertex isomorphism e, equals the Petrial matrix of H at the image subset e(F).
Unfolding the definition of the Petrial matrix, each entry is the sum of an adjacency indicator and a diagonal indicator for membership in the subset. We test entrywise equality at indices i, j ∈ W: the (i, j) entry of the reindexed matrix corresponds to indices e⁻¹(i) and e⁻¹(j) in G. By e.map_adj_iff, e⁻¹(i) and e⁻¹(j) are adjacent in G if and only if i and j are adjacent in H, so the adjacency terms agree. By Finset.mem_map_equiv and injectivity of e⁻¹ (via EmbeddingLike.apply_eq_iff_eq), e⁻¹(i) ∈ F and e⁻¹(i) = e⁻¹(j) are equivalent to i ∈ e(F) and i = j, so the diagonal terms agree as well.
uses
Matrix.submatrix_apply,Matrix.add_apply,SimpleGraph.adjMatrix_apply,Matrix.diagonal_apply,Finset.mem_map_equiv,e.map_adj_iff,EmbeddingLike.apply_eq_iff_eqhave hmat : (Matrix.reindex (e : V ≃ W) (e : V ≃ W)) (petrial_matrix G F) = petrial_matrix H (F.map (e : V ≃ W).toEmbedding) := by dsimp [petrial_matrix] ext i j simp only [Matrix.submatrix_apply, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply] simp only [Finset.mem_map_equiv] have h_adj : G.Adj ((e : V ≃ W).symm i) ((e : V ≃ W).symm j) ↔ H.Adj i j := by rw [← e.map_adj_iff] simp simp only [h_adj] congr 1 simp only [EmbeddingLike.apply_eq_iff_eq]
The Petrial matrix of H at e(F) has the same rank as the Petrial matrix of G at F.
Using the previous identity, the Petrial matrix of H at e(F) is obtained from the Petrial matrix of G at F by simultaneous row and column reindexing via e. By Matrix.rank_reindex, reindexing rows and columns preserves matrix rank.
uses
Matrix.rank_reindexhave hrank : (petrial_matrix H (Finset.map (e : V ≃ W).toEmbedding F)).rank = (petrial_matrix G F).rank := by rw [← hmat, Matrix.rank_reindex]
The summand for F matches the summand for e(F), completing the proof.
Applying Equiv.finsetCongr_apply rewrites the subset bijection to the embedding map. Substituting |V| = |W| (from hcard) and the rank equality (from hrank) into the exponent X^(|V| - rank(M)) shows that the two terms are identical.
uses
Equiv.finsetCongr_applyrw [Equiv.finsetCongr_apply] rw [hcard, hrank]
EmbeddingLike.apply_eq_iff_eq- Applying an injective map to two elements yields equal results if and only if the two elements are equal.
Equiv.finsetCongr- An equivalence between two types induces a bijection between their types of finite subsets.
Equiv.finsetCongr_apply- Evaluating the subset equivalence induced by e on a finite set s produces the image of s under e viewed as an embedding.
Finset.mem_map_equiv- An element b belongs to the image of a finite set s under an equivalence f if and only if f⁻¹(b) belongs to s.
Fintype.card_congr- Equivalent finite types have the same cardinality.
Fintype.sum_equiv- A sum over a finite index type can be reindexed along an equivalence with another finite type, provided the terms match under the bijection.
Matrix.add_apply- The (i, j) entry of the sum of two matrices is the sum of their (i, j) entries.
Matrix.diagonal_apply- The (i, j) entry of a diagonal matrix is the diagonal element at i if i = j, and 0 otherwise.
Matrix.rank_reindex- Reindexing the rows and columns of a matrix by bijections preserves its rank.
Matrix.submatrix_apply- The (i, j) entry of a submatrix with row map r and column map c is the (r(i), c(j)) entry of the original matrix.
SimpleGraph.adjMatrix_apply- The (v, w) entry of the adjacency matrix of a graph is 1 if v and w are adjacent, and 0 otherwise.
e.map_adj_iff- A graph isomorphism preserves and reflects adjacency: two vertices in the domain are adjacent if and only if their images in the codomain are adjacent.
- On paper, vertex sets and subsets are identified directly across a graph isomorphism; in Lean, this requires converting the equivalence e to an embedding and invoking explicit reindexing and congruence lemmas (such as Matrix.reindex and Equiv.finsetCongr).
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.
theorem petrial_nullity_poly_iso {V W : Type*} [Fintype V] [Fintype W] [DecidableEq V] [DecidableEq W] (G : SimpleGraph V) (H : SimpleGraph W) [DecidableRel G.Adj] [DecidableRel H.Adj] (e : G ≃g H) : petrial_nullity_poly G = petrial_nullity_poly H := by dsimp [petrial_nullity_poly] rw [Fintype.sum_equiv (Equiv.finsetCongr (e : V ≃ W))] intro F have hcard : Fintype.card V = Fintype.card W := Fintype.card_congr (e : V ≃ W) have hmat : (Matrix.reindex (e : V ≃ W) (e : V ≃ W)) (petrial_matrix G F) = petrial_matrix H (F.map (e : V ≃ W).toEmbedding) := by dsimp [petrial_matrix] ext i j simp only [Matrix.submatrix_apply, Matrix.add_apply, SimpleGraph.adjMatrix_apply, Matrix.diagonal_apply] simp only [Finset.mem_map_equiv] have h_adj : G.Adj ((e : V ≃ W).symm i) ((e : V ≃ W).symm j) ↔ H.Adj i j := by rw [← e.map_adj_iff] simp simp only [h_adj] congr 1 simp only [EmbeddingLike.apply_eq_iff_eq] have hrank : (petrial_matrix H (Finset.map (e : V ≃ W).toEmbedding F)).rank = (petrial_matrix G F).rank := by rw [← hmat, Matrix.rank_reindex] rw [Equiv.finsetCongr_apply] rw [hcard, hrank]