AFTD Auto-Formalizing Theoretical Domains

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

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