Biased graph

From Wikipedia, the free encyclopedia

In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then so is the third circle of the theta graph. A biased graph is a generalization of the combinatorial essentials of a gain graph and in particular of a signed graph.

Formally, a biased graph Ω is a pair (G, B) where B is a linear class of circles; this by definition is a class of circles that satisfies the theta-graph property mentioned above.

A subgraph or edge set whose circles are all in B (and which contains no halfedges) is called balanced. For instance, a circle belonging to B is balanced and one that does not belong to B is unbalanced.

Biased graphs are interesting mostly because of their matroids, but also because of their connection with multary quasigroups. See below.

Contents 1 Technical notes 2 Examples 3 Matroids 3.1 The frame matroid 3.2 The lift matroid 4 Multary quasigroups 5 References

[edit] Technical notes

A biased graph may have halfedges and loose edges.

Linear classes of circles are special cases of linear subclasses of circuits in a matroid.

[edit] Examples

• If every circle belongs to B, and there are no halfedges, Ω is balanced. A balanced biased graph is (for most purposes) essentially the same as an ordinary graph.

• If B is empty, Ω is called contrabalanced. Contrabalanced biased graphs are related to bicircular matroids.

• If B consists of the circles of odd length, Ω is called antibalanced and is the biased graph obtained from an all-negative signed graph.

• The linear class B is additive, that is, closed under set sum (for sums that give a circle), if and only if B is the class of positive circles of a signed graph.

• Ω may consist of a cycle of length n ≥ 3 with all edge doubled and such that no digon (circle of length 2) is balanced. Call them biased 2C_ns. Such biased graphs lead to spikes and swirls (see Matroids, below).

• Some kinds of biased graph are obtained from gain graphs or are generalizations of special kinds of gain graphs. The latter include biased expansion graphs, which generalize group expansion graphs.

[edit] Matroids

There are two matroids associated with a biased graph, both of which generalize the cycle matroid of a graph (Zaslavsky, 1991).

[edit] The frame matroid

The frame matroid or bias matroid, M(Ω) (Zaslavsky, 1989) has for its ground set the edge set E. An edge set is independent if each component contains either no circles or just one circle, which is unbalanced. (In matroid theory a halfedge acts like an unbalanced loop and a loose edge acts like a balanced loop.)

There are four kinds of circuit of the matroid; they are called frame circuits or bias circuits. One is a balanced circle. Two other kinds are a pair of unbalanced circles together with a connecting simple path, such that the two circles are either disjoint (then the connecting path has one end in common with each circle and is otherwise disjoint from both) or share just a single common vertex (in this case the connecting path is that single vertex). The fourth kind of circuit is a theta graph in which every circle is unbalanced.

The rank of an edge set S is n − b, where n is the number of vertices of G and b is the number of balanced components of S, counting isolated vertices as balanced components.

Frame matroids generalize the Dowling geometries associated with a group (Dowling, 1973). The frame matroid of a 2C_n is called a swirl. It seems to be important in matroid structure theory.

[edit] The lift matroid

The extended lift matroid L₀(G) has for its ground set the set E₀ the union of E with an extra point, which we denote e₀. The lift matroid L(G) is the extended lift matroid restricted to E. The extra point acts exactly like an unbalanced loop or a halfedge, so we describe only the lift matroid. An edge set is independent if it contains either no circles or just one circle, which is unbalanced. (This is the rule that is applied separately to each component in the frame matroid.)

A matroid circuit is a balanced circle, a pair of unbalanced circles that are either disjoint or have just a common vertex, or a theta graph whose circles are all unbalanced.

The rank of an edge set S is n − c + ε, where c is the number of components of S, counting isolated vertices, and ε is 0 if S is balanced and 1 if it is not.

The lift matroid of a 2C_n is called a spike. Spikes seem to be quite important in matroid structure theory.

[edit] Multary quasigroups

Just as a group expansion of a complete graph K_n encodes the group (see Dowling geometry), its combinatorial analog expanding a simple cycle of length n + 1 encodes an n-ary (multary) quasigroup. It is possible to prove some theorems about multary quasigroups by means of biased graphs (Zaslavsky, t.a.)

[edit] References

• T. A. Dowling (1973), A class of geometric lattices based on finite groups. Journal of Combinatorial Theory Series B, Vol. 14, 61-86.
• Thomas Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains. Journal of Combinatorial Theory Series B, Vol. 47, 32-52.
• Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. Journal of Combinatorial Theory Series B, Vol. 51, 46-72.
• Thomas Zaslavsky (t.a.), Associativity in multary quasigroups: The way of biased expansions. Submitted for publication.