SignedGraph.SameDeck
def
Two signed graphs G1 and G2 on finite types V1 and V2 with decidable equality have the same switching deck if there exists an equivalence π : V1 ≃ V2 such that G1.switch v is isomorphic to G2.switch (π v) for all v.
Statement
def SignedGraph.SameDeck {V1 V2 : Type*} [DecidableEq V1] [DecidableEq V2] [Fintype V1] [Fintype V2] (G1 : SignedGraph V1) (G2 : SignedGraph V2) : Prop
- Defined in
- arXiv:2611.13901, Sec. 2.2
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 3
- SignedGraphA signed graph on vertex type V consists of an underlying simple graph and a signature assigning to each edge a value in {1, -1}.
- SignedGraph.IsIsomorphicTwo signed graphs G1 and G2 are isomorphic if there is an isomorphism f between their underlying simple graphs that preserves the signs of…
- SignedGraph.switchThe switching of a signed graph G at a vertex v is the signed graph with the same underlying graph where the sign of every edge incident…
- Used by 6
- signed_graph_reconstructible_balanced_mono_pair_fixedLet G be a connected balanced signed graph on at least seven vertices, with a specified balance partition. Suppose distinct vertices a and…
- signed_graph_reconstructible_balanced_mono_invariantA connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex…
- signed_graph_reconstructible_balanced_three_fixedEvery connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has…
- SignedGraph.IsReconstructibleA signed graph G on a finite type V with decidable equality is reconstructible from its switching deck if every signed graph G' on a…
- signed_graph_reconstructible_balanced_mixed_twin_pairLet G be a connected balanced signed graph on at least five vertices, with a specified balance partition. Suppose distinct vertices a and…
- SignedGraph.IsSwitchPartnerA vertex w distinct from v is a switch partner of v in G if switching G at v and then at w is not isomorphic to G but has the same…
Read back from the Lean
For finite types $V_1$ and $V_2$ equipped with decidable equality, and signed graphs $G_1$ on vertex type $V_1$ and $G_2$ on vertex type $V_2$, SignedGraph.SameDeck G1 G2 asserts that there exists a bijection $\pi : V_1 \simeq V_2$ such that for all vertices $v : V_1$, the signed graph $G_1.\text{switch}(v)$ is isomorphic (SignedGraph.IsIsomorphic) to $G_2.\text{switch}(\pi(v))$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Two signed graphs have the same switching deck if their vertex switchings are isomorphic via a bijection. -/ def SignedGraph.SameDeck {V1 V2 : Type*} [DecidableEq V1] [DecidableEq V2] [Fintype V1] [Fintype V2] (G1 : SignedGraph V1) (G2 : SignedGraph V2) : Prop := ∃ (π : V1 ≃ V2), ∀ v : V1, SignedGraph.IsIsomorphic (G1.switch v) (G2.switch (π v))