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
- For each $X \in \mathcal{T}$, $\lambda(X) < k$;
- For each separation $(X,Y)$ with $\lambda(X) < k$, either $X$ or $Y$ is in $\mathcal{T}$;
- If $X, Y, Z \in \mathcal{T}$ then $X\cup Y \cup Z \neq E(M)$;
- 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.
