In this post I will define some matroids on graphs and give some examples. Such examples include graphic matroids, bicircular matroids and Dowling geometries. These matroids arise in different contexts and this led to a profusion (and confusion) of terminology. As a consequence, it’s really difficult to look up literature and see what has or hasn’t been done in the area. I’ll try to give a road map of the terminology and the main results. For now I’ll mostly give basic definitions and examples, leaving results for the next post.

1. Biased graphs

All graphs in this post are allowed parallel edges and loops. I’ll constantly talk about cycles of a graph: as is common in graph theory, by a cycle I mean a nonempty connected subgraph in which every vertex has degree two. In various contexts these are also called polygons, circuits, circles… I’ll stick to the word “cycle”. I’ll also abuse terminology and use the word “cycle” to mean the set of edges of a cycle. By a nonempty path I mean a path with at least one edge. Let’s start by defining our general universe.

Def. A biased graph is a pair $(G,\mathcal{B})$ where $\mathcal{B}$ is a set of cycles of $G$ satisfying the following property:

Theta property: for every two cycles $C_1$ and $C_2$ in $\mathcal{B}$ intersecting in a nonempty path, the third cycle in $C_1 \cup C_2$ is also in $\mathcal{B}$.

The cycles in $\mathcal{B}$ are called balanced, and the other cycles are unbalanced. Two cycles sharing a non-empty path form a theta; a theta with all cycles unbalanced is an unbalanced theta.

The theta property guarantees that the matroids defined in the next two sections are indeed matroids. In particular, this property guarantees that the third circuit axiom is satisfied.

Here are some important examples of biased graphs (the importance will become clear in the next sections):

• Biased graphs having only balanced cycles.
• Biased graphs having only unbalanced cycles.
• Signed graphs: consider a graph $G$ and a set of edges $F$ of $G$. Then we declare a cycle of $G$ to be balanced if it contains an even number of edges in $F$, and unbalanced otherwise. The resulting biased graph is called a signed graph. Balanced cycles in signed graphs are also called even or positive in the literature, while unbalanced cycles are also called odd or negative.
• Group labelled graphs: consider a graph $G$ and a (say multiplicative) group $\Gamma$. Orient every edge of $G$ and assign to every oriented edge a value from $\Gamma$. This is how we obtain group labelled graphs. Group labelled graphs are also called gain graphs or voltage graphs. From a group labelled graph we obtain a biased graph as follows. Pick any cycle $C$ of $G$ and choose an orientation for $C$. Traverse $C$ with this orientation and multiply the values on the traversed edges, where backward edges will get the inverse value (so if $(u,v)$ is an oriented edge with value $g$ and this edge appears as $(v,u)$ in the orientation of $C$, the value for this edge will be $g^{-1}$). If the total value along the cycle is $1$, then the cycle is declared to be balanced, otherwise it is unbalanced. Changing the orientation of a cycle only changes the value to its inverse, so this assignment is well defined. It is easy to see that this assignment of balanced/unbalanced cycles satisfies the theta property, so we obtain a biased graph from our group labelled graph. I’ll often abuse terminology and call this biased graph a group labelled graph. Signed graphs are special cases of group labelled graphs, obtained by labelling the edges of a graph with elements from $GF(2)$ or, equivalently, from the multiplicative group of the ternary field. I set them aside because they are relevant on their own.

Following are the two main matroids arising from biased graphs. This general setting was first introduced by Zaslavsky (see [Zas89] and [Zas91]).

2. Frame matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the frame matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles together with a minimal path joining them.
4. An unbalanced theta.

Circuits of frame matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

The circuits in 2. and 3. are called handcuffs (respectively tight and loose). 

Zaslavsky [Zas91] calls these matroids biased matroids, but recently the term “frame matroids” has become more common. Originally, a frame matroid was defined to be a matroid $M$ to which a basis $B$ could be added so that every element of $M$ is spanned by two elements in $B$. Zaslavsky showed that this definition is equivalent to the one coming from biased graphs. Consider a frame matroid $M$ represented by a biased graph $\Omega$. Form a new biased graph $\Omega’$ by adding an unbalanced loop to every vertex of $\Omega$ and call $B$ the set of these unbalanced loops. Then $B$ is a basis of the frame matroid $M’$ of $\Omega’$ and $M$ is a restriction of $M’$. Every loop of $\Omega$ is either balanced (hence spanned by the empty set), or unbalanced (so in parallel to the element of $B$ incident to the same vertex). Moreover, every edge of $\Omega$ that is not a loop is spanned by the two loops of $B$ at its endpoints.

It follows immediately from the definition that the independent sets of the frame matroid of $(G,\mathcal{B})$ are the set of edges $F$ such that every component induced by $F$ contains at most one cycle, which will have to be unbalanced.

Here are some examples of frame matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the frame matroids of biased graph with all cycles balanced. So frame matroids are a generalization of graphic matroids.
• Bicircular matroids: these are the frame matroids of biased graphs with all cycles unbalanced. Bicircular matroids have been widely studied (more of this in the next post, else no reader will make it to the definition of lift matroids).
• Signed-graphic matroids: these are frame matroids of signed graphs.
• Dowling geometries: first defined by Dowling ([Dow73]) these are frame matroids of group labelled graphs.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the multiplicative group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $e$ be an edge of $\Omega$ with label $g$. If $e$ is a balanced loop (i.e. a loop labelled $1$), then the column for $e$ is an all-zero column; if $e$ is an unbalanced loop incident to vertex $u$, then the column for $e$ has the $u$ entry equal to $g$ and zero everywhere else.  If $e=uv$ is not a loop and $e$ is oriented as (u,v), then the corresponding column for $e$ has a $1$ in position $u$, $-g$ in position $v$ and zero everywhere else. The proof that this is a representation of the frame matroid of $\Omega$ is not obvious, but appears, for example, in [Zas82].

The class of frame matroids (and the subclasses defined above) are minor-closed classes. The same is true for lift matroids, defined in the next section. However, this post is long enough without adding matroid operations for biased graphs. I’ll leave that for the next post as well.

3. Lift matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the lift matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles.
4. An unbalanced theta.

Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

At a first glance lift matroids may look quite similar to frame matroids, but the differences between them emerge as soon as you start working with them. My rule of thumb is that frame matroids are easier to deal with than lift matroids, for some definition of “easier”. Having circuits that are not connected in the graph makes things a lot more complicated in a lot of cases.

From the definition we can easily see that the independent sets of the lift matroid of $(G,\mathcal{B})$ are the set of edges $F$ containing at most one cycle, which will have to be unbalanced.

Here are some examples of lift matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the lift matroids of biased graph with all cycles balanced. So lift matroids are also a generalization of graphic matroids.
• Even cycle matroids: these are lift matroids of signed graphs. Even cycle matroids appear in alternative proofs of the list of excluded minors for graphic matroids ([Ger95]) and Seymour’s decomposition of regular matroids ([GG95]). In fact, any binary single element coextension of a graphic matroid is an even cycle matroid.
• Spikes: let $G$ be obtained from the cycle on $n$ edges by doubling every edge. Declare every pair of parallel edges to form an unbalanced cycle. The other cycles of the graph may be declared to be balanced or unbalanced, as long as the theta property is satisfied. The lift matroid of the resulting biased graph is a spike with no tip. To obtain a spike with a tip, add an unbalanced loop to the graph.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the additive group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $A$ be the vertex-edge oriented incidence matrix of $G$, with the orientation given in the group labelled graph. Add a row to $A$, where the entry for edge $e$ is the group label of $e$. The reader is invited to check that this is a valid matrix representation for the matroid.

In the next post I’ll survey some problems and results regarding these matroids.

References

The Twitterverse has been abuzz recently with the news that Rota’s Conjecture has been proved by Jim Geelen, Bert Gerards, and Geoff Whittle! See press releases here and here (with an interview of Geoff at the bottom) and here. This news was known, by word of mouth, to people in the community close to the sources for a while, but let me take this opportunity to try to explain to the non-experts what this conjecture is all about. I will build up in a few steps from a small class of objects to bigger and bigger classes. For the experts, this survey by Geelen, Gerards, and Whittle might be better reading. Continue reading →

$\newcommand{\cG}{\mathcal{G}}$ $\newcommand{\cM}{\mathcal{M}}$ $\newcommand{\elem}{\varepsilon}$ $\newcommand{\con}{/}$ $\newcommand{\del}{\!\backslash\!}$

I’m going to give what is hopefully a less frenetically paced exposition of what many readers have probably seen me talk about more that once – the growth rates of matroids in minor-closed classes. I’ll try to cover things from the ground up in order to motivate the subject, as well as provide some short proofs. The traditional starting point, from which I won’t deviate, is a theorem of Mader [Mader67]:

Theorem 1. If $\mathcal{G}$ is a proper minor-closed class of graphs, then $|E(G)| \le c_{\mathcal{G}}|V(G)|$ for each simple graph $G$ in $\cG$.

Here, `proper’ means that $\cG$ isn’t the class of all graphs, and $c_{\mathcal{G}}$ is a positive real constant depending only on $\cG$. Note that this theorem fails if we allow $\mathcal{G}$ to be the class of all graphs; the complete graph $K_t$ has $\binom{t}{2}$ edges and $t$ vertices, and the ratio $\binom{t}{2}$ is not bounded above by any linear function of $t$. With this fact in mind, what is interesting is the dichotomy; either $\cG$ is the class of all graphs and the densest simple graphs in $\mathcal{G}$ (the cliques) have a number of edges that is quadratic in their number of vertices, or $\mathcal{G}$ is not the class of all graphs and this bound is linear. This is not just a curiosity – we know now that it reflects the structure proved by Robertson and Seymour in the graph minors structure theorem – the graphs in a proper minor-closed class are at most linearly dense because they are `almost’ embeddable on a fixed surface. Of course we didn’t know this in 1967, so it presented a question rather than a corroboration.

Moving on to matroids, we first define some convenient notation. For a matroid $M$, we write $\elem(M)$ for $|\mathrm{si}(M)|$ (equivalently the number of rank-$1$ flats of $M$); this stops us having to awkwardly talk about simple matroids all the time. For a minor-closed class $\cM$, we use $h_{\cM}(n)$ to denote the function whose value at an integer $n$ is the maximum of $\elem(M)$ over all matroids $M \in \cM$ whose rank is at most $n$. Some people call this the size function but I’ll call in the growth rate function. We allow $h_{\cM}(n) = \infty$ – indeed any class that contains $U_{2,k}$ for all $k$ will satisfy this for all $n \ge 2$. In the interesting cases this function is monotonely increasing without bound. For example, for the class $\cM$ of graphic matroids has growth rate function $h_{\cM}(n) = \binom{n+1}{2}$, and by Theorem 1 above, all of its proper subclasses have growth rate function at most linear in $n$.

The next few theorems will combine to divide minor-closed classes of matroids into four types, just as Theorem 1 divides classes of graphs into two. These theorems all concern `dichotomies’ in growth rate functions. The first, due to Kung [Kung91] distinguishes classes with finite growth rate functions from those with infinite growth rate function. We’ll even prove it, since the proof is so nice.

Theorem 2.  If $\cM$ is a minor-closed class of matroids, then either

• $h_{\cM}(n) = \infty$ for all $n \ge 2$, or
• there is some $\ell \ge 2$ such that $U_{2,\ell+2} \notin \cM$ and $h_{\cM}(n) \le \frac{\ell^n-1}{\ell-1}$ for all $n$.

Proof: If $U_{2,\ell+2} \in \cM$ for all $\ell \ge 2$ then the first outcome holds, so we may assume that $U_{2,\ell+2} \notin \cM$ for some $\ell \ge 2$, and will show that $\elem(M) \le \frac{\ell^r-1}{\ell-1}$ for each integer $r$. Let $M \in \cM$ be a rank-$r$ matroid and $e$ be a nonloop of $M$. Inductively we may assume that $\elem(M \con e) \le \frac{\ell^{r-1}-1}{\ell-1}$, and we know $M$ has $\elem(M \con e)$ lines containing $e$. Since $M$ has no $U_{2,\ell+2}$-minor, each of these lines has at most $\ell$ points other than $e$, so $\elem(M) \le \ell \elem(M \con e) + 1 \le \ell\frac{\ell^{r-1}-1}{\ell-1}+ 1 \le \frac{\ell^r-1}{\ell-1}$, as required.

This theorem tells us that there is no minor-closed class with finite growth rate function greater than exponential in $n$, and cleanly divides growth rate functions into the infinite and the finite. In fact, there is much more to the story than this; we’ll finish by stating the theorem that will be the focus of my next post. This theorem was conjectured by Kung [Kung91] and stated in [GKW09] as a consequence of various theorems of Geelen, Kabell, Kung and Whittle.

Growth Rate Theorem. If $\cM$ is a minor-closed class of matroids, then either

• $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
• $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$ and $\cM$ contains all graphic matroids,
• there is a prime power $q$ such that $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n$ and $\cM$ contains all GF$(q)$-representable matroids, or
• $h_{\cM}(n) = \infty$ for all $n \ge 2$ and $\cM$ contains all simple rank-$2$ matroids.

Again $c_{\cM}$ is always a real constant depending only on $\cM$. In other words, up to a constant, there are just four possible qualitative behaviours for growth rate functions: linear, quadratic, exponential and infinite. This is dramatic behaviour and deserves more consideration. See you next time!

References

• [GKW09] J. Geelen, J. P. S. Kung, and G. Whittle. Growth rates of minor-closed classes of matroids. J. Combin. Theory Ser. B, 99(2):420–427, 2009.
• [Kung91] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 21–61. Amer. Math. Soc., Providence, RI, 1993.
• [Mader67] W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Mathematische Annalen, 174:265–268, 1967. 10.1007/BF01364272.

In this post I’d like to discuss three families of matroids that arise in the study of connectivity. The first is well-known and extensively studied; the other two are more recent and appear as lemmas buried in papers with a different main focus. I will focus on a few open problems for each of these families.

1. Gammoids

The matroid $Q_6$, represented as geometry (right) and as gammoid (left)

For our first example, consider a directed graph $D = (V,A)$. Let $S, T \subseteq V$, and define a function $\rho$ mapping subsets of $S$ to integers, defined as

$\rho(X) = $ the maximum number of vertex-disjoint $X-T$ paths.

Theorem 1. The function $\rho$ is the rank function of a matroid on ground set $S$.

We say that a matroid $M$ is a gammoid if there exist a digraph $D$ and sets $S, T$ such that the matroid defined above is isomorphic to $M$. If $S = V$ then the gammoid is said to be strict.

There is a beautiful and unexpected proof of this result, due to Ingleton and Piff [IP73], which takes a detour through transversal matroids. It reveals a beautiful duality relation between Menger’s and König’s theorems from graph theory. The proof can be found in Section 2.4 of [Oxl11]. A consequence is:

Theorem 2. The set of gammoids is precisely the set of transversal matroids and their contractions.

The question of representability of transversal matroids, and therefore of gammoids, has received some attention. Piff and Welsh first proved that they are representable over any sufficiently large field, and Atkin [Atk72] gave the following explicit bound:

Theorem 3. Let $M$ be a transversal matroid of rank $r$ on $n$ elements. Then $M$ is representable over every field $\mathbb{F}$ satisfying

$$ |\mathbb{F}| \geq n + {n \choose r – 1} $$

One problem that, to my knowledge, hasn’t received attention so far is the following:

Problem 1. Find a good upper bound on the size of the digraph needed to represent a gammoid. Concretely, find a function $f: \mathbb{N} \to \mathbb{N}$ such that every gammoid on $n$ elements can be realized in a digraph with at most $f(n)$ vertices.

In the variant where $D$ is an undirected graph, a result by Tony Huynh and me [HZ13] can be used to derive some function $f$, but it’s really bad: a tower of twos, i.e.

$$2^{2^{2^\cdots}},$$

of height $2^{n}$.

2. Linkage matroids

Tutte’s Linking Theorem is a generalization of Menger’s Theorem to arbitrary matroids. The two ingredients are the connectivity function of a matroid:

$$ \lambda(X) = r(X) + r(E – X) – r(M) $$

and Tutte’s connectivity function between $S$ and $T$:

$$ \kappa(S,T) = \min \{ \lambda(X) : S \subseteq X \subseteq E – T \}.$$

Tutte’s Linking Theorem [Tut65] is the following:

Theorem 4. The function $\kappa(S,T)$ equals the maximum, over all minors $N$ of $M$ with $E(N) = S \cup T$, of $\lambda_N(S)$.

See Section 8.5 of [Oxl11] for more on this important theorem. It was observed by Geelen, Gerards, and Whittle [GGW07, Lemma 4.6] that Tutte’s connectivity function can be used to define a matroid in much the same way as a gammoid:

Theorem 5. Let $T$ be a set of elements of the matroid $M$ with ground set $E$. For each $X \subseteq E – T$, define

$$\psi(X) = \kappa(X, T).$$

Then $\psi$ is the rank function of a matroid on E – T.

Proof. We verify the rank axioms. Monotonicity and unit increase are easily verified. To show submodularity, we use the fact that $\lambda$ is submodular. Pick $X_1, X_2 \subseteq E – T$. By definition there exist sets $A_1, A_2$ such that $X_i \subseteq A_i \subseteq E – T$ and $\lambda(A_i) = \kappa(X_i, T)$. Note that $X_1\cap X_2 \subseteq A_1\cap A_2$ and $X_1\cup X_2 \subseteq A_1\cup A_2$, so $\kappa(X_1\cap X_2, T) \leq \lambda(A_1\cap A_2)$ and $\kappa(X_1\cup X_2, T) \leq \lambda(A_1\cup A_2)$. Now

$$ \psi(X_1) + \psi(X_2) = \lambda(A_1) + \lambda(A_2) \geq \lambda(A_1\cap A_2) + \lambda(A_1\cup A_2) \geq \\
\kappa(X_1\cap X_2, T) + \kappa(X_1\cup X_2, T) = \psi(X_1\cap X_2) + \psi(X_1\cup X_2). \square$$

To the best of my knowledge, not much more is known about these matroids (let’s call them connectivity matroids for now). I’m listing one easy consequence and three problems:

Proposition 1. The connectivity matroid of $M^*$ with respect to $T$ equals the connectivity matroid of $M$ with respect to $T$.

Problem 2. Characterize the contractions of connectivity matroids.

Problem 3. Characterize the duals of connectivity matroids.

Problem 4. Is each connectivity matroid representable over every sufficiently large field?

3. Tangle matroids

For our third family of matroids we abstract away from the subset $T$ that appeared in the previous two. Instead, we go for a more general notion of “where the interesting part of the matroid lies”, called a tangle.

Definition 1. Let $M$ be a matroid, $k$ an integer, and $\mathcal{T}$ a collection of subsets of $M$ such that

1. For each $X \in \mathcal{T}$, $\lambda(X) < k$;
2. For each separation $(X,Y)$ with $\lambda(X) < k$, either $X$ or $Y$ is in $\mathcal{T}$;
3. If $X, Y, Z \in \mathcal{T}$ then $X\cup Y \cup Z \neq E(M)$;
4. For each element $e$, $E(M) – \{e\} \not\in \mathcal{T}$.

Then $\mathcal{T}$ is a tangle of $M$ of order $k$.

The members of $\mathcal{T}$ are called small. Intuitively, for each small set $X$, the important part of the matroid (such as a big grid minor or big projective geometry minor) is for the most part contained in the complement of $X$. Note that a matroid can have many different tangles (just as it can have many different grid minors).

Now we can define the tangle matroid, introduced by Geelen, Gerards, Robertson and Whittle [GGRW06, Lemma 4.3]:

Theorem 6. Let $M$ be a matroid, $\mathcal{T}$ a tangle of $M$ of order $k$, and define a function $\phi$ by

$$\phi(X) = \begin{cases}
\min \{ \lambda(Y) : X \subseteq Y \text{ and } Y \in \mathcal{T} \} & \text{if } Y \text{ exists;}\\
k & \text{otherwise.}
\end{cases}$$

Then $\phi$ is the rank function of a matroid on $E(M)$ called the tangle matroid and denoted by $M(\mathcal{T})$.

The proof is very similar to that of Theorem 5.

The tangle matroid is a very useful object in the study of tangles, since it summarizes connectivity information in a geometric manner: 3-separations correspond to lines, 4-separations to planes, and so on. One nagging problem is the following:

Problem 5. Let $M$ be a matroid representable over a (finite) field $\mathbb{F}$, and let $\mathcal{T}$ be a tangle of $M$. Is it true that $M(\mathcal{T})$ is representable over an extension field of $\mathbb{F}$?

It is problematic that $M(\mathcal{T})$ can have arbitrarily large projective geometry minors, so it won’t be representable over any sufficiently large field. Hopefully it is still sufficient to go to a sufficiently large extension field.

References

[Atk72] A. O. L. Atkin, Remark on a paper of Piff and Welsh, J. Combinatorial Theory Ser. B 13 (1972), 179–182.

[GGRW06] J.Geelen,B.Gerards,N.Robertson,andG.Whittle, Obstructions to branch-decomposition of matroids, J. Combin. Theory Ser. B 96 (2006), no. 4, 560–570.

[GGW07] Jim Geelen, Bert Gerards, and Geoff Whittle, Excluding a planar graph from GF(q)-representable matroids, J. Combin. Theory Ser. B 97 (2007), no. 6, 971–998.

[HZ13] T. Huynh and S. H. M. van Zwam, Intertwining connectivities for representable matroids, Submitted. Preprint at arXiv:1304.6488.

[IP73] A. W. Ingleton and M. J. Piff, Gammoids and transversal matroids, J. Combinatorial Theory Ser. B 15 (1973), 51–68.

[Oxl11] J. Oxley, Matroid theory, second edition, Oxford University Press, 2011.

[Tut65] W. T. Tutte, Menger’s theorem for matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 49–53.