|
|
Have you found anything interesting yet? |
|
|
|
|
[Updated 15 July 1999] Yes, I have! I have obtained a complete
characterization of the representability of a given signed graph. I’d like to
take a moment to provide some links, then let you know where some of the
ideas came from, before proceeding. Links to my papers: ·
“Binary Signed Graphs”,
in Word 2000 and html
formats. ·
“GF(4)
Representability of Bias Matroids of 3-connected Signed Graphs”, in Word 2000 and html formats. ·
“Vector
Representability of Bias Matroids of Signed Graphs”, in Word 2000 and html
formats. Note: The above html versions of my papers use Microsoft’s conversion tools
from Word 2000. Your browser may not display them. *** My work in the area of representability
has been based on the roads of study suggested by the following lemma,
derived from works of Zaslavsky, Whittle and Tutte:
Thus there are but three possibilities to
consider:
I now give a few more definitions integral
to my theorems. A block of a graph G is a maximal subgraph B of G for
which any two edges of B are contained in a polygon. Given a signed graph G,
by G^ we mean the signed graph obtained by contracting all balanced blocks of
G. Theorem 1: The bias matroid of a connected signed graph G is
binary iff G^ does not have a pair of vertex-disjoint negative
polygons. Corollary 1: If the signed graph G is two-connected and
loopless, then its bias matroid is binary iff G does not have a pair
of vertex-disjoint negative polygons. Corollary 2: If G^ has two or more blocks, then the bias
matroid of G is binary iff there is a vertex v in G^ such that
When I first wrote this page in 1996, I'd
only obtained Corollary 1. Since then, I’ve come quite some way, earning my
doctorate and eventually obtaining the complete characterization, including
all items shown below. We need a few more definitions. Let A, B and C be subgraphs of G, where
neither A nor C is contained wholly within B. We say that B is a barrier
between A and C if all paths from A to C intersect B. For a subgraph B of G, the
relation ~ on the collection of edges G\B given by (x~y iff
B is not a barrier between x and y) is an equivalence relation,
and the subgraphs of G determined by the equivalence classes of ~ are called
the bridges of B. A nontrivial bridge of B is one that contains
vertices not in B – so if B is a set of vertices, then B is a cutset of G iff
B has two or more nontrivial bridges. G is said to satisfy the non-barrier
condition if there exist three vertex-disjoint negative circles in G, none
of which is a barrier between the other two. If G has at least two
vertex-disjoint negative circles but does not satisfy the non-barrier
condition, then we say it satisfies the barrier condition. Let {a, b, c} be a vertex cutset of
G with a balanced, nontrivial bridge X. We may assume that X has only
positive edges. We delete X from G and replace it with a triangle of all
positive edges on {a, b, c}, (but we don’t duplicate a positive edge
that’s already in place). This operation is called 3-plating. I have
shown that if a 3-plating of G is GF(4)-representable, then so is G. A 2-plating
is defined similarly, and has the same preservation property just cited. Platings
lower the number of vertices in the signed graphs in consideration, so any
signed graph can be 2- and 3-plated until no more 2- and 3-platings remain,
and the resultant signed graph, which is called completely plated, is
GF(4)-representable iff G is. The signed graph Pr3 has six
vertices and twelve edges: vertices {v1, v2, v3, w1, w2, w3}, a positive triangle on {v1, v2, v3}, a positive triangle on {w1, w2, w3}, and negative digons on each {vi,
wi}. A cylindrical signed graph is one
that can be embedded (without crossings) on a cylinder such that a circle C
in G can be continuously deformed into a single point on the cylinder iff
C is positive. With these definitions, we are able to
state the main result of my doctoral thesis. Theorem 2. Let G be a completely plated 3-connected signed
graph. Then G is GF(4)-representable iff one of the following holds: 1) G satisfies the non-barrier condition and is Pr3. 2) G satisfies the non-barrier condition and is
cylindrical. I completed these two theorems, along with
a collection of other results, as part of my doctoral thesis. I graduated
from Binghamton University in the Spring of 1998, and am now working as an Instructor
at the University
of Kentucky, and I will be looking
for a full-time permanent position for the 2000-2001 school year. I have been
at UK for a year now, and during my stay here I perfected the
characterization begun in Theorems 1 and 2. Theorem 3 gives a complete
characterization. There is one missing definition – that of CNO – but I leave
that definition to the papers, to which I have placed links above. Theorem 3. Let G be a connected signed graph. Let G^ be the
signed graph obtains by contracting all balanced blocks of G. 1) G is binary (and hence regular) iff G^ contains no pair of
vertex-disjoint negative circles. 2) G 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 G^ 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
G0 with a balancing vertex, for which G0 has a
compatible negative orientation (CNO) that is perfect from v to w. 3) If G is neither binary nor quaternary, then G is representable over all fields of characteristic other than two, but no other fields. |
|
|
|
|
