# 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)$.

## 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.

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.

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.

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)$.

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.

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.

Consider 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.

The 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\}$.

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.

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$,

r(\cup \mathcal{A}) \leq \sum_{\mathcal{F}\subseteq \mathcal{A}\,:\,\mathcal{F}\ne\emptyset}

# 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\}$.

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.

# The number of representable matroids

Hello everyone – MatroidUnion is back!

Rudi and Jorn wrote a nice post earlier this year about questions in asymptotic matroid theory, and beautiful new results they’ve obtained in this area. While reading one of their papers on this topic, I saw that they restated the conjecture that almost all matroids on $n$ elements are non-representable. This was first explicitly written down by Mayhew, Newman, Welsh and Whittle [1] but earlier alluded to by Brylawski and Kelly [2] (in fact, the latter authors claim that the problem is an ‘exercise in random matroids’ but give no clue how to complete it). Indeed I would argue that most of us would independently come up with the same conjecture after thinking about these questions for a few minutes; surely representable matroids are vanishingly rare among all matroids!

In any case, reading this conjecture reminded me that, like many ‘obvious’ statements in asymptotic matroid theory it was still open, and seemed somewhat hard to approach with existing techniques. I’m happy to say that this is no longer the case; as it happened, I discovered a short proof that I will now give in this post. The proof is also on the arXiv [3]; there, it is written with the bounds as tight as possible. Here, I will relax the calculations a little here to make the proof more accessible, as well as using more elementary bounds so the entire argument is self-contained. The theorem we prove is the following:

Theorem: For $n \ge 10$, the number of representable matroids with ground set $[n] = \{1,\dotsc,n\}$ is at most $2^{2n^3}$.

The number of matroids on $n$ elements is well-known to be doubly exponential in $n$, so the above gives the ‘almost all’ statement we need, in fact confirming the intuition that representable matroids are extremely rare among matroids in general. The bound in the proof can in fact be improved to something of the form $2^{n^3(1/4 + o(1))}$, and I believe the true count has this form; see [3] for more of a discussion.

Our path to the proof is indirect; we proceed by considering a more general question on `zero-patterns’ of polynomials, in the vein of [4]. Let $f_1, \dotsc, f_N$ be integer polynomials in variables $x_1, \dotsc, x_m$. Write $\|f\|$ for the absolute value of the largest coefficient of a polynomial $f$, which we call its height; it is fairly easy to prove that $\|f + g\| \le \|f\| + \|g\|$ and that $\|fg\| \le \binom{\deg(f) + \deg(g)}{\deg(f)} \|f\|\ \|g\|$ for all $f$ and $g$. We will map these polynomials to various fields; for a field $\mathbb{K}$ and a polynomial $f$, write $f^{\mathbb{K}}$ for the polynomial in $\mathbb{K}[x_1, \dotsc, x_m]$ obtained by mapping each coefficient of $f$ to an element of $\mathbb{K}$ using the natural homomorphism $\phi\colon \mathbb{Z} \to \mathbb{K}$.

Given a field $\mathbb{K}$ and some $u_1, \dotsc, u_m \in \mathbb{K}$, the polynomials $f_i^{\mathbb{K}}(u_1, \dotsc, u_m)$ all take values in $\mathbb{K}$, and in general some will be zero and some nonzero in $\mathbb{K}$. We are interested in the number of different ways this can happen, where we allow both the field $\mathbb{K}$ and the $u_j$ to be chosen arbitrarily; to this end, we say a set $S \subseteq [N]$ is \realisable with respect to the polynomials $f_1, \dotsc, f_N$ if there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that $S = \{i \in [N]: f^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}.$ In other words, $S$ is realisable if and only if, after mapping to some field and substituting some values into the arguments, $S$ is the support of the list $f_1, \dotsc, f_N$. We will get to the matroid application in a minute; for now, we prove a lemma that bounds the number of different realisable sets:

Lemma: Let $c,d$ be integers and let $f_1, \dotsc, f_N$ be integer polynomials in $x_1, \dotsc, x_m$ with $\deg(f_i) \le d$ and $\|f_i\| \le c$ for all $i$. If an integer $k$ satisfies
$2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}},$ then there are at most $k$ realisable sets for $(f_1, \dotsc, f_N)$.

Proof: If not, then there are distinct realisable sets $S_1, \dotsc, S_k \subseteq [N]$. For each $i \in [k]$, define a polynomial $g_i$ by $g_i(x_1, \dotsc, x_m) = \prod_{j \in S_i}f_j(x)$. Clearly $\deg(g_i) \le Nd$, and since each $g_i$ is the product of at most $N$ different $f_i$, we use our upper bound on the product of heights to get
$\|g_i\| \le c^N \binom{dN}{d}^N (2kc’)^D$, so we have a collision – there exist distinct sets $I,I’ \subseteq [k]$ such that $g_I = g_I’$. By removing common elements we can assume that $I$ and $I’$ are disjoint.

Let $\ell \in I \cup I’$ be chosen so that $|S_{\ell}|$ is as small as possible. We can assume that $\ell \in I$. Since the set $S_{\ell}$ is realisable, there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that $S_{\ell} = \{i \in [N]: f_{\ell}^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}$. So $g^{\mathbb{K}}_{\ell}$, by its definition, is the product of nonzero elements of $\mathbb{K}$, so is nonzero. For each $t \in I \cup I’ – \{\ell\}$, on the other hand, since $|S_t| \ge |S_\ell|$ and $S_t \ne S_\ell$ there is some $j \in S_t – S_\ell$, which implies that the zero term $f^{\mathbb{K}}_j(u_1, \dotsc, u_m)$ shows up in the product $g^{\mathbb{K}}_t(u_1, \dotsc, u_m)$. It follows from these two observations that
$0_{\mathbb{K}} \ne g^{\mathbb{K}}_I(u_1, \dotsc, u_m) = g^{\mathbb{K}}_{I’}(u_1, \dotsc, u_m) = 0_{\mathbb{K}},$ which is a contradiction.

Why is this relevant to representable matroids? Because representing a rank-$r$ matroid $M$ with ground set $[n]$ is equivalent to finding an $r \times n$ matrix $[x_{i,j}]$ over some field, for which the $r \times r$ determinants corresponding to bases of $M$ are nonzero and the other determinants are zero. In other words, a matroid $M$ is representable if and only if the set $\mathcal{B}$ of bases of $M$ is realisable with respect to the polynomials $(f_A \colon A \in \binom{[n]}{r})$, where $f_A$ is the integer polynomial in the $rn$ variables $[x_{ij} \colon i \in [r],j \in [n]]$ that is the determinant of the $r \times r$ submatrix of $[x_{ij}]$ with column set $A$. Thus, the number of rank-$r$ representable matroids on $n$ elements is the number of realisable sets with respect to these $f_A$.

To bound this quantity, we apply the Lemma, for which we need to understand the parameters $N,m,a,d$. Now $m = rn \le n^2$ is just the number of variables. $N = \binom{n}{r} \le 2^n$ is the number of $r \times r$ submatrices. (We can in fact assume that $N = 2^n$ and $m = n^2$ by introducing dummy polynomials and variables). Finally, since the $f_A$ are determinants, we have $\deg(f_A) = r \le n$ and $\|f_A\| = 1$ for all $a$, so $(N,m,c,d) = (2^n,n^2,1,n)$ will do. To apply the lemma, it suffices to find a $k$ for which
$2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}},$ or in other words, $k > N\binom{Nd+m}{m}\log_2(2kc(dN)^d)).$ If you are happy to believe that $k = 2^{2n^3}/2n$ satisfies this, then you can skip the next two estimates, but for the sticklers among us, here they are:
Using $(N,m,d,c) = (2^n,n^2,n,1)$ and $n \ge 20$ we have $N\binom{Nd+m}{m} \le 2^n(2^{n+1}n)^{n^2} = 2^{n^2(n+1 + \log_2(n)) + n} \le 2^{2n^3}/6n^4.$ (Here we need that $n^3 > n^2(1+\log_2 n) + n + \log_2(6n^4)$, which holds for $n \ge 10$.) Similarly, for $k = 2^{2n^3}/(2n)$ we have $2kc < 2^{2n^3}$, so
$\log_2(2kc(dN)^d)) < \log_2(2^{2n^3}(n2^n)^n) < 2n^3 + n^2 + n \log_2 n < 3n^3.$ Combining these estimates, we see that $k = 2^{2n^3}/2n$ satisfies the hypotheses of the lemma, so this $k$ is an upper bound on the number of rank-$r$ representable matroids on $n$ elements. This is only a valid bound for each particular $r$, but that is what our extra factor of $2n$ was for; the rank $r$ can take at most $n+1$ values, so the number of representable matroids on $[n]$ in total is at most $(n+1)k < 2nk = 2^{2n^3}$. This completes the proof of the main theorem.

[1] D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, European J. Combin. 32 (2011), 882-890.
[2] T. Brylawski and D. Kelly, Matroids and combinatorial geometries, University of North Carolina Department of Mathematics, Chapel Hill, N.C. (1980). Carolina Lecture Series
[3] P. Nelson, Almost all matroids are non-representable, arXiv:1605.04288 [math.CO]
[4] L. Rónyai, L. Babai and M. K. Ganapathy, On the number of zero-patterns of a sequence of polynomials, J. Amer. Math. Soc. 14 (2001), 717–735.