Signed Graph - Matroid Theory

Matroid Theory

There are two matroids associated with a signed graph, called the signed-graphic matroid (also called the frame matroid or sometimes bias matroid) and the lift matroid, both of which generalize the cycle matroid of a graph. They are special cases of the same matroids of a biased graph.

The frame matroid (or signed-graphic matroid) M(G) (Zaslavsky, 1982) 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 negative. (In matroid theory a half-edge acts exactly like a negative loop.) A circuit of the matroid is either a positive circle, or a pair of negative 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 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. This matroid is the column matroid of the incidence matrix of the signed graph. That is why it describes the linear dependencies of the roots of a classical root system.

The extended lift matroid L₀(G) has for its ground set the set E₀ the union of edge set 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 a negative loop, so we describe only the lift matroid. An edge set is independent if it contains either no circles or just one circle, which is negative. (This is the same rule that is applied separately to each component in the signed-graphic matroid.) A matroid circuit is either a positive circle or a pair of negative circles that are either disjoint or have just a common vertex. 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.