Four proofs of a theorem by Vámos

Let $\chi(M)$ be the characteristic set of the matroid $M$; that is, \[\chi(M)=\{\operatorname{char}(\mathbb{F})\colon M\ \text{is representable over the field}\ \mathbb{F}\},\] where $\operatorname{char}(\mathbb{F})$ is the characteristic of $\mathbb{F}$. It is well known that $0\in\chi(M)$ if and only if $\chi(M)$ contains infinitely many primes. One direction is due to Rado [4]. The following theorem contains the other direction.

Theorem 1. If $\chi(M)$ contains infinitely many primes, then it contains zero.

One unusual aspect of Theorem 1 is that there are four proofs of it in the literature. All of them are attractive, and they call upon different (but related) sets of tools: Zorn’s lemma, compactness in first-order logic, ultraproducts, and Gröbner bases. In this post I will review all four proofs.

To start with, let $r$ be $r(M)$, and assume that $E(M)=\{1,\ldots, n\}$. Let $X$ be the set of variables $\{x_{i,j}\}_{1\leq i \leq r,\ 1\leq j \leq n}$, and let $R$ be the polynomial ring $\mathbb{Z}[X]$. We will let $A$ be the $r\times n$ matrix where the entry in row $i$ and column $j$ is $x_{i,j}$. Each $r$-element subset of $E(M)$ corresponds to an $r\times r$ submatrix of $A$, and thereby to a homogeneous polynomial in $R$, namely the determinant of that submatrix. Let $\mathcal{B}$ be the set of polynomials that correspond to bases of $M$, and let $\mathcal{N}$ contain the polynomials that correspond to dependent $r$-element subsets in $M$. Thus a representation of $M$ is a ring homomorphism from $R$ to a field that sends every polynomial in $\mathcal{N}$, but no polynomial in $\mathcal{B}$, to zero.

The first proof of Theorem 1 is due to Peter Vámos. He published two articles in the proceedings entitled Möbius Algebras, produced by the University of Waterloo in 1971. The proof of Theorem 1 has sometimes been cited as coming from [6], but in fact the correct attribution is to [5]. His proof hinges on the following lemma. Recall that an ideal, $P$, is prime, if $ab\in P$ implies that $a\in P$ or $b\in P$.

Lemma 1. Let $I$ be an ideal in a commutative ring, $S$, and let $T$ be a multiplicatively closed set of $S$ that is disjoint from $I$. There exists a prime ideal, $P$, such that $I\subseteq P$, and $P\cap T=\emptyset$.

Proof. We consider the partial order of ideals in $S$ that contain $I$ and that are disjoint from $T$. Assume that $J_{1}\subset J_{2}\subset J_{3}\subset \cdots$ is a chain in the order. It is easy to confirm that the $J_{1}\cup J_{2}\cup J_{3}\cup \cdots$ is itself an ideal in the order. This means that every such chain of ideals has a maximal element, so we can apply Zorn’s Lemma. Therefore the partial order has a maximal element, $P$. It remains to show that $P$ is a prime ideal. Assume otherwise, so that the product $ab$ belongs to $P$, even though $a\notin P$ and $b\notin P$. The maximality of $P$ means that the ideal generated by $P$ and $a$ is not disjoint from $T$, so there is some element, $ca+p$ in $T\cap \langle P, a\rangle$. (Here $p\in P$, and $c$ is an element of $S$.) Similarly, there are elements $q\in P$ and $d\in S$ such that $db+q$ belongs to $T$. Since $T$ is multiplicatively closed, we see that $(ca+p)(db+q)=(cd)(ab)+(ca)q+(db)p+pq$ is in $T$. But this element is also in $P$, since $ab\in P$. Now we have a contradiction to the fact that $P$ and $T$ are disjoint. $\square$

Proof 1. Let $p_{1},p_{2},p_{3},\ldots$ be distinct primes such that $M$ is representable over a field of characteristic $p_{i}$ for each $i$. Let $\phi_{i}$ be a homomorphism from $R$ to a field of characteristic $p_{i}$ that takes all the polynomials in $\mathcal{N}$, and no polynomial in $\mathcal{B}$, to zero. Then the kernel, $\ker(\phi_{i})$, of $\phi_{i}$ is a prime ideal of $R$ containing $\mathcal{N}$, but disjoint from $\mathcal{B}$. Moreover, the integer $p_{i}$ is contained in $\ker(\phi_{i})$. In fact, the only integers in $\ker(\phi_{i})$ are the multiples of $p_{i}$, since if $\ker(\phi_{i})$ contains a non-multiple of $p_{i}$, then it contains the greatest common divisor of that non-multiple and $p_{i}$ (namely $1$). This would imply that $\ker(\phi_{i})$ is equal to $R$, which is impossible.

Assume that there is an element in both the ideal $\langle \mathcal{N}\rangle$ and the multiplicatively closed set generated by $\mathcal{B}\cup\mathbb{Z}$. Such an element is of the form $kf$, where $k$ is an integer, and $f$ is a product of polynomials from $\mathcal{B}$. Since $kf$ is in $\langle \mathcal{N}\rangle$, it is in each $\ker(\phi_{i})$, even though $f$ is not. Thus $k$ is in each ideal $\ker(\phi_{i})$. Thus $k$ is a multiple of each of the distinct primes $p_{1},p_{2},p_{3},\ldots$, and we have a contradiction. Now, by Lemma $1$, there is a prime ideal, $P$, of $R$ which contains $\langle \mathcal{N}\rangle$, and which avoids $\mathcal{B}\cup\mathbb{Z}$. Because $P$ is prime, the quotient ring, $R/P$, is an integral domain. Let $F$ be the field of fractions of $R/P$. The natural homomorphism from $R$ to $F$ gives us a representation of $M$. As $P$ does not contain any integer, it follows that $R/P$ has characteristic zero, and we are done. $\square$

The next proof of Theorem 1 makes use of the Compactness Theorem in first-order logic. It is due to Samuel Wagstaff and appeared two years after Vámos’s proof, in 1973 [7]. Wagstaff does not supply many details — perhaps the account in his PhD thesis (upon which the article based) is more explicit. But I believe that my version below captures his key ideas.

Proof 2. We construct a first-order language of vector spaces. We have a countable supply of variables, $x_{1},x_{2},x_{3},\ldots$, and unary predicates $\operatorname{Scal}$ and $\operatorname{Vec}$. In our interpretation, these predicates will indicate that a variable stands for a scalar or a vector. We also have constants, $0_{S}$, $1_{S}$, and $0_{V}$, which are interpreted as the identities of the vector space. The functions $+_{S}$, $\times_{S}$, $+_{V}$, and $\times_{V}$, are interpreted as the binary operations of the field of scalars, as addition of vectors, and as scalar multiplication. The only binary relation we need is equality. Now, in this language, we can express the axioms for fields and for vector spaces. To illustrate, the compatibility of scalar and vector multiplication would be expressed with the sentence \begin{multline*}\forall x_{1}\forall x_{2}\forall x_{3} (\operatorname{Scal}(x_{1})\land \operatorname{Scal}(x_{2})\land \operatorname{Vec}(x_{3}) \to\\ ((x_{1}\times_{S}x_{2})\times_{V}x_{3}=x_{1}\times_{V}(x_{2}\times_{V}x_{3}))).\end{multline*} We can assert the representability of $M$ by requiring that there exist $x_{1},x_{2},\ldots, x_{n}$ such that $\operatorname{Vec}(x_{i})$ holds for each $i$. For each subset $X\subseteq E(M)=\{1,\ldots, n\}$, we include a sentence asserting that the corresponding subset of $\{x_{1},x_{2},\ldots, x_{n}\}$ is linearly independent if $X$ is independent in $M$, and otherwise asserting that it is linearly dependent. Let us illustrate how this can be accomplished by writing the formula which asserts that $\{x_{1},x_{2},x_{3}\}$ is linearly independent. Let $y_{1}, y_{2}, y_{3}$ be variables that are not used elsewhere in our sentence. The formula we need is as follows: \begin{multline*}\forall y_{1}\forall y_{2}\forall y_{3} (\operatorname{Scal}(y_{1})\land \operatorname{Scal}(y_{2})\land \operatorname{Scal}(y_{3}) \land (y_{1}\ne 0_{S} \lor y_{2}\ne 0_{S} \lor y_{3}\ne 0_{S})\to\\ (y_{1}\times_{V}x_{1}) +_{V} (y_{2}\times_{V} x_{2}) +_{V} (y_{3}\times_{V}x_{3})\ne 0_{V}).\end{multline*} We simply perform this trick for each subset of $E(M)$.

Now we have a finite collection, $\mathcal{T}$, of sentences which can be satisfied if and only if $M$ is representable over a field. For each prime, $p$, let $S_{p}$ be the sentence asserting that the sum of $p$ copies of $1_{S}$ is equal to $0_{S}$. Thus $M$ is representable over a field of characteristic $p$ if and only if $\mathcal{T}\cup\{S_{p}\}$ can be satisfied. Assume that $M$ is not representable over a field with characteristic zero. Then the collection $\mathcal{T}\cup\{\neg S_{p}\colon p\ \text{is a prime}\}$ is inconsistent: it cannot be satisfied by any model. The Compactness Theorem tells us that there is a finite subcollection which is inconsistent. Therefore we can assume that $\mathcal{T}\cup\{\neg S_{p} \colon p\ \text{is a prime and}\ p\leq N\}$ has no model, for some integer $N$. This implies that there can be no representation of $M$ over a field with characteristic greater than $N$, so we have proved the contrapositive of Theorem 1. $\square$

The next proof appeared in 1989, and comes courtesy of Imre Leader [3]. I think it might be my favourite out of the four. It uses the notion of an ultraproduct.

Proof 3. Let $F_{1},F_{2},F_{3},\ldots$ be an infinite sequence of fields such that $M$ is representable over each $F_{i}$ and $\operatorname{char}(F_{i+1})>\operatorname{char}(F_{i})$. Let $\mathcal{U}$ be a non-principal ultrafilter of the positive integers. This means that $\mathcal{U}$ is a collection of subsets of positive integers, and $\mathcal{U}$ satisfies: (1) any superset of a member of $\mathcal{U}$ is also in $\mathcal{U}$; (2) if $U,V\in\mathcal{U}$, then $U\cap V\in \mathcal{U}$; and (3) if $U$ is any subset of $\mathbb{Z}^{+}$, then exactly one of $U$ or $\mathbb{Z}^{+}-U$ is in $\mathcal{U}$. Non-principal ultrafilters cannot be described explicitly, but we know that they exist by an application of Zorn’s Lemma. If $U$ is a finite subset of $\mathbb{Z}^{+}$, then $\mathbb{Z}^{+}-U$ is in $\mathcal{U}$. We consider sequences $(x_{1},x_{2},x_{3},\ldots)$, where each $x_{i}$ is an element of $F_{i}$. We declare $(x_{1},x_{2},x_{3},\ldots)$ and $(y_{1},y_{2},y_{3},\ldots)$ to be equivalent if $\{i\in\mathbb{Z}^{+}\colon x_{i}=y_{i}\}$ is a member of $\mathcal{U}$. We perform componentwise addition and multiplication on sequences. It is not too difficult to see that these operations respect our notion of equivalence, and that the equivalence classes of sequences form a field, $F$, under componentwise addition and multiplication. Moreover, the characteristic of $F$ is zero. We consider a sequence of representations of $M$ over the fields $F_{1},F_{2},F_{3},\ldots$. This leads to a representation of $M$ over $F$ in the obvious way: we simply “stack” the infinite sequence of matrices, and produce a matrix whose entries are infinite sequences of numbers. $\square$

Finally, we come full circle! In 2003, Vámos (along with Rosemary Baines) published another proof of Theorem 1 [2]. The proof is actually an easy consequence of the algorithm that Stefan mentioned in a previous post, and the main ingredient is the use of Gröbner bases. I will tweak the proof slightly, for the sake of simplicity.

Proof 4. Let $f$ be the product of all polynomials in $\mathcal{B}$. We introduce the new, “dummy”, variable, $y$. From now on, we will operate in the ring $\mathbb{Z}[X\cup\{y\}]$. Note that an evaluation of the variables in $X\cup\{y\}$ will make $yf-1$ zero if and only if it makes each polynomial in $\mathcal{B}$ non-zero. Let $I$ be the ideal of $\mathbb{Z}[X\cup\{y\}]$ that is generated by $\mathcal{N}\cup\{yf-1\}$. Thus a representation of $M$ is really a ring homomorphism from $\mathbb{Z}[X\cup\{y\}]$ to a field that takes every polynomial in $I$ to zero.

Let $G$ be a strong Gröbner basis of $I$ (see [1]). Thus $I$ is the ideal generated by $G$. In addition, we have an ordering on products of variables (the lexicographic order will suffice). The leading term of a polynomial is the highest non-zero term under this ordering. For $G$ to be a strong Gröbner basis, we require that if $h$ is in $I$, then there is a polynomial $g\in G$ such that the leading term of $g$ divides the leading term of $h$. Assume that $G$ contains an integer, $N$. If $\phi$ is a homomorphism from $\mathbb{Z}[X\cup\{y\}]$ to a field, $F$, such that $\ker(\phi)$ contains $I$, then $N$ is taken to zero by $\phi$. This means that the characteristic of $F$ is at most $N$, so $M$ is not representable over infinitely many prime characteristics. Therefore we will now assume that $G$ contains no integer.

Let $I_{\mathbb{Q}}$ be the ideal of $\mathbb{Q}[X\cup\{y\}]$ generated by $\mathcal{N}\cup\{yf-1\}$. Assume that $1\in I_{\mathbb{Q}}$. Then $1$ can be expressed as a polynomial combination of the polynomials in $\mathcal{N}\cup\{yf-1\}$. By multiplying this combination through by the denominators of the coefficients, we see that $I$ contains an integer, $N$. Thus $G$ contains a polynomial whose leading term divides the leading term of $N$, which is $N$ itself. But in the lexicographic ordering, a constant polynomial is below all non-constant polynomials, from which we deduce that $G$ contains a constant polynomial, contradicting our conclusion from the previous paragraph. Therefore $1\notin I_{\mathbb{Q}}$, which means that $I_{\mathbb{Q}}$ is contained in a maximal ideal, $P$. Note that $P$ contains no constant polynomial. Now $\mathbb{Q}[X\cup\{y\}]/P$ is a field, and the natural homomorphism from $\mathbb{Q}[X\cup\{y\}]$ to this field leads to a representation of $M$ over a field of characteristic zero. $\square$

References.

[1] W. W. Adams and P. Loustaunau. An introduction to Gröbner bases. Graduate Studies in Mathematics, 3. American Mathematical Society, Providence, RI, 1994.

[2] R. Baines and P. Vámos. An algorithm to compute the set of characteristics of a system of polynomial equations over the integers. J. Symbolic Comput. 35 (2003), no. 3, 269–279.

[3] I. Leader. A short proof of a theorem of Vámos on matroid representations. Discrete Math. 75 (1989), no. 1-3, 315–317.

[4] R. Rado. Note on independence functions. Proc. London Math. Soc. (3) 7 (1957), 300–320.

[5] P. Vámos. A necessary and sufficient condition for a matroid to be linear. Möbius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 162–169. Univ. Waterloo, Waterloo, Ont., 1971.

[6] P. Vámos. Linearity of matroids over division rings. Notes by G. Roulet. Möbius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 170–174. Univ. Waterloo, Waterloo, Ont., 1971.

[7] S. S. Wagstaff Jr. Infinite matroids. Trans. Amer. Math. Soc. 175 (1973), 141–153.

Partial Fields, III. Universal partial fields

I’ve talked about partial fields before here and, earlier, here. A quick refresher:

Definition 1. partial field is a pair $\mathbb{P} = (R,G)$ of a commutative ring $R$ and a subgroup $G$ of the invertible elements of $R$ such that $-1 \in G$.

Definition 2. A matrix $A$ over $R$ is a (strong) $\mathbb{P}$-matrix if every square submatrix has a determinant in $G\cup \{0\}$.

Definition 3. An $r\times n$ matrix $A$ over $R$ is a weak $\mathbb{P}$-matrix if every $r\times r$ square submatrix has a determinant in $G\cup \{0\}$, and at least one such matrix has nonzero determinant.

One can check that, if $D$ is a submatrix with nonzero determinant as in the latter definition, then $D^{-1}A$ represents the same matroid, and is a strong $\mathbb{P}$-matrix. The following was Theorem 10 in Part I:

Proposition 4. If $A$ is a weak $\mathbb{P}$-matrix with columns labeled by a set $E$, then $\mathcal{B} = \{ B \subseteq E : |B| = r, \det(A[B]) \neq 0\}$ is the set of bases of a matroid $M$, denoted $M = M[A]$.

Today, we are interested in the following question: given a matroid $M$, can we find a partial field $\mathbb{P}_M$ that is a “best fit” for $M$? The qualities we are looking for are:

  • $M$ is representable over $\mathbb{P}_M$;
  • We can find (information about) other representations of $M$;
  • We can compute (with) $\mathbb{P}_M$;
  • The representation of $M$ over $\mathbb{P}_M$ is unique.

The fourth property turns out to be impractical, but we can get the first three. This post is based on Section 4 of [PvZ10]; see also Section 3.3 of my thesis [vZ09].

Constructing the universal partial field

Let $M$ be a rank-$r$ matroid with ground set $E$. Fix a basis $B$ of $M$. First, let $D^\#$ be the $B$-fundamental-circuit incidence-matrix (see [Oxl11, p.182]). Recall that any representation of $M$ of the form $[I\ D]$ will have the same zero/nonzero pattern in $D$ as in $D^\#$, and that we can scale rows and columns of $D$ to make certain nonzero entries equal to $1$. Let $T$ be the set of coordinates of a maximal set of coordinates that we can scale to be $1$ (see [Oxl11, Theorem 6.4.7] for details).

Next, for each $x \in B$ and $y \in E-B$ introduce a variable $a_{xy}$; also introduce variables $i_{B’}$ for every basis $B’$ of $M$. Let $\mathcal{Y}$ be the set of all these variables, and consider the ring of polynomials $\mathbb{Z}[\mathcal{Y}]$. Let $\hat D$ be the $B\times (E-B)$ matrix with entries $a_{xy}$, and let $\hat A = [I\ \hat D]$.

Now consider the ideal $I_{M,B,T}$ in $\mathbb{Z}[\mathcal{Y}]$ generated by the following relations:

  • $\det(\hat A[Z])$ for all $r$-subsets $Z\subseteq E$ that are nonbases of $M$;
  • $\det(\hat A[Z])i_Z – 1$ for all bases $Z$ of $M$;
  •  $a_{xy} – 1$ for all $xy \in T$.

Finally, we set $\mathbb{B}_M = \mathbb{Z}[\mathcal{Y}] / I_{M,B,T}$ and the partial field

$$\mathbb{P}_M = (\mathbb{B}_M, \langle \{-1\}\cup \{ i_{B’} : B’ \text{ basis of } M\}\rangle),$$

where $\langle\cdot\rangle$ denotes “multiplicative group generated by”. Note that this formalism is nothing other than introducing notation for the steps you would already take to produce a representation of a given abstract matroid. We have the following nice properties (which I won’t prove):

Proposition 5. Let $M$ be a matroid and $\mathbb{P}_M$, $\hat A$, etc. as above.

  1. The partial field $\mathbb{P}_M$ does not depend on the choice of $B$ or $T$.
  2. If $\mathbb{P}_M$ is not the trivial partial field (that is, if $1 \neq 0$), then $M$ is represented over $\mathbb{P}_M$ by the image $A$ of $\hat A$ under the obvious map from $\mathbb{Z}[\mathcal{Y}] \to \mathbb{Z}[\mathcal{Y}] / I_{M,B,T}$.
  3. If $M$ is represented over a (partial) field $\mathbb{P}$ by a matrix $A’$, then there is a partial field homomorphism $\phi:\mathbb{P}_M\to\mathbb{P}$ with $\phi(A) = A’$.

Here a partial field homomorphism $\phi: (R_1, G_1) \to (R_2, G_2)$ is a ring homomorphism $\phi:R_1 \to R_2$ such that $\phi(G_1) \subseteq G_2$. Such homomorphisms preserve matroids, i.e. $M[A] = M[\phi(A)]$ if $A$ is a $\mathbb{P}$-matrix. This third property earns $\mathbb{P}_M$ the name universal partial field: every representation of $M$ can be obtained from it!

Computation: Baines and Vámos and the set of characteristics

The set of characteristics of a matroid is the subset of $\{p: p = 0$ or $p$ is prime $\}$ such that $M$ has a representation over some field of that characteristic. It is known that the set of characteristics can be any finite subset not containing 0, and any infinite subset containing 0 (see [Oxl11, Section 6.8]). In [BV03], Baines and Vámos gave an algorithm to compute the set of characteristics from the ideal $I_{M,B,T}$ defined above. A brief summary is as follows:

  1. Compute a Gröbner basis $G$ over the integers for $I_{M,B,T}$.
  2. If the $G$ contains 1, then $M$ is not representable.
  3. If the $G$ contains a constant $k > 1$, then the prime factors of $k$ are exactly the characteristics over which $M$ is representable.
  4. Otherwise, let $\gamma$ be the least common multiple of the leading coefficients of the polynomials in $G$. Compute the Gröbner basis for the ideal generated by $G \cup \{\gamma\}$, and let $k$ be its constant member. Then $M$ is representable over characteristic 0 and all prime characteristics, except those dividing $\gamma$ but not $k$.

Note that Gröbner basis computations are notoriously difficult to compute and can take up huge amounts of memory. But for small examples this works well. The Gröbner basis generates the same ideal as the one we started with, and these computations often give a simpler representation of the partial field.

Examples

The universal partial field of $\text{PG}(2,q)$ is $\text{GF}(q)$. The non-Fano matroid and $P_8$ both have the dyadic partial field as their universal partial field, as do the ternary Dowling geometries. The Betsy Ross matroid can be shown to yield the Golden Ratio partial field (that is, it’s representable over $\text{GF}(4)$ and $\text{GF}(5)$), and the matroid represented by the following diagram is representable over the partial field $\mathbb{P}_4$, and is the source of Conjecture 15 in Part I. The matroid was obtained from Gordon Royle, out of his database of matroids with up to 9 elements, through a certain query regarding matroids with only 1 representation over $\text{GF}(5)$.

p4-matroid

Related results and concepts

Many people have devoted attention to the theory of generic representations of a matroid. In [PvZ10] we discuss a construction of the universal partial field that does not rely on the choice of a special basis and scaling set. This construction is built on the idea of a bracket ring, introduced by White [Whi75], where we introduce a variable for each $r$-tuple of elements of $E$, followed by relations that make these $r$-tuples behave like determinants (alternating, 0 for repeated columns, 0 for nonbases, and relations encoding basis exchange). In addition to White’s construction we introduce symbols to make the bracket of each basis invertible.

Dress and Wenzel [DW89] introduce the Tutte Group, which again introduces a symbol for each basis, but only takes multiplicative relations into account. This group has received a considerable amount of attention. In particular the torsion of this group can give information on characteristics over which $M$ is not representable. Dress and Wenzel give a number of constructions of their group, based on various matroid axiomatizations.

Problems

I’ll conclude with some (computational) questions I’ve recently been asking myself.

  • Can we employ scaling techniques as in the definition of $\mathbb{P}_M$ to obtain a (quotient of the) Tutte-group that is faster to compute?
  • Can we combine computations of the Tutte-group with Gröbner basis techniques for a faster computation of the set of characteristics, or to determine whether $M$ is representable over any given finite field?

Unfortunately, $M$ is not always uniquely representable over $\mathbb{P}_M$ (up to partial field automorphisms, row- and column-scaling). The only obstacles I know involve partial fields $\mathbb{P}_M$ with an infinite set of cross ratios, such as the “near-regular-mod-2” partial field. Perhaps unique representability is recovered when the set of cross ratios is finite?

References

[BV03] R. Baines, P. Vámos, An algorithm to compute the set of characteristics of a system of polynomial equations over the integers. J. Symbolic Computat. 35, pp. 269-279 (2003).

[DW89] A.W.M. Dress, W. Wenzel, Geometric Algebra for Combinatorial Geometries. Adv. in Math. 77, pp. 1-36 (1989).

[Oxl11] J. Oxley, Matroid Theory. Second Edition. Oxford University Press (2011).

[PvZ10] R.A. Pendavingh, S.H.M. van Zwam, Confinement of matroid representations to subsets of partial fields. J. Comb. Th. Ser. B, vol. 100, pp. 510-545 (2010).

[Whi75] N.L. White. The bracket ring of a combinatorial geometry. I. Trans. Amer. Math. Soc. 214, pp. 233-248 (1975).

[vZ09] S.H.M. van Zwam, Partial Fields in Matroid TheoryPhD Thesis, Eindhoven University of Technology (2009).

 

A Taste of Tangles

Guest post by Tara Fife

This semester, I’ve been doing a reading course with Stefan van Zwam, the bulk of which involved reading interesting papers about tangles. This post highlights some of my favorite ideas so far. We start with an example that essentially comes from Reinhard Diestel and Geoff Whittle’s paper “Tangles and the Mona Lisa” [1]. The goal is to illustrate the intuition behind some of the definitions related to tangles. Precise definitions for connectivity systems and tangles as related to pictures can be found in [1]. Here is a picture of my brother Daniel and me on a ferry outside Seattle.

MeAndDan

If this picture were printed out and cut into two pieces, then we could sometimes decide that one piece was less important than the other. For instance, if we cut along the red lines below, it is clear that the center piece, while missing some of the beautiful scenery, is the important part of the picture from the perspective of capturing the human subjects of the picture.

MeAndDan2

If, however, we cut the picture with a squiggly cut, as below, then perhaps neither piece is unimportant. A connectivity system $K=(E(K),\lambda_K)$ consists of a finite set, $E(K)$, together with a connectivity function $\lambda _K:2^{E(K)}\rightarrow\mathbb{R}$ that gives us a way to rank the size of cuts. As such, we expect $\lambda_K(X)=\lambda_K(E(K)-X)$, for all subsets $X$ of $E(K)$. That is, we expect $\lambda_K$ to be symmetric. We also want our connectivity function to be submodular, that is, $\lambda_K(X)+\lambda_K(Y)\geq \lambda_K(X\cap Y)+\lambda_K(X\cup Y)$ for all subsets $X$ and $Y$ of $E(K)$. Any function which is symmetric and submodular is a connectivity function.

MeAndDan5

If $\lambda_1$ and $\lambda_2$ are connectivity functions on the same set, then it is straightforward to check that so is $\lambda_1+\lambda_2$ and, for a positive constant $c$, both $c\cdot\lambda_1$and $\lambda_1+c$. If $K=(E,\lambda_K)$ and $K’=(E,\lambda_{K’})$ are connectivity systems, then we say that $K’$ is a tie breaker if $\lambda_{K’}(X)\leq \lambda_{K’}(Y)$ whenever $\lambda_K(X)\leq \lambda_K(Y)$ and $\lambda_{K’}(X)\not=\lambda_{K’}(Y)$ unless $X=Y$ or $X=E-Y$. Geelen, Gerards, and Whittle’s “Tangles, tree-decompositions and grids in matroids” [2] proves the following.

Lemma 1 All connectivity functions have tie breakers.

Proof. Let $K=(E,\lambda)$ be a connectivity function. We can assume that $E=\{1, 2, \ldots, n\}$ Define $\lambda_L$ by $\lambda_L(X)=\sum_{i\in X}2^i$ for $X\subseteq {1, 2,\ldots, n-1}$, and $\lambda(X)=\lambda(E-X)$ for $X$ containing $n$. We need to show that $\lambda_L$ is submodular. If $X,Y\subseteq\{1, 2,\ldots, n-1\}$, then
\begin{align*}
\lambda(X)+\lambda(Y) & =\sum_{i\in X}2^i+\sum_{i\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X-Y}2^i+\sum_{i\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X\cup Y}2^i\\
& =\lambda_L(X\cap Y)+\lambda_L(X\cup Y).
\end{align*}

If $X\subseteq\{1,2,\ldots,n-1\}$ and $n\in Y$, then
\begin{align*}
\lambda(X)+\lambda(Y) & =\sum_{i\in X}2^i+\sum_{i\not\in Y}2^i=\sum_{i\in X\cap Y}2^i+\sum_{i\in X-Y}2^i+\sum_{i\not\in Y\cup X}2^i+\sum_{i\not\in X-Y}2^i\\
& \geq\sum_{i\in X\cap Y}2^i+\sum_{i\not\in X\cap Y}2^i=\lambda_L(X\cap Y)+\lambda_L(X\cup Y).
\end{align*}

If $n\in X$ and $n\in Y$, then
\begin{align*}
\lambda_L(X)+\lambda_L(Y) & =\lambda_L(E-X)+\lambda_L(E-Y)\\
& =\lambda_L((E-X)\cap(E-Y))+\lambda_L((E-X)\cup(E-Y))\\
& =\lambda_L(E-(X\cup Y))+\lambda_L(E-(X\cap Y)).
\end{align*}

Thus $\lambda_L$ is a connectivity function. Now let $\lambda'(X)=2^n\cdot\lambda(X)+\lambda_L(X)$. It is straightforward to check that $K’=(E,\lambda’)$ is a tie breaker for $K$.

$\square$

A tangle can be thought of as a collection $\mathcal{T}$ of less important (or small ) pieces. So far, we expect that the tangle should only make decisions about relatively simple cuts, and that the tangle should make a decision for all of the simple cuts. If we decide that the two pieces cut out of the picture below are both small, then we don’t want the part of the picture that is left to be contained in a small piece. More precisely, if $K$ is a connectivity system, then a collection $\mathcal{T}$ is a tangle of order $\theta$ in $K$ if

(T1)
$\lambda_K(A) < \theta$, for all $A \in \mathcal{T}$.
(T2)
For each separation $(A,B)$ of order less that $\theta$, either $A\in\mathcal{T}$ or $B\in\mathcal{T}$.
(T3)
If $A,B,C\in\mathcal{T}$, then $A\cup B\cup C \not=E(K)$.
(T4)
$E(K)-e$ is not in $\mathcal{T}$, for each $e\in E(K)$.

MeAndDan6

For some types of cuts, there might be different opinions about which part is less important. For instance, in the following picture, the matroid community would probably say that the part containing my brother was slightly less important, because the other half contains someone who at least knows the definition of a matroid, while my brother’s company would probably say that the part that contains me is slightly less important.

MeAndDan3

My mother would not consider either part unimportant, as we are both somewhat meaningful to her. Since the tangle induced by the opinion of the matroid community disagrees with the one induced by the opinion of Daniel’s company about which half of the separation above is less important, that separation is called a distinguishing separation. Since the tangle induced by my mother’s opinions (that is, a piece is only unimportant if it avoids me and avoids Daniel) is a subset of the matroid community tangle (where a piece is unimportant if it avoids me) and a subset of the company tangle (where a piece in unimportant if it avoids Daniel), it is called a truncation of either of them. That is, $\mathcal{T}’$ is a truncation of $\mathcal{T}$ if $\mathcal{T}’\subseteq\mathcal{T}$. If a tangle is not a proper truncation of another tangle, then it is a maximal tangle.

The above definition of a connectivity function includes the usual connectivity function of a matroid $M$, namely, $\lambda(X)=r(X)+r(E-X)-r(M)$. One of the main results of [2] gives us information about maximal tangles in a matroid. Before we state the theorem, we need to introduce a bit more notation. If $K=(E,\lambda)$ is a connectivity system, $T$ is a tree, and $\mathcal{P}$ a function from $E$ to $V(T)$, then we say that $(T,\mathcal{P})$ is a tree decomposition of $E$. For a subset $X$ of $V(T)$, we define $\mathcal{P}(X)=\{e:P(e)\in X\}$, and for a subtree $T’$ of $T$, we define $\mathcal{P}(T’)=\mathcal{P}(V(T’))$. We say that a separation $(A,B)$ of $K$ is displayed by $(T,\mathcal{P})$ if $A=\mathcal{P}(T’)$ for some subtree $T’$ of $V(T)$ obtained by deleting an edge of $T$ and letting $T’$ be one of the resulting connected components.The order if a separation $(A,B)$ is $\lambda(A)=\lambda(B)$.

Theorem 1

Let $K$ be a connectivity system, and let $\mathcal{T}_1,\mathcal{T}_2,\ldots,\mathcal{T}_n$ be maximal tangles in $K$. Then there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ with $V(T)=[n]$ such that the following hold.

  1. For each $i\in V(T)$ and $e\in E(T)$, if $T’$ is the component of $T-e$ containing $i$, then $\mathcal{P}(T’)$ is not in $\mathcal{T}_i$.
  2. For each pair of distinct vertices $i$ and $j$ of $T$, there is a minimum-order distinguishing separation for $\mathcal{T}_i$ and $\mathcal{T}_j$ displayed by $T$.

Before we sketch a proof of this theorem, we give an example that illustrates the statement of the theorem.

Alien2Consider the matroid, $M=([12],\mathcal{I})$ illustrated above. We first need to determine what the maximal tangles are. Let $S_1=\{9,10\}$, $S_2=\{11,12\}$, and $S_3=[8]$. We will show that an order-1 tangle of $M$ has the form the union of $\{S_i,S_j,(S_i\cup S_j)\}$ together with the set of singletons, where $i$ and $j$ are distinct members of $\{1,2,3\}$.

Let $\mathcal{T}$ be an order-1 tangle of $M$. The sets with connectivity 1 consist of the 12 singletons, their complements, and $S_1$, $S_2$, $S_3$, and their complements. By (T3), at most two of $S_1, S_2, S_3$ are in $\mathcal{T}$. Assume that $\{i,j,k\}=\{1,2,3\}$, and that $S_k$ is not in $\mathcal{T}$. Since $(S_i\cup S_j,S_k)$ is an order-1 separation of $M$, by (T2) $S_i\cup S_j$ is in $\mathcal{T}$. By (T3) (and the fact that there are at least 3 elements of $\mathcal{T}$), we get that neither $S_j\cup S_k$ nor $S_i\cup S_k$ is in $\mathcal{T}$, so by (T2), $S_i$ and $S_j$ are in $\mathcal{T}$.
Since singletons must all be in every tangle of order at least 1, the result follows.

The sets with connectivity 2 either contain $\{1,2,3,4\}$ and avoid $\{5,6,7,8\}$ or contain $\{5,6,7,8\}$ and avoid $\{1,2,3,4\}$. Arguing as above, we get that that the order-2 tangles of $M$ are $\{X:\lambda(X)\leq 2 \text{ and } S\not\subseteq X\}$ for $S\in\{\{1,2,3,4\}, \{5,6,7,8\}\}$. We note that the order-1 tangle where $\{S_i,S_j\}=\{\{1,2,3,4\},\{5,6,7,8\}\}$ is a truncation of both of the order-2 tangles, and that the other order-1 tangles can be represented as $\{X:\lambda(X)\leq 1 \text{ and } \{1,2, 3, 4\}\not\subseteq X\}$ and $\{X:\lambda(X)\leq 1 \text{ and } \{5,6, 7, 8\}\not\subseteq X\}$. Since there are no separations of order-3 or more in $M$, the four maximal tangles of $M$ are $\mathcal{T}_S=\{X:\lambda(X)\leq \lambda(S) \text{ and } S\not\subseteq X\}$, for $S\in\{\{1,2,3,4\},\{5,6,7,8\},\{9,10\},\{11,12\}\}$. For $S \in \{\{1,2,3,4\}, \{9,10\},\{11,12\}\}$, a minimum-order distinguishing separation for $\mathcal{T}_S$ and $\mathcal{T}_{S’}$ is $(S,[12]-S)$, which is displayed by the tree, $T$, below.

AlienTree1The above argument showing that if $S_i\cup S_j$ is in $\mathcal{T}$, then each of $S_i$ and $S_j$ are in $\mathcal{T}$, can be generalized to show the following.

Lemma 2

If $A$ is in a tangle, $\mathcal{T}$ of $K$ of order $\theta$, and $B\subseteq A$ with $\lambda_K(B)\leq\theta$, then $B\in\mathcal{T}$.

To prove Theorem 1, we actually prove the following slightly stronger result also from [2].

Theorem 2

Let $K$ be a connectivity system, and let $\mathcal{T}_1,\mathcal{T}_2,\ldots,\mathcal{T}_n$ be tangles in $K$, none a truncation of another. Then there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ with $V(T)=[n]$ such that the following hold.

  1. For each $i\in V(T)$ and $e\in E(T)$, if $T’$ is the component of $T-e$ containing $i$, then $\mathcal{P}(T’)$ is not in $\mathcal{T}_i$.
  2. For each pair of distinct vertices $i$ and $j$ of $T$, there is a minimum-order distinguishing separation for $\mathcal{T}_i$ and $\mathcal{T}_j$ displayed by $T$.

Proof Sketch
If $K$ is a connectivity system and $K’$ is a tie breaker for $K$, then it is easy to see that a tangle $\mathcal{T}$ of $K$ is also a tangle of $K’$, so it is safe to assume that $K$ is its own tie breaker.

Since $K$ is its own tie breaker, for each distinct $i$ and $j$ in $[n]$, there is a minimum-order separation $(X_{ij},Y_{ij})$ of $K$ distinguishing $\mathcal{T}_i$ and $\mathcal{T}_j$, where $X_{ij}\in\mathcal{T}_i$. Using some well known results (whose statements require terminology which we haven’t introduced), it can be show that there is a tree decomposition $(T,\mathcal{P})$ of $E(K)$ such that each separation $(X_{ij},Y_{ij})$ is displayed by $(T,\mathcal{P})$, that these are the only separations displayed by $(T,\mathcal{P})$, and that each edge of $T$ displays a proper and distinct separation. It remains to show that there is a bijection from $\{\mathcal{T}_1,\ldots,\mathcal{T}_n\}$ to the vertices of $T$ satisfying the conclusion of Theorem 2.

For $i\in[n]$, let $\chi_i$ be the set of subsets $X$ of $V(T)$ such that $E(K)-\mathcal{P}[X]\in\mathcal{T}_i$ and such that $(E(K)-\mathcal{P}[X],\mathcal{P}[X])$ is displayed by $(T,\mathcal{P})$. Each member of $\chi_i$ induces a sub-tree of $T$, and, by (T3), each two members of $\chi_i$ intersect, so the intersection of the members of $\chi_i$ is non-empty. Call this intersection $V_i$. Each edge of $T$ that leaves $V_i$ displays a separation $(A,B)$ with $\mathcal{P}[V_i]\subseteq A$ and $B\in\mathcal{T}_i$. The proof concludes by showing that the $V_i$’s partition the vertices of $T$ into singletons, since this shows that $|V(T)|=n$, and since vertices in $V_i$ satisfy the condition (1) of the theorem.

For each $i\not=j$, the set $\mathcal(V_i)$ is in $Y_{ij}$ and the set $\mathcal(V_j)$ is in $Y_{ji}=X_{ij}$, so the sets $V_1, \ldots, V_n$ are disjoint.

Suppose that $w\in V_i$. We need to show that $\{w\}=V_i$. Choose the edge $e$ incident with $w$ that displays the separation $(X_{ij},Y_{ij})$ of strictly largest order. Since we are assuming that $K$ is its own tie breaker, there is a strictly largest order. Now, each of the other edges incident with $w$ displays a separation of order less than the order displayed by $e$, and hence, less than the orders of $\mathcal{T}_i$ and $\mathcal{T}_j$. Then, by the definition of $(X_{ij},Y_{ij})$, none of these separations distinguish $\mathcal{T}_i$ and $\mathcal{T}_j$. By the definition of $V_i$ and the fact that $X_{ij}$ is in $\mathcal{T}_i$, we know that $\mathcal{P}(w)$ is not a subset of $X_{ij}$ so it is a subset of $Y_{ij}$. Then by Lemma 2, for each of the separations induced by edges other than $e$ incident to $w$, the set not containing $\mathcal{P}(w)$ is in $\mathcal{T}_j$, and hence it is in $\mathcal{T_i}$. Thus, $V_i=\{w\}$.
$\square$

The complete details of the last proof can be found in [2] along with a corollary which bounds the number of maximal tangles.

As hinted at in the example, tangles can end up pointing to “highly” connected regions of the matroid. This is useful in structure theory because the highly connected regions usually contain the structure that we care about, and a tangle can be used to identify where deletions and contractions can be made while preserving the structure. This idea is utilized, for example, in [3, 4]. Tangles in general grew out of a definition for tangles of graphs, which were used to prove that finite graphs are well quasi ordered.

References

[1] R. Diestel, and G. Whittle, Tangles and the Mona Lisa, arXiv:1603.06652v2 [math.CO]

[2] J. Geelen, B. Gerards, and G. Whittle, Tangles, tree-decompositions and grids in matroids, J. Combin. Theory Ser. B 99 (2009) 657-667

[3] J. Geelen, and S. van Zwam, Matroid 3-connectivity and branch width, arXiv:1107.3914v2 [math.CO]

[4] P. Nelson, and S. van Zwam, Matroids representable over fields with a common subfield, arXiv:1401.7040v1 [math.CO]

[5] N. Robertson and P. D. Seymour, Graph minors, X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B, 52(2):153-190, 1991.

$P_{8}^{=}$ is not a gammoid

Guest post by Joe Bonin.

In his talk at the recent workshop in Eindhoven, Immanuel Albrecht noted that each matroid in the appendix of examples in James Oxley’s book Matroid Theory is designated as either being a gammoid or not, except for $P_8^=$. In this post, we show that $P_8^=$ is not a gammoid. The ideas used may apply more widely.

Transversal and cotransversal matroids

Gammoids are minors of transversal matroids, so in this section, we sketch the items about transversal matroids and their duals that we use. Those who know the characterization of transversal and cotransversal matroids in Theorems 2 and 3 might prefer to omit this introductory section.

We start with a bipartite graph with vertex classes $S$ and $T$. We will use the example below, with $S=\{a,b,c,d,s,t,u\}$.

Figure 1

A partial transversal is a subset of $S$, such as $\{a,b,u\}$ above, that can be matched with a subset of the vertices in $T$ via edges in the graph. The partial transversals are the independent sets of the resulting transversal matroid.

For $X\subseteq S$, let $N_G(X)$ denote the set of neighbors of $X$ in $G$, that is,
$$N_G(X) = \{v\in T\,:\, v \text{ is adjacent to at least one } x\in X\}.$$ A set $X$ in a matroid $M$ is cyclic if $X$ is a union of circuits, that is, $M|X$ has no coloops. The cyclic flats in the example are $\emptyset$, $\{a,c,s,t\}$, $\{b,d,t,u\}$, $\{a,d,s,u\}$, $\{b,c,s,u\}$, and $S$. In this example, the rank of each cyclic flat ($0$, $3$, $3$, $3$, $3$, and $4$, respectively) is its number of neighbors. This illustrates the lemma below.

Lemma 1. Let $G$ be a bipartite graph on $S\cup T$ that represents $M$. If $X$ is a cyclic set of rank $k$ in $M$, then $|N_G(X)|=k$.

Proof. A basis of $X$ can be matched to the vertices in some $k$-element subset $T’$ of $T$. Let $G’$ be the induced subgraph of $G$ on $S\cup T’$, so $G’$ gives a rank-$k$ transversal matroid $M’$ on $S$, and $r_{M’}(X)=k$.

We first show that $M’|X=M|X$. Independent sets in $M’|X$ are independent in $M|X$. If the converse failed, then some circuit $C$ of $M’|X$ would be independent in $M|X$. Since $C$ can be matched in $G$ but not in $G’$, some $a\in C$ is adjacent to a vertex $v\in T-T’$. Extend $C-a$ to a basis $B$ of $M’|X$. Now $r_{M’}(X)=k$, so matching $B$ with the vertices in $T’$ and $a$ with $v$ gives the contradiction $r_M(X)>k$. Thus, $M’|X=M|X$.

We now get that $N_G(X)=T’$, for if instead some $b\in X$ were adjacent to some vertex $v\in T-T’$, then the same type of matching argument, using a basis $B$ of $M|X$ with $b\not\in B$ (which exists since $b$ is not a coloop of $M|X=M’|X$), would yield a contradiction. Thus, $|N_G(X)|=k$. $\square$

This proof adapts to show that we can always choose $G$ so that $|T|=r(M)$.

The bipartite graph $G$ on $S\cup T$ is an induced subgraph of a bipartite graph $G’$ on $S’\cup T$ in which, for each $x\in T$, there is a $y\in S’$ with $N_{G’}(y)=\{x\}$. Such an extension of our example above is shown below; the red vertices have been added.

The bipartite graph $G$ on $S\cup T$ is an induced subgraph of a bipartite graph $G’$ on $S’\cup T$ in which, for each $x\in T$, there is a $y\in S’$ with $N_{G’}(y)=\{x\}$. Such an extension of our example above is shown below; the red vertices have been added.

Figure 2

The resulting matroid $M’$ is an extension of $M$.

Pick a subset $B$ of $S’$ (for example, the red and green vertices above) for which, for each $x\in T$, there is one $y\in B$ with $N_{G’}(y)=\{x\}$. Clearly $B$ is a basis of $M’$. Moreover, if $X$ is a cyclic flat of $M’$, then $X\cap B$ is a basis of $X$ since $r(X) = |N_{G’}(X)|$ by Lemma 1, so the flat $X$ must contain the elements of $B$ that are adjacent to the vertices in $N_{G’}(X)$. Thus, $r_{M’}(X) = |X\cap B|$. It is not hard to show, more generally, that for any cyclic flats $X_1,X_2,\ldots,X_n$ of $M’$,
\begin{equation*}
r_{M’}(X_1\cup X_2\cup \cdots \cup X_n )= \bigl|B\cap (X_1\cup X_2\cup
\cdots \cup X_n)\bigl|
\end{equation*}
and
\begin{equation*}
r_{M’}(X_1\cap X_2\cap \cdots \cap X_n) = \bigl|B\cap (X_1\cap X_2\cap
\cdots \cap X_n)\bigr|.
\end{equation*}
From these equations and inclusion/exclusion, it follows that
\begin{equation*}
r_{M’}(X_1\cap X_2\cap \cdots \cap X_n) =
\sum_{J\subseteq[n]} (-1)^{|J|+1}r_{M’}\bigl(\bigcup_{j\in J}X_j\bigr).
\end{equation*}

A transversal matroid might not have the type of basis that we used to derive the equalities above, but we do get the inequality in Theorem 2 below. To see this, delete $S’-S$ to get the original transversal matroid $M$. The rank of unions of cyclic flats of $M$ are the same as for their closures in $M’$, but the rank of intersections may be less. This proves the half of Theorem 2 that we will use. (For a proof of the converse, see [1].) John Mason proved this result for cyclic sets and Aubrey Ingleton refined it to cyclic flats. We let $\cup\mathcal{F}$ denote the union of a family of sets, and we use $\cap\mathcal{F}$ similarly.

Theorem 2. A matroid $M$ is transversal if and only if for all nonempty sets $\mathcal{A}$ of cyclic flats of $M$,
\begin{equation*}
r(\cap\mathcal{A})\leq \sum_{\mathcal{F}\subseteq \mathcal{A}} (-1)^{|\mathcal{F}|+1} r(\cup\mathcal{F}).
\end{equation*}

We will use the dual of this result, which we state next. Duals of transversal matroids are called cotransversal matroids or strict gammoids.

Theorem 3. A matroid $M$ is cotransversal if and only if for all sets $\mathcal{A}$ of cyclic flats of $M$,
\begin{equation}
r(\cup \mathcal{A}) \leq \sum_{\mathcal{F}\subseteq \mathcal{A}\,:\,\mathcal{F}\ne\emptyset}
(-1)^{|\mathcal{F}|+1}r(\cap \mathcal{F}).\qquad\qquad (1)
\end{equation}

Gammoids and $P_8^=$

Restrictions of transversal matroids are transversal, so any gammoid (a minor of a transversal matroid) is a contraction of a transversal matroid. The set we contract can be taken to be independent since $M/X =M\backslash (X-B)/B$ if $B$ is a basis of $M|X$, so any gammoid is a nullity-preserving contraction of a transversal matroid. The class of gammoids is closed under duality, so we get Lemma 4 below.

Lemma 4. Any gammoid has a rank-preserving extension to a cotransversal matroid.

Because of this lemma, below we focus exclusively on extensions that are rank-preserving.

We will also use the corollary below of the following theorem of Ingleton and Piff [2].

Theorem 5. A matroid of rank at most three is a gammoid if and only if it is cotransversal.

Corollary 6. Let $M$ be a rank-$r$ matroid with $r\geq 3$. If $H_1$, $H_2$, $H_3$, and $H_4$ are cyclic hyperplanes, any two of which intersect in a flat of rank $r-2$, and each set of three or four intersects in a flat $X$ of rank $r-3$, then $M$ is not a gammoid.

Proof. In $M/X$, the sets $H_i-X$, for $1\leq i\leq 4$, are cyclic lines. (Contraction does not create coloops.) The rank of the union of these four cyclic lines is $3$, but the alternating sum in inequality (1) is $4\cdot 2 – 6\cdot 1 = 2$, so $M/X$ is not cotransversal by Theorem 3. Thus, since $r(M/X)=3$, it is not a gammoid by Theorem 5, so $M$ is not a gammoid. $\square$

To show that $P_8^=$ is not a gammoid, we focus on a particular failure of inequality (1) in $P_8^=$ and show that between $P_8^=$ and any extension $M’$ of $P_8^=$ in which the counterpart of that particular inequality holds, we have a single-element extension of $P_8^=$ to which Corollary 6 applies. Thus, any such $M’$ has a restriction that is not a gammoid, so $M’$ is not cotransversal, and so $P_8^=$ is not a gammoid by Lemma 4.

To define $P_8^=$, we first briefly discuss $P_8$, which we get by placing points at the vertices of a cube and twisting the top of the cube an eighth turn. Label the points in the top and bottom planes of $P_8$ as shown below (the second diagram shows the view from above). We get $P_8^=$ by from $P_8$ by relaxing the circuit-hyperplanes $\{a,b,c,d\}$ and $\{s,t,u,v\}$.

Figure 3

From this, we see that the cyclic flats of $P_8^=$, besides the empty set and the whole set, are the following planes. In each, we put what we call its diagonal in bold.
$$\{\mathbf{a},\mathbf{c},u,v\}
\quad\{\mathbf{a},\mathbf{c},s,t\} \quad
\{\mathbf{b},\mathbf{d},s,v\}\quad
\{\mathbf{b},\mathbf{d},t,u\}$$
$$\{a,b,\mathbf{t},\mathbf{v}\}
\quad\{c,d,\mathbf{t},\mathbf{v}\}\quad
\{a,d,\mathbf{s},\mathbf{u}\}\quad
\{b,c,\mathbf{s},\mathbf{u}\}$$

Observe that each cyclic plane $X$ intersects five others in exactly two points (this includes all four cyclic planes that are not in the same row as $X$), and the remaining two cyclic planes in one point each (and those are different points). Thus, the number of sets of two cyclic planes that intersect in two points is $8\cdot 5/2 = 20$, and the number of sets of two cyclic planes that intersect in a single point is $8\cdot 2/2 = 8$. No triple of cyclic planes intersects in two points. Also, each point is in exactly four cyclic planes, so the number of sets of three planes that intersect in a singleton is $8\cdot 4=32$, and the number of sets of four points that intersect in a singleton is $8$.

Let $\mathcal{A}$ be the set of all eight cyclic planes. The term on the left side of inequality (1) is $4$. On the right side, the counting in the previous paragraph gives $$8\cdot 3 – 20\cdot 2 -8 + 32 -8 = 0.$$ Thus, inequality (1) fails.

Let $M’$ be a rank-preserving extension of $P_8^=$ in which the counterpart of this instance of inequality (1) holds. (If there is no such $M’$, then $P_8^=$ is not a gammoid, as we aim to show.) Think of constructing $M’$ by a sequence of single-element extensions. If each of these single-element extensions added a point to at most two of the cyclic planes of $P_8^=$, or parallel to a point of $P_8^=$, then the counterpart of this instance of inequality (1) would fail; thus, not all extensions are of these types. Focus on one point, say $e$, that is added to at least three cyclic planes of $P_8^=$ and not parallel to an element of $P_8^=$, and consider the single-element extension of $P_8^=$ formed by restricting $M’$ to $E(P_8^=)\cup e$. We show that, up to symmetry, there are only two such single-element extensions of $P_8^=$. As we see below, in both options, $e$ is added to exactly three cyclic planes, not more.

First consider adding $e$ to two cyclic planes that have the same diagonal, say, by symmetry, $\{a,c,u,v\}$ and $\{a,c,s,t\}$. We cannot add $e$ to $\{a,b,t,v\}$ since this plane intersects the other two in lines that share a point: adding $e$ to all three planes would give $r(\{a,v,e\})=2=r(\{a,t,e\})$, so either $e$ is parallel to $a$ (which we discarded) or $\{a,t,v\}$ would be a $3$-circuit, contrary to the structure of $P_8^=$. Similar reasoning eliminates adding $e$ to any plane in the second row. The only candidates left are $\{b,d,s,v\}$ and $\{b,d,t,u\}$, and we cannot add $e$ to both since then $\{a,c,e\}$ and $\{b,d,e\}$ would be lines that intersect in $e$, but $a,b,c,d$ are not coplanar.

Now assume that no two planes to which we add $e$ have the same diagonal. We must have a pair of sets in the same row but with different diagonals; by symmetry, we can use $\{a,c,u,v\}$ and $\{b,d,s,v\}$. An argument like the one above shows that the only other planes to which we can add $e$ are $\{a,d,s,u\}$ or $\{b,c,s,u\}$, and we cannot add $e$ to both since they have the same diagonal.

Thus, between $P_8^=$ and $M’$ we have a single-element extension $M$ of $P_8^=$ in which a point $e$ is added to exactly three of the original cyclic planes. By the argument above, up to symmetry, there are two cases to consider: the extended cyclic planes are either

  1. $\{a,c,u,v,e\}$,  $\{a,c,s,t,e\}$,  and $\{b,d,s,v,e\}$,  or
  2. $\{a,c,u,v,e\}$, $\{b,d,s,v,e\}$, and $\{a,d,s,u,e\}$.

In either case, the cyclic planes of $M$ that contain $v$, that is, $$\{a,c,u,v,e\}, \quad \{b,d,s,v,e\},\quad \{a,b,t,v\}, \quad\{c,d,t,v\},$$ satisfy the hypothesis of Lemma 6, so $M$ is not a gammoid. Thus, no coextension of $M$ is cotransversal, so $P_8^=$ is not a gammoid. Indeed, we have the result below.

Proposition 7. The matroid $P_8^=$ is an excluded minor for the class of gammoids.

To prove this, first check that $P_8^=$ is self-dual. With that and the symmetry of $P_8^=$, it suffices to check that $P_8^=\backslash v$ is a gammoid. One can check that it is the transversal matroid in our example in the introductory section.

References

[1] J. Bonin, J.P.S. Kung, and A. de Mier, Characterizations of transversal and fundamental transversal matroids, Electron. J. Combin. 18 (2011) #P106.

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