SignedGraph.IsBalancedPartition
A pair of disjoint finsets A and B partitioning the vertex set Finset.univ of a signed graph G is a balance partition if every edge whose endpoints both lie in A or both lie in B has sign 1, and every edge with one endpoint in A and one in B has sign -1.
Statement
def SignedGraph.IsBalancedPartition {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (A B : Finset V) : Prop
- Defined in
- arXiv:2611.13901, Sec. 2.1 and Sec. 4.1
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- 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}.
- Used by 5
- 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_balanced_partition_unique_connectedAny two balance partitions of the same connected signed graph agree up to exchanging their two parts.
- 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…
- 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…
Read back from the Lean
Given a finite type $V$ with decidable equality, a signed graph $G$ on $V$ (a simple graph with an edge-weight function into $\{-1, 1\}$), and two finite subsets $A, B \subseteq V$, SignedGraph.IsBalancedPartition G A B asserts that:
1. $A$ and $B$ partition the vertex set $V$, meaning $A \cup B = V$ and $A \cap B = \emptyset$ (Disjoint A B);
2. For every pair of vertices $u, v \in V$ adjacent in $G$,
- if both $u, v \in A$ or both $u, v \in B$, then the sign of the edge $\{u, v\}$ is $1$;
- if one of $u, v$ is in $A$ and the other is in $B$, then the sign of the edge $\{u, v\}$ is $-1$.
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
/-- A bipartition of vertices where internal edges are positive and cross edges are negative. -/ def SignedGraph.IsBalancedPartition {V : Type*} [DecidableEq V] [Fintype V] (G : SignedGraph V) (A B : Finset V) : Prop := (A ∪ B = Finset.univ) ∧ Disjoint A B ∧ (∀ (u v : V) (h : G.graph.Adj u v), ((u ∈ A ∧ v ∈ A) ∨ (u ∈ B ∧ v ∈ B) → G.sgn ⟨s(u, v), h⟩ = 1) ∧ ((u ∈ A ∧ v ∈ B) ∨ (u ∈ B ∧ v ∈ A) → G.sgn ⟨s(u, v), h⟩ = -1))