GF(4)-Representations of Bias Matroids of Signed Graphs: The 3-Connected Case
Steven R. Pagano
University of Kentucky
Abstract
Given a signed graph S, we may determine the collection of all
fields over which its bias matroid G(S) is representable merely by
determining whether G(S) is binary and whether it
is GF(4)-representable. We characterize those signed graphs whose respective
bias matroids are binary, and we characterize those signed graphs whose bias
matroids are GF(4)-representable.
1. Introduction and definitions
A signed graph is a graph with each of its edges labeled “plus” or
“minus”. The sign of a path or a circle (i.e., a simple closed path) in a
signed graph S is the product of the signs
of its edges. The bias matroid G(S) of a signed graph S is the matroid on E(S) whose circuits are the edge sets of S that induce the following types of
subgraphs:
i)
A
positive circle.
ii)
A
pair of negative circles that meet in exactly one vertex (a “tight handcuff”).
iii)
A
pair of vertex-disjoint negative circles C1 and C2 and a
minimal non-self-intersecting path P such that C1ÈPÈC2 is connected
(a “loose handcuff”).
Zaslavsky (in [10]) gives a
construction of a matrix that represents G(S) over all fields of
characteristic other than two (in particular, over GF(3)). Because G(S) is ternary, we may apply Whittle’s theorems
on ternary matroids [9, Theorems 1.1 and 1.4] and Tutte’s theorem on regular
matroids (in [7], [8]) to obtain the following known result:
·
If
G(S) is binary, then it is representable over
all fields.
·
If
G(S) is GF(4)-representable but not binary, then
it is representable over all fields except GF(2).
·
If
G(S) is not GF(4)-representable, then it is
representable over all fields except those of characteristic two.
The entirety of this paper is
devoted to proving the following two theorems.
Theorem
1.1. Let S be a 3-connected, simply
signed, loopless signed graph which satisfies the non-barrier condition, for
which G(S) is nonbinary. Then G(S) is GF(4)-representable iff S is a mesa graph with three
negative digons.
Theorem
1.2. Let S be a 3-connected, simply
signed, loopless signed graph which satisfies the barrier condition, for which
G(S) is nonbinary. Then G(S) is GF(4)-representable iff S is plate-cylindrical.
We shall make use of the following
theorem, my main result in [3].
Theorem 1.3. Let S be a connected signed
graph, and let 
be the signed graph
obtained by contracting all balanced blocks of S. Then G(S) is binary iff 
contains no pair of
vertex-disjoint negative circles.
We assume the notation and
terminology given in Oxley [2] as well as the definitions that follow. In
particular, the symbol / denotes contraction, and \ denotes deletion.
A loop is an edge whose endpoints are identical, and a link is an edge with distinct
endpoints. A path is said to be trivial
if it contains no edges. A graph is said to be empty if it contains no vertices or edges. A pair of paths is said
to be internally vertex-disjoint if
no vertex internal to one meets the other.
Let X, Y and Z be three subgraphs of
a connected graph G for which none of the three
is properly contained within another, and for which XÇZ is edge-empty. We say that Y is a barrier between X and Z if all paths
connecting X and Z meet a vertex of Y. The relation ~ on E(G)\E(Y) given by
e~f Û Y is not a barrier between e and f
is
an equivalence relation. The subgraphs of G induced by the equivalence
classes of ~ are called the bridges
of Y. A bridge B of Y is trivial if
V(B) Í V(Y) and nontrivial otherwise.
We define a vertex cutset of a graph G to be a subset W of V(G) that has two or more nontrivial bridges. A cut-vertex
is a vertex v for which {v} is a vertex cutset (as opposed to a cutpoint, which is a vertex with two or
more bridges). For a positive integer k,
a graph is said to be k-connected if it has no vertex cutsets
of size smaller than k. A block of G is a maximal subgraph of G containing no cutpoints. All blocks are
2-connected, and any loop of G is a block in and of
itself.
Let X Í E(G) and W Í V(G), both nonempty. By G:X we mean the subgraph of G consisting of X and the endpoints of the
edges in X. By G:W we mean the subgraph of G consisting of W and those edges for which
both endpoints are contained in W.
Given a graph G, by ±G we mean the signed graph obtained by
replacing each edge of G by a pair of signed edges,
one positive and one negative. By –G we mean the signed graph
obtained from G by replacing each edge of G with a negative edge. By kG we mean the graph obtained
from G by replacing each edge of G with k
copies of that edge. By S(k) we mean the signed graph obtained from S by adding a negative loop
at each of k distinct vertices, and
by S° we mean the signed graph
obtained by adding a negative loop to every vertex of S. By Cn
we mean the circle with n vertices,
and by Kn we mean the
complete graph on n vertices. A theta graph is any subdivision of 3K2.
To switch a vertex of S is to change the sign of
all links (i.e., non-loop edges) incident to that vertex. Switching a vertex of
S does not change G(S).
A signed graph S is balanced
if it contains no negative circles, and unbalanced
otherwise. Given a balanced subgraph Y of S, we may switch some subset of V(S) so that all edges of Y are positive (Zaslavsky, [11]). Furthermore,
if S is balanced, then G(S) is the cycle matroid of the underlying
graph of S, and hence is regular.
Zaslavsky also showed [10] that r(S) = |V(S)| – b(S), where b(S) is the number of balanced components of S.
Contracting an edge of S is done as follows:
·
If
the edge is a positive loop, delete it.
·
If
the edge is a positive link, then delete it and identify its endpoints.
·
If
the edge is a negative link, switch one of its endpoints, then delete the edge
and identify its endpoints.
·
If
the edge is a negative loop, delete it and its incident vertex v; all other edges of S incident to v now become negative loops at their other endpoint.
Note
that contraction is only defined up to switching.
A signed graph Y obtained from S by a possibly empty
sequence of contractions of edges and deletions of edges and/or vertices of S is called a minor of S. Zaslavsky [10] showed that
G(S\e)
= G(S)\e
and G(S/e) = G(S)/e. Given a matroid M, if there is a signed graph S for which M = G(S), then we say that M is signed-graphic.
Finally, we make heavy use of
various consequences of Menger’s vertex theorem (see, among others, [1]).
Primary among these are the following two theorems:
Theorem
1.4 (Menger). For k ³ 1, a graph G is k-connected iff given any
two nonadjacent vertices {v, w} of G there are at least k internally vertex-disjoint paths in G that connect v to w.
Theorem
1.5 (Dirac). If G is a k-connected graph, then whenever V1
and V2 are disjoint sets of k
vertices, there exist k pairwise
vertex-disjoint paths of which each have one endpoint in V1 and the
other endpoint in V2.
An easy
corollary to Theorem 1.5 is the following, which we use most of all:
Corollary 1.6. If G is a k-connected graph and C1 and
C2 are two vertex-disjoint circles in S with at least k vertices in each, then there exist k pairwise vertex-disjoint paths of
which each is internally vertex disjoint from C1ÈC2
and has one endpoint in C1 and the other in C2.
As stated previously, this paper is
dedicated to proving Theorems 1.1 and 1.2. To that end, we first give obtain a
forbidden minor lemma (Section 2), then obtain our primary tool for showing
when G(S) does have a representation
matrix over GF(4) (Section 3). Following that, we discuss mesa graphs and
obtain a proof of Theorem 1.1 (Sections 4 and 5), after which we discuss
cylindrical and plate-cylindrical signed graphs (Section 6) and obtain a proof
to Theorem 1.2 (Sections 7-12).
2. The Forbidden Minors
Theorem
2.1. (Pagano, [4]) G(S) is GF(4) representable iff S does not have any of {±C3(1), ±C4\e, –K4(1)}
as a minor.
¨
Actually, in this paper, we only
need the fact that G(±C3(1)) = F7–
and G(±C4\e) = (F7–)*,
so both ±C3(1) and ±C4\e are forbidden minors for GF(4). In fact, we only need consider
the following two collections of signed graphs, each of which contain forbidden
minors for GF(4).
An evil graph is ±C4\e or any signed graph that contracts to it.
Let S1 be obtained by taking +K4 and adding a negative edge
in parallel to each of two nonadjacent edges. If we contract one of the
negative edges of S1, we obtain ±C3(1), so S1 is a forbidden minor for
GF(4). We call S1, or any signed graph that
contracts to it, a bad drum. The
following lemma is immediate from these definitions. It is our primary tool in
showing when G(S) is not GF(4)
representable.
Lemma
2.2. If S has an evil subgraph or a
bad drum minor, then G(S) is not GF(4)
representable.
¨
3. Negative Orientations and the w-representation
We now obtain our primary tool in
showing when G(S) is GF(4) representable.
A negative orientation of S is obtained by giving a
direction to each negative edge of S, so that each negative edge
has an initial vertex and a terminal vertex. Given a negative orientation of S, we construct a matrix called an w-matrix of S as follows:
Let Jw be an |V(S)|´|E(S)| matrix over GF(4), with rows indexed by V(S) = {v1,
v2, …, vn} and columns indexed by E(S) = {e1,
e2, … , em}. The entries in the row
corresponding to ek are
all zero, except possibly for those entries in rows corresponding to endpoints
of ek:
·
If
ek = vivi is a loop, then Jw(i, k) is 0 if ek
is positive, and 1 if ek
is negative.
·
If
ek = vivj is a positive link, then Jw(i, k) = Jw(j, k) = 1.
·
If
ek is a negative link
oriented from vi to vj, then Jw(i, k) = 1 and Jw(j, k) = w.
An w-representation
of S
is an w-matrix of S that represents G(S) over GF(4).
We
now show that certain negative orientations of S give rise to w-representations of G(S). Given a circle C in S, we choose an arbitrary orientation for C. The negative edges of C are said to be clockwise if their orientation agrees with that of C, and counterclockwise otherwise. (An edge may be clockwise in one circle
and counterclockwise in another.) We say that C is compatible provided
that C is positive iff the number of clockwise and
counterclockwise edges of C are
congruent modulo 3. If every circle of C is compatible, then the negative
orientation is called a compatible
negative orientation (CNO).
Lemma
3.1. If S has a compatible negative
orientation, then the w-representation
corresponding to that negative orientation represents G(S) over GF(4).
Proof.
We need only check that circuits of G(S) map to dependent sets of
vectors in Jw, and that bases of G(S) map to independent sets. To this end, we
need only prove that a circle maps to a collection of linearly dependent
vectors iff it is positive.
Up to row and column permutation,
and after deleting all zero rows, the submatrix M of Jw corresponding to a circle
in S is
, where 
.
Now, 
, which is zero iff
the number of ai’s which
are w are congruent modulo 3 to the number of ai’s which are w+1 iff
the number of clockwise and counterclockwise edges of the circle are congruent
modulo 3.
¨
We will often show that G(S) is representable over GF(4) by showing that
S has a compatible negative orientation.
4. Mesa Graphs
We now introduce our first class of
GF(4)-representable signed graphs, and prove one half of Theorem 1.1.
Let S be a connected signed graph
with a partition {A, B} of V(S) such that
i)
S:A and S:B are both balanced and connected, and
ii)
the
collection of edges of S with one vertex in A and
the other in B induces a subgraph S0 of S made up entirely of vertex-disjoint negative
digons.
We call S a mesa
graph. Of particular import is the mesa graph Pr3 wherein S:A and S:B are both positive
triangles and S0 has three digons.
The following lemma proves one
direction of Theorem 1.1.
Lemma
4.1. Let S be a mesa graph with three
or fewer negative digons. Then S switches to have a
compatible negative orientation, hence G(S) is GF(4) representable.
Proof.
We switch S so that S:A and S:B are all positive. We then
orient the three negative edges of S from A towards B. This
yields a compatible negative orientation for S.
¨
5. The Non-Barrier Case
For this section, we assume that S is 3-connected, loopless, and simply signed.
Lemma
5.1. If S has a Pr3 minor,
then G(S) is GF(4)-representable iff S is a mesa graph with three
negative digons.
Proof. Let