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.
Greetings, nice post.
On Theorem 2, the gammoids are the DUALS of tranversal matroids an their contractions.
João
What I claimed is also correct. See Oxley’s book, Section 3.2, exercise 8.
OH! Right. Transversal is strict gammoid on a bipratite graph.
With respect to Problems 2, 3, 4: all matroids are connectivity matroids. Add an element in parallel with each element and add that element to $T$.
The “connectivity matroid” of a matroid M with respect to set T as in Theorem 5 is the dual of the union of the two matroids M/T and M*/T. So if M is representable then that “connectivity matroid” representable over some extension field.
Bert
That’s a very nice characterization!
Now, for Problem 5, perhaps a tangle matroid can be turned into a “connectivity matroid” over some extension field? Or is a tangle too intangible a concept for that?
Any hyperplane of the tangle matroid of a matroid is a connectivity matroid, right?
So that is representable, when the matroid is.
Nice observation! Tantalizingly close to solving Problem 5.
The following conjecture would give another partial result towards Problem 5 and would also be of independent interest.
Conjecture: For each integer $k$ there is an integer $n$ such that, if $\cT$ is a tangle of order $n$ in a matroid $M$, then there is a $k$-element set $X$ in $M$ such that the truncation of the tangle matroid to rank $k$ is the same as the connectivity matroid of $(M,T)$.
(Here I take the connectivity matroid on $E(M)$ not $E(M)-T$ as Stefan proposes.)
Ingleton suggests that it is “probably futile” to attempt to characterize the class of gammoids by excluded minors. Much the same can be said for characterizing the class of $R$-representable matroids, but for the class of $R$-representable matroids Mayhew, Newman, and Whittle have backed the claim up with compelling evidence. Do similar results hold for gammoids?
Conjecture: Each gammoid is a minor of an excluded-minor for the class of gammoids.
This struck me as a really interesting conjecture, so I became a little obsessed with it, when I probably should have been
thinking about other things. But in any case, I believe we can prove it using some of the same ideas as the MNW theorem you mentioned:
We take an arbitrary gammoid, embed it in a larger gammoid that contains a circuit-hyperplane, and then show that the relaxation violates the Ingleton condition. The relaxation is therefore not a gammoid, and in fact turns out to be an excluded minor for the class.
Here’s a broad-brush-strokes outline of the proof. If $G$ is a digraph, and $S$ and $T$ are subsets of vertices, then $L(G,S,T)$ will stand for the gammoid with ground set $S$, where $X\subseteq S$ is independent if and only if there is a set of $|X|$ disjoint directed paths each of which has their first vertex in $X$, and their last in $T$.
Lemma. Let $B$ be a basis of the gammoid $M$. There is a digraph $G$, such that $M=L(G,E(M),B)$.
Proof. This is straightforward from Theorem 2.4.4 in Oxley.
Lemma. Let $M$ be a gammoid. Then $M$ is a minor of a gammoid whose ground set is partitioned into two bases.
Proof. The class of gammoids is closed under duality, free extensions, and series extensions. Therefore we can use the same argument as in Lemma 2.2 of the MNW paper.
Let $N$ be a gammoid. By the previous lemmas, we can assume without loss of generality that $N=L(G_{N},S\cup T,T)$, where $S$ and $T$ are disjoint bases of $N$. Let $S$ and $T$ be $\{s_{1},\ldots, s_{r}\}$ and $\{t_{1},\ldots, t_{r}\}$. Add vertex set $T’=\{t_{1}’,\ldots, t_{r}’\}$ and arcs joining each $t_{i}’$ to $t_{i}$. Now we swap labels on $t_{i}$ and $t_{i}’$, for each $i$.
Next add new vertices $s_{r+1}$ and $t_{r+1}$, and add arcs from them to every vertex in $T’$. Add vertex set $U=\{u_{1},\ldots, u_{r+1}\}$ and arcs joining each $u_{i}$ to every vertex in $T’$. Add vertices $v_{S}$, $v_{T}$, and $v_{U}$, and arcs joining every vertex in $S\cup s_{r+1}$ to $v_{S}$, every vertex in $T\cup t_{r+1}$ to $v_{T}$, and every vertex in $U$ to $v_{U}$. Finally, add vertices $x$ and $y$, and add arcs from $x$ to every vertex in $T’\cup\{v_{S},v_{T},v_{U}\}$, and arcs from $y$ to $x$ and to every vertex in $T’$. Call this digraph $G$, and let $M$ be $L(G,S\cup T\cup U\cup\{x,y,s_{r+1},t_{r+1}\}, T’\cup\{v_{S},v_{T},v_{U}\})$. It’s not too difficult to see that $N$ is a minor of $M$.
Let $A=\{x,y\}$, $B=U$, $C=S\cup s_{r+1}$, and $D=T\cup t_{r+1}$. Then $A\cup B$ is a circuit-hyperplane in $M$. Let $M’$ be the matroid obtained by relaxing it. Now $M’$ violates the Ingleton condition since $r(C)+r(D)+r(A\cup B)+r(A\cup C\cup D)+r(B\cup C\cup D)=5r+11$ and $r(A\cup C)+r(A\cup D)+r(B\cup C)+r(B\cup D)+r(C\cup D)=5r+10$. Hence $M’$ is not representable, and therefore not a gammoid. It’s easy to see $M’$ has $N$ as a minor. We show any single-element deletion or contraction of $M’$ is a gammoid.
This is obvious if we delete an element from $A\cup B$ or contract an element from $C\cup D$, since the result will be a single-element deletion or contraction of $M$. Let $v$ be in $E(M’)$. If $v$ is in $C=S\cup s_{r+1}$, then $M’\backslash v=L(G_{1},E(M’\backslash v),T’\cup \{v_{S},v_{T},v_{U}\})$, where $G_{1}$ is obtained from $G$ by adding an arc from $y$ to $v_{T}$. Similarly, if $v$ is in $D=T\cup t_{r+1}$, then $M\backslash v=L(G_{2},E(M’\backslash v),T’\cup\{v_{S},v_{T},v_{U}\})$, where $G_{2}$ is obtained from $G$ by adding an arc from $y$ to $v_{S}$. Assume $v$ is in $B=U$. The only non-spanning circuits of $M$ that contain $x$ are $S\cup \{s_{r+1},x,y\}$, $T\cup\{t_{r+1},x,y\}$, and $U\cup\{x,y\}$, and these all span hyperplanes. Therefore in $M/v$, the only non-spanning circuit containing $x$ is $(U\cup\{x,y\})-v=(C\cup D)-v$, so $x$ is freely placed in $M’/v$. Therefore $M’/v$ is a gammoid if and only if $M’/v\backslash x$ is, and this follows from the observation at the beginning of the paragraph. Finally, $x$ and $y$ are clones in $M’$, so to complete the proof it suffices to show $M’/x$ is a gammoid. Let $u\in U$ be arbitrary. Any non-spanning circuit of $M$ that contains $u$ either spans one of the hyperplanes $U\cup S\cup s_{r+1}$ and $U\cup T\cup t_{r+1}$, or is equal to $U\cup\{x,y\}$. Therefore $U\cup y$ is the only non-spanning circuit of $M/x$ that contains $u$, and $u$ is freely placed in $M’/x$. Thus $M’/x$ is a gammoid if and only if $M’/x\backslash u$ is, and this is true by the same argument as before.
Great! I’ve not looked at your proof carefully, but the strategy is very believable.
Here is another conjecture to distract you.
Conjecture: The number of $n$-element gammoids is vanishingly small in comparison with the number of $n$-element excluded minors for the class of gammoids.
That would be a great conjecture to settle. It seems difficult to me, though.
We now know that the excluded minors for gammoids/real-representable form maximal anti-chains in the minor order: every matroid either contains an excluded minor, or is contained in an excluded minor (or both). I wonder if this implies the property that you mention. I’ll follow Newman and Whittle and say a class is fractal if the number of $n$-element matroids in the class vanishes in comparison to the number of $n$-element excluded minors. So my question is: if a minor-closed class has a maximal anti-chain as its set of excluded minors, does that class necessarily have the fractal property?
I think that the answer is no.
Take $\mathcal{M}_1$ to be the set containing the truncation of all wheels of rank at least $3$ to rank $3$. Take $\mathcal{M}_2$ to be the set of all proper minors of matroids in $\mathcal{M}_1$. Now the set of excluded minors for $\mathcal{M}_2$ consists of the matroids in $\mathcal{M}_1$ together with a finite number of additional matroids. The class $\mathcal{M}_2$ is not fractal, but its set of excluded minors is a maximal antichain.
Yep, that’s fair enough. Instead of doing our afternoon crossword, Stefan and I just determined the excluded minors that are not in $\mathcal{M}_{1}$. Turns out that in this case, “finite” = 7.
In case anyone would like to see a fleshed-out version of this proof, I have put it on the arxiv: http://arxiv.org/abs/1601.04220.
Problem 1 was solved by Stefan Kratsch and Magnus Wahlström in the paper “Representative sets and irrelevant vertices: New tools for kernelization” (arXiv:1111.2195). They show that there is a digraph representation on $O(n^3)$ vertices. If fact, their Theorem 3 implies the stronger result that any digraph representation of the gammoid can be reduced to a small representation by eliminating irrelevant vertices.
That’s great! I wasn’t aware of that paper. Thanks for pointing it out.