![\"The](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2013\/08\/Q6gammoid.png\")
<\/a>The matroid $Q_6$, represented as geometry (right) and as gammoid (left)<\/p><\/div>\n
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<\/p>\n
$\\rho(X) = $ the maximum number of vertex-disjoint $X-T$ paths.<\/p>\n
Theorem 1.<\/strong> The function $\\rho$ is the rank function of a matroid on ground set $S$.<\/em><\/p>\n We say that a matroid $M$ is a\u00a0gammoid<\/em> 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\u00a0strict<\/em>.<\/p>\n There is a beautiful and unexpected proof of this result, due to Ingleton and Piff [IP73], which takes a detour through\u00a0transversal matroids.\u00a0<\/em>It reveals a beautiful duality relation between Menger’s and K\u00f6nig’s theorems from graph theory. The proof can be found in Section 2.4 of [Oxl11]. A consequence is:<\/p>\n Theorem 2.\u00a0<\/strong>The set of gammoids is precisely the set of transversal matroids and their contractions.<\/em><\/p>\n 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:<\/p>\n Theorem 3.\u00a0<\/strong>Let $M$ be a transversal matroid of rank $r$ on $n$ elements. Then $M$ is representable over every field $\\mathbb{F}$ satisfying<\/em><\/p>\n $$ |\\mathbb{F}| \\geq n + {n \\choose r – 1} $$<\/p>\n One problem that, to my knowledge, hasn’t received attention so far is the following:<\/p>\n Problem 1.\u00a0<\/strong>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.<\/p>\n 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.<\/p>\n $$2^{2^{2^\\cdots}},$$<\/p>\n of height $2^{n}$.<\/p>\n Tutte’s Linking Theorem\u00a0<\/em>is a generalization of Menger’s Theorem to arbitrary matroids. The two ingredients are the\u00a0connectivity function<\/em>\u00a0<\/em>of a matroid:<\/p>\n $$ \\lambda(X) = r(X) + r(E – X) – r(M) $$<\/p>\n and Tutte’s\u00a0connectivity function between $S$ and $T$<\/em>:<\/p>\n $$ \\kappa(S,T) = \\min \\{ \\lambda(X) : S \\subseteq X \\subseteq E – T \\}.$$<\/p>\n Tutte’s Linking Theorem [Tut65] is the following:<\/p>\n Theorem 4.\u00a0<\/strong>The function $\\kappa(S,T)$ equals the maximum, over all minors $N$ of $M$ with $E(N) = S \\cup T$, of $\\lambda_N(S)$.<\/em><\/p>\n 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:<\/p>\n Theorem 5.\u00a0<\/strong>Let $T$ be a set of elements of the matroid $M$ with ground set $E$. For each $X \\subseteq E – T$, define<\/em><\/p>\n $$\\psi(X) = \\kappa(X, T).$$<\/em><\/p>\n Then $\\psi$ is the rank function of a matroid on E – T.<\/em><\/p>\n Proof.\u00a0<\/em>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<\/p>\n $$ \\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 \\\\ To the best of my knowledge, not much more is known about these matroids (let’s call them connectivity matroids\u00a0<\/em>for now). I’m listing one easy consequence and three problems:<\/p>\n Proposition 1.\u00a0<\/strong>The connectivity matroid of $M^*$ with respect to $T$ equals the connectivity matroid of $M$ with respect to $T$.<\/em><\/p>\n Problem 2.\u00a0<\/strong>Characterize the contractions of connectivity matroids.<\/p>\n Problem 3.\u00a0<\/strong>Characterize the duals of connectivity matroids.<\/p>\n Problem 4.\u00a0<\/strong>Is each connectivity matroid representable over every sufficiently large field?<\/p>\n 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\u00a0tangle<\/em>.<\/p>\n Definition 1.\u00a0<\/strong>Let $M$ be a matroid, $k$ an integer, and $\\mathcal{T}$ a collection of subsets of $M$ such that<\/p>\n Then $\\mathcal{T}$ is a\u00a0tangle of $M$ of order $k$.<\/em><\/p>\n The members of $\\mathcal{T}$ are called\u00a0small.\u00a0<\/em>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).<\/p>\n Now we can define the\u00a0tangle matroid, <\/em>introduced by Geelen, Gerards, Robertson and Whittle [GGRW06, Lemma 4.3]: Theorem 6.\u00a0<\/strong>Let $M$ be a matroid, $\\mathcal{T}$ a tangle of $M$ of order $k$, and define a function $\\phi$ by<\/em><\/p>\n $$\\phi(X) = \\begin{cases} Then $\\phi$ is the rank function of a matroid on $E(M)$ called the\u00a0tangle matroid\u00a0and denoted by $M(\\mathcal{T})$.<\/em><\/p>\n The proof is very similar to that of Theorem 5.<\/p>\n 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:<\/p>\n Problem 5.\u00a0<\/strong>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}$?<\/p>\n 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.<\/p>\n [Atk72] A. O. L. Atkin, Remark on a paper of Piff and Welsh<\/i>, J. Combinatorial Theory Ser. B 13 (1972), 179\u2013182.<\/p>\n [GGRW06] J.Geelen,B.Gerards,N.Robertson,andG.Whittle,\u00a0Obstructions to branch-decomposition of matroids<\/i>, J. Combin. Theory Ser. B 96 (2006), no. 4, 560\u2013570.<\/p>\n [GGW07] Jim Geelen, Bert Gerards, and Geoff Whittle,\u00a0Excluding a planar graph from\u00a0<\/i>GF(q<\/i>)-representable matroids<\/i>, J. Combin. Theory Ser. B 97 (2007), no. 6, 971\u2013998.<\/p>\n [HZ13] T. Huynh and S. H. M. van Zwam, Intertwining connectivities for representable matroids<\/i>, Submitted. Preprint at arXiv:1304.6488<\/a>.<\/p>\n [IP73] A. W. Ingleton and M. J. Piff, Gammoids and transversal matroids<\/i>, J. Combinatorial Theory Ser. B 15 (1973), 51\u201368.<\/p>\n [Oxl11] J. Oxley, Matroid theory, second edition<\/i>, Oxford University Press, 2011.<\/p>\n [Tut65] W. T. Tutte, Menger\u2019s theorem for matroids<\/i>, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 49\u201353.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading 2. Linkage matroids<\/h2>\n
\n\\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$$<\/p>\n3. Tangle matroids<\/h2>\n
\n
\n<\/em><\/p>\n
\n\\min \\{ \\lambda(Y) : X \\subseteq Y \\text{ and } Y \\in \\mathcal{T} \\} & \\text{if } Y \\text{ exists;}\\\\
\nk & \\text{otherwise.}
\n\\end{cases}$$<\/p>\nReferences<\/h2>\n