en>ChrisGualtieri: General Fixes using AWB

2013-11-08T04:08:13Z

General Fixes using AWB

New page

In the [[mathematics|mathematical]] subject of [[matroid]] theory, the '''bicircular matroid''' of a [[graph (mathematics)|graph]] ''G'' is the matroid ''B''(''G'') whose points are the edges of ''G'' and whose independent sets are the edge sets of [[pseudoforest]]s of ''G'', that is, the edge sets in which each [[connected component (graph theory)|connected component]] contains at most one [[cycle (graph theory)|cycle]]. The circuits, or minimal dependent sets, of this matroid are the '''bicircular graphs''' (or '''bicycles''', but that term has other meanings in graph theory); these are the [[theta graph]], consisting of three paths joining the same two vertices but not intersecting each other, the figure eight graph (or tight handcuff), which consists of two cycles having just one common vertex, and the loose handcuff (or barbell), which consists of two disjoint cycles and a minimal connecting path. All these definitions apply to [[multigraph]]s, i.e., they permit multiple edges (edges sharing the same endpoints) and loops (edges whose two endpoints are the same vertex).

The bicircular matroid was introduced by Simões-Pereira and explored further by Matthews and others. It is a special case of the [[frame matroid]] of a [[biased graph]].

Bicircular matroids can be characterized as the [[Matroid#Transversal matroids|transversal matroid]]s that arise when no point belongs to more than two sets. A transversal presentation in terms of a point set and a class of subsets comes directly from the graph. The points of the presentation are the edges. There is one set for each vertex, and it consists of the edges which have that vertex as an endpoint.

The [[Matroid#Closed sets (flats)|closed sets]] (flats) of the bicircular matroid of a graph ''G'' can be described as the [[Graph theory|forest]]s ''F'' of ''G'' such that in the induced subgraph in ''V''(''G'') − ''V''(''F''), every connected component has a cycle. Since the flats of a matroid form a [[geometric lattice]] when [[partial ordering|partially ordered]] by set inclusion, these forests of ''G'' also form a geometric lattice. Their partial ordering is that ''F''1 ≤ ''F''2 if
* each component tree of ''F''1 is either contained in or vertex-disjoint from every tree of ''F''2 and
* each vertex of ''F''2 is a vertex of ''F''1.
For the most interesting example, let ''G'' o be ''G'' with a loop added to every vertex. Then the flats of ''B''(''G'' o) are all forests of ''G'', spanning or nonspanning; thus, all forests of a graph ''G'' form a geometric lattice, the '''forest lattice''' of ''G'' (Zaslavsky 1982).

==Minors==
Unlike transversal matroids in general, bicircular matroids form a [[Matroid minor|minor-closed class]]; that is, any submatroid or contraction of a bicircular matroid is also a bicircular matroid. (That can be seen from their description in terms of [[biased graph]]s (Zaslavsky 1991).)
Here is a description of deletion and contraction of an edge in terms of the underlying graph: To delete an edge from the matroid, remove it from the graph. The rule for contraction depends on what kind of edge it is. To contract a link (a non-loop) in the matroid, contract it in the graph in the usual way. To contract a loop ''e'' at vertex ''v'', delete ''e'' and ''v'' but not the other edges incident with v; rather, each edge incident with ''v'' and another vertex ''w'' becomes a loop at ''w''. Any other graph loops at ''v'' become matroid loops—to describe this correctly in terms of the graph one needs half-edges and loose edges; see [[Biased graph#Minors|biased graph minors]].

==Characteristic polynomial==

The [[Matroid#Characteristic_polynomial|characteristic polynomial]] of the bicircular matroid ''B''(''G'' o) expresses in a simple way the numbers of spanning [[Tree (graph theory)|forest]]s (forests that contain all vertices of ''G'') of each size in ''G''. The formula is
:<math>p_{B(G)}(\lambda) := \sum_{k=0}^n (-1)^k f_k (\lambda-1)^{n-k},</math>
where ''f''''k'' equals the number of ''k''-edge spanning forests in ''G''. See Zaslavsky (1982).

==Vector representation==

Bicircular matroids, like all other transversal matroids, can be [[Matroid representation|represented]] by vectors over any infinite [[Field (mathematics)|field]]. However, unlike [[graphic matroid]]s, they are not [[regular matroid|regular]]: they cannot be represented by vectors over an arbitrary [[finite field]]. The question of the fields over which a bicircular matroid has a vector representation leads to the largely unsolved problem of finding the fields over which a graph has multiplicative [[Gain graph|gains]]. See Zaslavsky (2007).

==References==

* L.R. Matthews (1977), Bicircular matroids, ''Quarterly Journal of Mathematics (Oxford)'', Second Series, vol. 28, pp. 213–227.
* J.M.S. Simões-Pereira (1972), On subgraphs as matroid cells. ''Mathematische Zeitschrift'', vol. 127, pp. 315–322.
* Thomas Zaslavsky (1982), Bicircular geometry and the lattice of forests of a graph. ''Quarterly Journal of Mathematics, Oxford'' Second Series, Vol. 33, pp. 493–511.
* Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. ''Journal of Combinatorial Theory Series B'', vol. 51, pp. 46–72.
* Thomas Zaslavsky (2007), Biased graphs. VII. Contrabalance and antivoltages". ''Journal of Combinatorial Theory Series B'', vol. 97, no. 6, pp. 1019-1040.

[[Category:Graph theory]]
[[Category:Matroid theory]]

Lower flammable limit - Revision history

en>ChrisGualtieri: General Fixes using AWB