Vector Representability of Bias Matroids of Signed Graphs

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 quaternary (i.e., GF(4)-representable). We give a decomposition theorem for determining when a signed graph is binary or quaternary.

1. Introduction and preliminary results.

            The entirety of this paper is given to proving the following result. All definitions that appear therein shall follow.

 

Theorem 1.1. Let S be a connected signed graph. Let  be the signed graph obtains by contracting all balanced blocks of S.

1)      S is binary (and hence regular) iff  contains no pair of vertex-disjoint negative circles.

2)      S is quaternary (and hence representable over all fields except possibly GF(2)) iff it is binary or it is nonbinary but each nonloop block of  can be obtained from a negative digon by repeated application of a (possibly empty) sequence of the following transformations:

a)      Duplication of edges.

b)      Reversing a 2-plating or 3-plating.

c)      For a negative digon D on vertices v and w, pasting one of the following subgraphs onto the graph at v and w, possibly deleting one or both edges of D:

i)                    Pr3, where {v, w} support a negative digon D’ in Pr3; we may delete any edges of D’;

ii)                   A plate-cylindrical signed graph, where v and w are on the same end-circle;

iii)                 A binary signed graph S0 with a balancing vertex, for which S0 has a compatible negative orientation (CNO) that is perfect from v to w.

3)      If S is neither binary nor quaternary, then S is representable over all fields of characteristic other than two, but no other fields.

 

            I proved part 1) of Theorem 1.1 as [2, Theorem 1], and I proved part 2) for 3-connected S as [3, Theorems 1.1 and 1.2], so it only remains to prove part 2) for S not 3-connected.

 

            A signed graph S is a graph, each of whose edges are labeled with a + or a -. A circle (polygon, cycle) or a path in S is positive or negative according to the product of the signs of its edges. The bias matroid G(S) of the signed graph S is the matroid on E(S) whose circuits determine the following types of subgraph:

·        A positive circle,

·        A pair of negative circles sharing a common vertex,

·        A pair of vertex-disjoint negative circles and a minimal path of any sign which connects them.

            We shall say that S is binary (resp., quaternary) if G(S) is GF(2)-representable (resp., GF(4)-representable). Zaslavsky showed that G(S) is always ternary and rational [7, Theorem 8B.1], so by theorems of Whittle [6, Theorems 1.1 and 1.4] and Tutte [4] [5] we obtain the following:

 

Theorem 1.2. If S is binary, then G(S) is regular. If S is quaternary but not binary, then G(S) is representable over all fields except GF(2). Otherwise, G(S) is representable only over those fields with characteristic other than two.

 

            So we may determine the complete collection of fields over which G(S) is representable by determining whether S is binary or quaternary.

            We assume the notation and terminology given in Oxley [1] as well as the definitions that follow.

            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.

            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, by Pn we mean a path with n edges, 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, [8]). 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 (cite) 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 [19, Theorem 2.5] showed that G(S\e) = G(S)\e and G(S/e) = G(S)/e.

            A balancing vertex of an unbalanced signed graph S is a vertex v of S such that S\v is balanced.

            We will make use of various consequences of Menger’s vertex theorem (see, for example, [10, Section I.2]. Primary among these are the following two theorems:

 

Theorem 1.3 (Menger). For k ³ 1, a graph G is k-connected iff given any two vertices {v, w} of G there are at least k internally vertex-disjoint paths in G that connect v to w.

 

Theorem 1.4 (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.

 

            The signed graph Pr3 consists of an all-positive triangle on {v1, v2, v3}, an all-positive triangle on {w1, w2, w3}, and negative digons on {v1, w1}, {v2, w2}, and {v3, w3}.

            A cylindrical signed graph S is one that may be embedded (without crossings) on a cylinder such that each positive circle of S is topologically contractible on the cylinder and each negative circle is not. Equivalently, a switching of S may be embedded on a cylinder such that a red line may be drawn down the length of the cylinder so that the red line crosses each negative edge of S once and meets no positive edge of S. Any maximal collection of vertex-disjointed negative circles can be labeled C1, C2, …, Cn such that for distinct i, j, and k, Cj is a barrier between Ci and Ck iff i < j < k or i > j > k. In this scenario C1 and Cn are called the end circles of the embedding.

            Suppose S has a vertex cutset W = {v, w}, and that W has a nontrivial balanced union of bridges X. Every path in X from v to w must be the same sign s. By 2-plating we mean replacing X by the edge vw with sign s, then deleting any duplicate edges. We define a 3-plating similarly, with cutset W’ = {u, v, w}, and a balanced union of bridges X of W’ being replaced by a positive triangle on W’, each edge signed as above. A complete plating of S is a signed graph S’ obtained from S by a possibly empty sequence of 2- and 3-platings, for which no further plating may be performed on S’. The operations of plating and switching commute [3, Lemma 6.3].

            By a compatible negative orientation (CNO) of S we mean an orientation of only the negative edges of S such that a circle C in S is positive iff the number of clockwise and counterclockwise edges of C are congruent modulo 3. A path taken from a to b in S has net forward number equal to its number of forward edges minus its number of backward edges. A CNO is said to be perfect with respect to a and b if either

i)                    all paths in S from a to b have net forward number 0 or 1, or

ii)                   all paths in S from a to b have net forward number 0 or –1.

            I proved the following lemmas in [3]:

 

Lemma 1.5[3, Lemma 3.1]. If S has a CNO, then S is quaternary.

 

Lemma 1.6[3, Lemma 6.5]. If a plating (or a complete plating) of S has a CNO, then so does S.

 

Lemma 1.7[3, Lemmas 4.1 and 6.4]. Pr3 has a CNO that is perfect with respect to any pair of its vertices. (This CNO orients each negative edge –viwi towards vi.) A cylindrical signed graph has a CNO (we orient each negative edge so that it crosses the red line in the same direction).

 

            By Lemmas 1.6 and 1.7, any signed graph S which has a complete plating that is cylindrical we call plate-cylindrical. In [3] I also proved the following:

 

Theorem 1.8[3, Theorems 1.1 and 1.2]. Suppose S is completely plated and 3-connected, with at least two vertex-disjoint negative circles (so that S is nonbinary).

1)      If S has three vertex-disjoint negative circles, none of which is a barrier between the other two, then S is quaternary iff it is Pr3.

2)      If S does not have three vertex-disjoint negative circles, none of which is a barrier between the other two, then S is quaternary iff it is cylindrical.

 

            Note that a subdivision of a 3-connected graph completely 2-plates to become a 3-connected graph, so Theorem 1.8 holds if S is completely plated up to subdivisions of edges, and we replace Pr3 in part (1) with “a subdivision of Pr3”.

            The last preliminary result is the following easy lemma:

 

Lemma 1.9 [3, Theorem 2.1]. ±C3(1), –K4(1), and ±C4\e are forbidden minors for GF(4) representability.

 

Proof. G(±C3(1)) = G(–K4(1)) = F7– (the non-Fano plane) and G(±C4\e) = (F7–)*.

                                                                                                                        ¨¨¨

2. The Proof of Theorem 1.1.

We begin with the following lemma.

 

Lemma [SP1] 2.1. If each unbalanced block of S has a CNO, then so does S.

 

Proof. We may switch blocks of S in an order such that at each step, the block in which we are switching is incident to at most one other block we have already switched. Since switching v and switching V(S)\v yield the same signed graph, we can assume that our switching does not disturb any previously switched blocks. We switch any unbalanced block to its switching that has a CNO, and we switch any balanced block so that it is positive. Since any circle C of S lies wholly within one block, C is compatibly oriented, and thus we have obtained a CNO of S.

                                                                                                                        ¨¨¨

 

            We shall thus assume that S is completely plated, nonbinary, and 2-connected, but not 3-connected. We shall show that S has a CNO, and is of the form specified in Theorem 1.1.

            Let W = {v, w} be a vertex cutset of S. We define a rooted path from v to w to be any subgraph of S which contracts to ±P2, where v and w are the two degree-two vertices of ±P2. A semi-rooted path from v to w is a rooted path with one edge deleted. If one bridge of W contains a rooted path from v to w and another contains a semi-rooted path from v to w, then S has a ±C4\e minor and is not quaternary. Note that every nontrivial bridge of W is unbalanced (else it could be plated away).

 

Lemma 2.2. Let A be a nontrivial bridge of W. Then A contains a semi-rooted path from v to w.

 

Proof. A is unbalanced, so it contains a negative circle C. Since S is 2-connected, there are vertex-disjoint paths from C to v and w respectively. If either of these two paths is nontrivial, we are finished, so we assume that v and w are on C.

            Let P1 and P2 be the minimal paths in C connecting v to w. Since A is a bridge of W, W cannot be a barrier between P1 and P2, so there is a path P3 in A connecting P1 to P2 and not meeting v or w. But now one of the circles of the theta graph CΘP3 containing P3 is negative, so CΘP3 contains a semi-rooted path from v to w.

                                                                                                                        ¨¨¨

            W has at least two bridges, so if any bridge of W contains a rooted path from v to w, then S has a ±C4\e minor and is hence not quaternary. Similarly, if any bridge of W contains a ±C3 minor or a –K4 minor, then S contains ±C3(1) or –K4(1) and is not quaternary.

            Suppose A is an (unbalanced and nontrivial) bridge of W and A has a CNO that is perfect with respect to W. If we replace A by a negative digon D on W, then we have performed a D-plating of S.

 

Lemma 2.3. Suppose, given any switching of v (or w), we can switch vertices in V(B)\{v, w} to obtain a signing of B that has a CNO which is perfect with respect to v and w. If the D-plating S’ obtained by replacing B with a digon D has a CNO, then so does S.

 

Proof. Suppose S’ has a CNO. We may have switched v and/or w to obtain the switching of S’ that has the CNO. Since switching a subset of V(S’) is the same as switching its complement in V(S’), we may assume we have not switched w. If we have switched v, we switch vertices of V(B)\{v, w} to obtain the signing of B that has a perfect CNO with respect to {v, w}. We may reverse the directions of all negative edges in