Clutters I

I have been trying to firm up my feeling for the theory of clutters. To that end, I have been working through proofs of some elementary lemmas. For my future use, as much as anything else, I will post some of that material here.

A clutter is a pair $H=(S,\mathcal{A})$, where $S$ is a finite set, and $\mathcal{A}$ is a collection of subsets of $S$ satisfying the constraint that $A,A’\in\mathcal{A}$ implies $A\not\subset A’$. In other words, a clutter is a hypergraph satisfying the constraint that no edge is properly contained in another. For this reason we will say that the members of $\mathcal{A}$ are edges of $H$. Clutters are also known as Sperner families, because of Sperner’s result establishing that if $|S|=n$, then
\[\mathcal{A}\leq \binom{n}{\lfloor n/2\rfloor}.\]

Clutters abound in ‘nature': the circuits, bases, or hyperplanes in a matroid; the edge-sets of Hamilton cycles, spanning trees, or $s$-$t$ paths in a graph. Even a simple (loopless with no parallel edges) graph may be considered as a clutter: just consider each edge of the graph to be a set of two vertices, and in this way an edge of the clutter. There is one example that is particularly important for this audience: let $M$ be a matroid on the ground set $E$ with $\mathcal{C}(M)$ as its family of circuits, and let $e$ be an element of $E$. We define $\operatorname{Port}(M,e)$ to be the clutter
\[(E-e,\{C-e\colon e\in C\in \mathcal{C}(M)\})\]
and such a clutter is said to be a matroid port.

If $H=(S,\mathcal{A})$ is a clutter, then we define the blocker of $H$ (denoted by $b(H)$) as follows: $b(H)$ is a clutter on the set $S$, and the edges of $b(M)$ are the minimal members of the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$. Thus a subset of $S$ is an edge of $b(H)$ if and only if it is a minimal subset that has non-empty intersection with every edge of $H$. Note that if $\mathcal{A}=\{\}$, then vacuously, $|X\cap A|\geq 1$ for all $A\in \mathcal{A}$, no matter what $X$ is. The minimal $X\subseteq S$ is the empty set, so $b((S,\{\}))$ should be $(S,\{\emptyset\})$. Similarly, if $\mathcal{A}=\{\emptyset\}$, then the collection $\{X\subseteq S\colon |X\cap A|\geq 1,\ \forall A\in\mathcal{A}\}$ is empty, so $b((S,\{\emptyset\}))$ should be $(S,\{\})$. The clutter with no edges and the clutter with only the empty edge are known as trivial clutters.

Our first lemma was noted by Edmonds and Fulkerson in 1970.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter. Then $b(b(H))=H$.

Proof. If $H$ is trivial, the result follows by the discussion above. Therefore we will assume that $H$ has at least one edge and that the empty set is not an edge. This implies that $b(H)$ and $b(b(H))$ are also non-trivial. Let $A$ be an edge of $H$. Now every edge of $b(H)$ has non-empty intersection with $A$, by the definition of $b(H)$. Since $A$ is a set intersecting every edge of $b(H)$, it contains a minimal such set. Thus $A$ contains an edge of $b(b(H))$.

Now let $A’$ be an edge of $b(b(H))$. Assume that $A’$ contains no edge of $H$: in other words, assume that every edge of $H$ has non-empty intersection with $S-A’$. Then $S-A’$ contains a minimal subset that has non-empty intersection with every edge of $H$; that is, $S-A’$ contains an edge of $b(H)$. This edge contains no element in common with $A’$. As $A’$ is an edge of $b(b(H))$, this contradicts the definition of a blocker. Hence $A’$ contains an edge of $H$.

Let $A$ be an edge of $H$. By the previous paragraphs, $A$ contains $A’$, an edge of $b(b(H))$, and $A’$ contains $A^{\prime\prime}$, an edge of $H$. Now $A^{\prime\prime}\subseteq A’\subseteq A$ implies $A^{\prime\prime}=A$, and hence $A=A’$. Thus $A$ is also an edge of $b(b(H))$. Similarly, if $A’$ is an edge of $b(b(H))$, then $A^{\prime\prime}\subseteq A\subseteq A’$, where $A’$ and $A^{\prime\prime}$ are edges of $b(b(H))$, and $A$ is an edge of $H$. This implies $A’=A^{\prime\prime}=A$, so $A’$ is an edge of $H$. As $H$ and $b(b(H))$ have identical edges, they are the same clutter. $\square$

If $H=(S,\mathcal{A})$ is a simple graph (so that each edge has cardinality two), then the edges of $b(H)$ are the minimal vertex covers. In the case of matroid ports, the blocker operation behaves exactly as we would expect an involution to do$\ldots$

Lemma. Let $M$ be a matroid and let $e$ be an element of $E(M)$. Then \[b(\operatorname{Port}(M,e))=\operatorname{Port}(M^{*},e).\]

Proof. Note that if $e$ is a coloop of $M$, then $\operatorname{Port}(M,e)$ has no edges, and if $e$ is a loop, then $\operatorname{Port}(M,e)$ contains only the empty edge. In these cases, the result follows from earlier discussion. Now we can assume that $e$ is neither a loop nor a coloop of $M$. Let $A$ be an edge in $\operatorname{Port}(M^{*},e)$, so that $A\cup e$ is a cocircuit of $M$. Since a circuit and a cocircuit cannot meet in the set $\{e\}$, it follows that $A$ has non-empty intersection with every circuit of $M$ that contains $e$, and hence with every edge of $\operatorname{Port}(M,e)$. Now $A$ contains a minimal set with this property, so $A$ contains an edge of $b(\operatorname{Port}(M,e))$.

Conversely, let $A’$ be an edge of $b(\operatorname{Port}(M,e))$. Assume that $e$ is not in the coclosure of $A’$. By a standard matroid exercise this means that $e$ is in the closure of $E(M)-(A’\cup e)$. Let $C$ be a circuit contained in $E(M)-A’$ that contains $e$. Then $C-e$ is an edge of $\operatorname{Port}(M,e)$ that is disjoint from $A’$. This contradicts the fact that $A’$ is an edge of the blocker. Therefore $e$ is in the coclosure of $A’$, so there is a cocircuit $C^{*}$ contained in $A’\cup e$ that contains $e$. Therefore $A’$ contains the edge, $C^{*}-e$, of $\operatorname{Port}(M^{*},e)$.

In exactly the same way as the previous proof, we can demonstrate that $b(\operatorname{Port}(M,e))$ and $\operatorname{Port}(M^{*},e)$ have identical edges. $\square$

This last fact should be attractive to matroid theorists: clutters have a notion of duality that coincides with matroid duality. There is also a notion of minors. Let $H=(S,\mathcal{A})$ be a clutter and let $s$ be an element of $S$. Define $H\backslash s$, known as $H$ delete $s$, to be
\[(S-s,\{A\colon A\in \mathcal{A},\ s\notin A\}\]
and define $H/s$, called $H$ contract $s$, to be
\[(S-s,\{A-s\colon A\in \mathcal{A},\ A’\in \mathcal{A}\Rightarrow A’-s\not\subset A-s\}.\]
It is very clear that $H\backslash s$ and $H/s$ are indeed clutters. Any clutter produced from $H$ by a (possibly empty) sequence of deletions and contractions is a minor of $H$.

We will finish with one more elementary lemma.

Lemma. Let $H=(S,\mathcal{A})$ be a clutter, and let $s$ be an element in $S$. Then

  1. $b(H\backslash s) = b(H)/s$, and
  2. $b(H/s) = b(H)\backslash s$.

Proof. We note that it suffices to prove the first statement: imagine that the first statement holds. Then
\[b(b(H)\backslash s)=b(b(H))/s=H/s\]
which implies that
\[
b(H)\backslash s=b(b(b(H)\backslash s))=b(H/s)
\]
and that therefore the second statement holds.

If $H$ has no edge, then neither does $H\backslash s$, so $b(H\backslash s)$ has only the empty edge. Also, $b(H)$ and $b(H)/s$ have only the empty edge, so the result holds. Now assume $H$ has only the empty edge. Then $H\backslash s$ has only the empty edge, so $b(H\backslash s)$ has no edges. Also, $b(H)$ and $b(H)/s$ have no edges. Hence we can assume that $H$ is nontrivial, and therefore so is $b(H)$.

If $s$ is in every edge of $H$, then $H\backslash s$ has no edges, so $b(H\backslash s)$ has only the empty edge. Also, $\{s\}$ is an edge of $b(H)$, so $b(H)/s$ has only the empty edge. Therefore we can now assume that some edge of $H$ does not contain $s$, and that therefore $H\backslash s$ is non-trivial and $\{s\}$ is not an edge of $b(H)$.

As $b(H)$ has at least one edge we can let $A$ be an arbitrary edge of $b(H)/s$, and as $\{s\}$ is not an edge of $b(H)$, it follows that $A$ is non-empty. Since $s$ is not in every edge of $H$, we can let $A’$ be an arbitrary edge of $H\backslash s$. Hence $A’$ is an edge of $H$. As $H$ is non-trivial, $A’$ is non-empty. If $A$ is an edge of $b(H)$, then certainly $A$ and $A’$ have non-empty intersection. Otherwise, $A\cup s$ is an edge of $b(H)$, so $A\cup s$ and $A’$ have non-empty intersection. As $A’$ does not contain $s$, it follows that $A$ and $A’$ have non-empty intersection in any case. This shows that every edge of $b(H)/s$ intersects every edge of $H\backslash s$, and thus every edge of $b(H)/s$ contains an edge of $b(H\backslash s)$.

As $H\backslash s$ is non-trivial, so is $b(H\backslash s)$. We let $A’$ be an arbitrary edge of $b(H\backslash s)$ and note that $A’$ is non-empty. Let $A$ be an arbitrary edge of $H$, so that $A$ is non-empty. If $s\notin A$, then $A$ is an edge of $H\backslash s$, so $A’\cap A\ne\emptyset$. If $s$ is in $A$, then $(A’\cup s)\cap A\ne\emptyset$. This means that $A’\cup s$ intersects every edge of $H$, so it contains an edge of $b(H)$ and therefore $A’=(A’\cup s)-s$ contains an edge of $b(H)/s$. We have shown that every edge of $b(H\backslash s)$ contains an edge of $b(H)/s$ and now the rest is easy. $\square$

Partial fields, II. The Lift Theorem

A long time ago, I wrote about partial fields. I defined a partial field as a pair $\mathbb{P} = (R, G)$ of a commutative ring $R$ and a subgroup $G$ of the units of $R$, such that $-1 \in G$. I defined a $\mathbb{P}$-matrix as a matrix over $R$ such that every square sub matrix has a determinant in the set $G \cup \{0\}$, and showed that there is an associated matroid $M[A]$ if some $r\times r$ sub matrix has nonzero determinant.

Partial fields first arose in Whittle’s study of matroids having representations over several different fields. In this post I will discuss the main results of his work on ternary matroids [Whi95, Whi97]. First, let me remind you of Tutte’s characterization of the regular matroids:

Theorem 1. The following statements are equivalent for a matroid $M$:

  1. $M$ is representable over both $\text{GF}(2)$ and $\text{GF}(3)$;
  2. $M$ is representable over $\text{GF}(2)$ and some field of characteristic other than $2$;
  3. $M$ is representable over $\mathbb{R}$ by a totally unimodular matrix;
  4. $M$ is representable over every field.

In addition, Tutte showed that there are exactly three excluded minors for the class of regular matroids: $\{U_{2,4}, F_7, F_7^*\}$. If you’ve never done so, you should definitely read Bert Gerards’ concise proof of this fact [Ger89]. Geoff Whittle wondered if similar theorems would hold when the set of fields in the fourth outcome were changed. In particular, what if we don’t require the matroid to be binary? Here is one of his theorems:

Theorem 2. The following statements are equivalent for a matroid $M$:

  1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(5)$;
  2. $M$ is representable over all fields of characteristic other than $2$;
  3. $M$ is representable over $\mathbb{Q}$ by a matrix with every square submatrix in $\{0\} \cup \{\pm 2^i : i \in \mathbb{Z}\}$.

Recall from the last post the dyadic partial field $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \{\pm 2^i : i \in \mathbb{Z}\})$. Let $\mathbb{F}$ be a field of characteristic $p$ other than 2, and define the ring homomorphism $\phi: \mathbb{Z}[\frac{1}{2}] \to \mathbb{F}$ by sending $x \in \mathbb{Z}$ to $x \pmod p$ and $\frac{1}{2}$ to the inverse of $\phi(2)$ in $\mathbb{F}$. Then $\phi$ is a partial-field homomorphism, and therefore any dyadic matrix $A$ will have $M[A] = M[\phi(A)]$. With this homomorphism, the implication $(3) \implies (2)$ follows immediately. The implication $(2) \implies (1)$ is trivial. To show that $(1)$ implies $(3)$ we need some more work.

fundamental element of a partial field $\mathbb{P}$ is an element $p \in G$ such that $1-p \in G$ as well. Together with Rudi Pendavingh I proved the following theorem, generalizing Whittle’s proof techniques:

Theorem 3. Let $\mathbb{P}_1$ and $\mathbb{P}_2$ be partial fields, and $\phi: \mathbb{P}_1\to \mathbb{P}_2$ a partial-field homomorphism whose restriction to the fundamental elements of $\mathbb{P}_1$ and $\mathbb{P}_2$ is a bijection. Let $A_2$ be a $\mathbb{P}_2$-matrix. Then exactly one of the following holds:

  1. There exists a $\mathbb{P}_1$-matrix $A_1$ such that $\phi(A_1) = A_2$;
  2. $A_2$ can be transformed, using pivots, row and column permutations, transposing, and row and column scaling, to a matrix $A$ of the form $$ \begin{bmatrix}  1 & 1 & 1\\  1 & a & b\end{bmatrix} \textit{ or } \begin{bmatrix} 1 & 1 & 0 & 1\\ 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 \end{bmatrix}$$ such that (1) does not hold for $A$ either.

The associated matroid is $M[I\ A_1]$. To use this theorem for Whittle’s result, let $\mathbb{P}_1 = \mathbb{D}$ and $\mathbb{P}_2 = \text{GF}(3)\times \text{GF}(5)$, where addition and multiplication are componentwise. Then all we have to check is that there is a bijection between the matrices of the forms above between these two partial fields, which is a finite task (because the entries $a$ and $b$ have to be fundamental elements). We called this result the lift theorem, because it allows us to “lift” the finite representation over the partial field $\text{GF}(3) \times \text{GF}(5)$ to a representation over the infinite partial field $\mathbb{D}$.

The proof of the theorem follows Gerards’ proof of Tutte’s theorem (mentioned above) very closely. A new ingredient, though, is the construction of the matrix $A_1$ out of the matrix $A_2$. I will briefly sketch this construction. Let $G= (V, E)$ be the bipartite graph whose vertices are the rows and columns of the matrix $A_2$, and whose edges correspond to the nonzero entries. We may scale so that the entries corresponding to a spanning tree $H$ of $G$ are 1. We fill $A_1$ with $1$s corresponding to the spanning tree, $0$s corresponding to the zero entries of $A_2$, and question marks for the other entries. We repeatedly select a question mark for which the shortest path in $H$ between its terminal vertices is minimal. Up to row and column permutations, this matrix has the following shape: $$\begin{bmatrix} * & 0 & \cdots & 0 & *\\ * & * & 0 & & 0\\ 0 & * & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & * & 0\\ 0 & \cdots & 0 & * & * \end{bmatrix}$$ (where the top right entry corresponds to the question mark in $A_1$). We scale the rows and columns of both this sub matrix of $A_2$ and of $A_1$ to get the following pair:

$$\begin{bmatrix} -1 & 0 & \cdots & 0 & p\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}, \begin{bmatrix} -1 & 0 & \cdots & 0 & ?\\ 1& -1 & 0 & & 0\\ 0 & 1 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & -1 & 0\\ 0 & \cdots & 0 & 1 & -1 \end{bmatrix}.$$

The determinant of the left matrix is $\pm (1-p)$, so $p$ is a fundamental element of $\mathbb{P}_2$. Since there is a unique $q$ such that $\phi(q) = p$, we can replace the question mark with $q$. Then we revert the scaling, and add the corresponding edge to $H$.

We can show that, if a $\mathbb{P}_1$-matrix $A_1$ exists with $\phi(A_1) = A_2$, then this construction finds it. Moreover, the construction commutes with pivoting because it is unique up to row and column scaling. The rest of the proof roughly goes as follows:

Take a minimal counterexample $A_2$. We may assume the bipartite graph is connected and not a path or cycle. Possibly after transposing we can find two columns $u$ and $v$ such that $G – u, G – v, G – \{u,v\}$ are all connected. Scale as above, where the spanning tree has $u$ and $v$ as leaves. Find a matrix $A_1 – u$ corresponding to $A_2 – u$ (by which we mean the matrix with column $u$ removed), and a matrix $A_1 – v$ corresponding to $A_2 – v$. These matrices will agree on the columns other than $u, v$. If the matrix $A_1$ obtained by overlaying these two is not a $\mathbb{P}_1$-matrix, some determinant is wrong. By pivoting, we can ensure this determinant is $2\times 2$ and involves columns $u$ and $v$. Let $a,b$ be the rows of this sub matrix. In $G – u,v$ find a path from $a$ to $b$. More pivots result in a path of length $2$ or $4$, and a sub matrix of the following form (the $*$ symbols correspond to the bad sub matrix):

$$ \begin{bmatrix}  1 & * & *\\  1 & * & *\end{bmatrix} \textit{ or } \begin{bmatrix} 1 & 1 & p & q\\ 1 & 0 & * & *\\ 0 & 1 & * & * \end{bmatrix}$$

Then a little more analysis cuts down on the possible values of the entries.

Whittle also proved the following characterizations:

Theorem 4. The following statements are equivalent for a matroid $M$:

  1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(4)$;
  2. $M$ is representable over all fields having a root of $x^2 – x + 1$;
  3. $M$ is representable over $\mathbb{C}$ by a matrix with every square submatrix in $\{0\} \cup \{\zeta^i : i = 1, \ldots, 6\}$, where $\zeta$ is a complex sixth root of unity.

Theorem 5. The following statements are equivalent for a matroid $M$:

  1. $M$ is representable over both $\text{GF}(3)$, $\text{GF}(4)$, and $\text{GF}(5)$;
  2. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(8)$;
  3. $M$ is representable over all fields with at least 3 elements;
  4. $M$ is representable over $\mathbb{Q}(\alpha)$, where $\alpha$ is an indeterminate, by a matrix with every square submatrix in $\{0\} \cup \{\pm \alpha^i(1-\alpha)^j : i, j \in \mathbb{Z}\}$.

Theorem 6. The following statements are equivalent for a matroid $M$:

  1. $M$ is representable over both $\text{GF}(3)$ and $\text{GF}(7)$;
  2. $M$ is representable over $\text{GF}(3)$, $\text{GF}(p^2)$ for all $p > 2$, and over $\text{GF}(p)$ when $p \equiv 1 \pmod 3$;
  3. $M$ is representable over $\mathbb{C}$ by a matrix with every square submatrix in $\{0\} \cup \{\pm 2^i\zeta^j : i,j \in \mathbb{Z}\}$.

Most excitingly, Whittle also managed to prove that these are all theorems of this kind involving $\text{GF}(3)$:

Theorem 7. Let $M$ be a matroid representable over $\text{GF}(3)$ and some field of characteristic other than 3. Then $M$ is representable over at least one of $\{\text{GF}(2), \text{GF}(4), \text{GF}(5), \text{GF}(7)\}$.

An analogous result for $\text{GF}(4)$ and other fields, unfortunately, cannot be obtained: because of the presence of the free spikes, which are representable over all sufficiently large prime fields, there is an infinite number of different classes of matroids representable over $\text{GF}(4)$ and $\text{GF}(p)$, as $p$ ranges over the primes.

Rudi Pendavingh recently implemented the lift construction mentioned above in Sage (it is part of the latest developer beta version). I will write about that in some future post.

References

[Ger89] Bert Gerards. A short proof of Tutte’s characterization of totally unimodular matrices. Lin. Alg. Appl. 114/115:207-212, 1989.

[Whi95]  Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.

[Whi97]  Geoff Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.

A menagerie of infinite matroids

So far in this series we have focused on the search for a good way to axiomatise infinite matroids. Now that we have the axioms, our next aim is to get a better sense of what sort of ground they stake out by taking a whirlwind tour of the known examples of infinite matroids.

Let’s start off with some very familiar examples: The set of subsets of a given set which have size at most $n$,  the set of (edge sets of) forests in a given graph and the set of linearly independent subsets of a given family of vectors in a vector space each give the set of independent sets of a matroid. This is true even if we allow the set, graph or family of vectors in question to be infinite. Of course, all of these examples are finitary (that is, a set is independent as soon as all of its finite subsets are). We saw earlier that it would be a bad idea to only consider finitary matroids, because we would lose the power of duality. But we certainly want our notion of infinite matroid to include all of these examples. Since we now have a concept of infinite matroid which is closed under duality, we get all their duals for free, too.

What about matroids which are neither finitary nor cofinitary? At first it looks like a simple way to construct such examples would be by building infinite uniform matroids. But the usual definition of uniformity, namely that the bases should be all sets of a given size, becomes silly when we replace `size’ by `cardinality’, since infinite sets can have proper subsets of the same cardinality. It doesn’t help to define things in terms of independent sets. For example, we might hope to have a matroid whose independent sets are just the countable subsets of some uncountable set $E$. But since there are no maximal countable sets, this object wouldn’t even have any bases.

The right notion of uniformity for infinite matroids is as follows: if $B$ is a base and $x$ and $y$ are elements of the ground set $E$ with $x$ in $B$ but $y$ not in $B$ then $B – x + y$ is also a base. It isn’t hard to check that this is equivalent to uniformity when applied to finite matroids. Now we might try to build infinite uniform matroids by just recursively choosing the set of bases, paying attention to the fact that (because of the definition above) whenever we choose a set $B$ we also have to choose all sets $B’$ for which $B \setminus B’$ and $B’ \setminus B$ are finite and of equal size. This simpleminded strategy works, given some weak assumptions [BG15]. Because this recursive construction gives us so much freedom, infinite uniform matroids are much more varied than finite ones.

The flexibility of this construction lets us resolve a very basic question: must it be true that any two bases of an infinite matroid have the same cardinality? Higgs showed that this is true if we assume the continuum hypothesis [H69a]. But using the freedom mentioned above we can also show that it is consistent that the following naive plan for building a matroid with bases of different sizes actually works: run the above recursive construction to build a uniform matroid on an uncountable set, and begin by nominating some countable subset and some uncountable subset as bases [BG15]. So the answer to the question above is actually independent of the usual axioms of set theory.

The other examples we’ll look at today will all be associated to graphs. The finitary matroid mentioned above, whose circuits are (edge sets of) cycles in a given graph $G$, is called the finite-cycle matroid of $G$. There is another finitary matroid whose circuits are the finite bonds of $G$. But these two are no longer dual to each other. The circuits of the dual of the finite-bond matroid correspond to topological circles in a topological space, called the end-compactification of $G$. This space is obtained from $G$ by adding some points at infinity, called ends. These `topological cycles’ were actually first invented for a very different reason and helped to motivate the current axiomatisations of infinite matroids. This was the starting point of our story.

So although there is one canonical matroid associated to a finite graph, for an infinite graph we already have two. In fact there are many more. For example, Higgs showed that there very often is a matroid whose circuits are the (edge sets of) finite cycles or double rays in the graph $G$. This doesn’t always work. For example, in the Bean Graph, shown below, the set of bold edges and the set of dashed edges are both bases but there is no way to replace the edge $e$ with a bold edge in the dashed basis and still have a base. So the base axioms don’t hold.

BeanGraph

This is essentially all that can go wrong: Higgs showed [H69b] that if $G$ includes no subdivision of the Bean Graph then there is a matroid, called the algebraic-cycle matroid of $G$, whose circuits are given as above by the finite cycles and double rays.

Another fertile way to build more matroids from graphs is to ignore some of the ends. More precisely, we consider topological circles in a space obtained from the end-compactification of $G$ by deleting some of the ends. For example, the double ladder has two ends and we might wish to keep only one of them, giving rise to the following space:

ladder_with_only_one_end

Once more it is true that the (edge sets of) topological circles give the circuits of a matroid, as long as the set of ends we remove is Borel [BC15].

Is there any unifying theme to this profusion of examples, except that they can all be built somehow from graphs? Yes! Each of these matroids can represented by a topological space. The finite-cycle matroid of $G$ is represented by the geometric realisation of $G$ and the topological-cycle matroid by the end-compactification. The rich collection of matroids we just discussed are represented by subspaces of the end-compactification. The algebraic-cycle matroid is represented by the space obtained from the end-compactification by identifying all the ends.

More generally, there is a precisely specified class of graph-like topological spaces and a  notion of representation of a matroid by such a space, such that a matroid is representable in this way if and only if, firstly, every intersection of a circuit with a cocircuit is finite (this corresponds to the fact that topological circles are compact), and secondly, it satisfies the usual excluded-minor characterisation of graphic matroids.

Thus the wide range of ways of building infinite matroids from graphs corresponds to the variety of ways of building such graph-like spaces out of graphs. We have seen that this construction doesn’t always give a matroid, as with the Bean Graph above, but it does so often enough to give a rich variety of matroids. For example, we always get a matroid when the space is compact. Hence the (edge sets of) topological circles in the following picture give the circuits of a matroid, the Sierpinski Matroid:

sierpinski

Before we conclude, lets just glance at a couple of the other kinds of infinite matroid which have been discovered. There are frame matroids: Matthews and Oxley showed that in any graph $G$ the edge sets of subdivisions of the following graphs gives the set of circuits of a matroid [MO77], and a more general construction works in in infinite biased graphs.

Frame1

Frame2

There are infinite gammoids, defined either in terms of bipartite graphs or of directed graphs. The question of when these constructions give rise to matroids is a delicate one and has been investigated by Afzali, Law and Müller [ALM15].

Finally, we can define the truncation of a non-free matroid $M$ to have as independent sets the proper subsets of independent sets of $M$, and all truncations and co-truncations of infinite matroids are again infinite matroids. This gives lots of new examples, such as the matroids whose circuits are edge sets of topological copies of the following spaces in a graph-like space:

Spaces

This is not so much a class of examples as a way to build new infinite matroids from old. We’ll consider some other fertile ways to combine infinite matroids next time.

[ALM15] H. Afzali, Hiu-Fai Law and M. Müller, Infinite gammoids. Electronic J. Comb. 22 (2015), #P1.53
[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, submitted to LMS, available here.
[BG15] N. Bowler and S. Geschke,  Self-Dual Uniform Matroids on Infinite Sets, to appear in the Bulletin of the American Mathematical Society, available here.
[H69a] D. Higgs, Equicardinality of bases in B-matroids, Canadian Math. Bul. 12 (1969), 861–862.
[H69b] D. Higgs. Infinite graphs and matroids. Recent Progress in Combinatorics, Proceedings Third Waterloo Conference on Combinatorics, Academic Press (1969),  245-53.
[MO77] L. Matthews, J. Oxley, Infinite graphs and bicircular matroids. Discrete Mathematics, Volume 19, Issue 1 (1977), 61-65.

Growth Rates VI

$\newcommand{\PG}{\text{PG}}$

Denser than a Geometry

Hello everyone. In my last post, I discussed an unavoidable minor theorem for large matroids of density greater than $\binom{n+1}{2}$, which as a consequence characterised exactly the minor-closed classes of matroids that grow like the the graphic matroids. Today I’ll write about the exponential analogue of this problem; this appears in a paper of mine [2] available on the arXiv, and I will also be speaking on this topic at the matroid session of the upcoming CanaDAM conference in Saskatchewan.

I’ll first state a nice theorem of Kung, specialized to prime powers:

Theorem: If $q$ is a prime power, and $M$ is a simple rank-$n$ matroid with $|M| > \frac{q^n-1}{q-1}$, then $M$ has a $U_{2,q+2}$-minor.

This is certainly an important theorem – it says that if $M$ has too many elements to be a projective geometry over GF$(q)$, then $M$ has a rank-$2$ minor with the same property. However, if $n$ is large then this is somewhat unsatisfying, as the $U_{2,q+2}$-minor has constant size, and does not really ‘explain’ why $M$ is so dense. We would like a similar theorem that, instead of finding a $U_{2,q+2}$-minor, finds an unavoidable minor whose size grows with $n$.

What should such a minor be? That is, what are the large matroids that are ‘canonically’ denser than a projective geometry over GF$(q)$?

The first example is easy; rank-$2$ matroids can contain arbitrarily many elements, so the uniform matroid $U_{2,t}$ for some large $t$ must appear as an outcome. The direct sum of $U_{2,q^n}$ and $U_{n-2,n-2}$, for example, is a rank-$n$ matroid with more elements than $\PG(n-1,q)$, and essentially no more interesting structure.

Another matroid denser than $\PG(n-1,q)$ is simply a projective geometry $\PG(t-1,q’)$ over finite field GF$(q’)$.with $q’ > q$. This is our second outcome.

The next two outcomes are more interesting. An obvious way to construct a matroid denser than $\PG(n-1,q)$ is to perform a single-element extension. By modularity, every extension of $\PG(n-1,q)$ consists of adding a point freely to some flat $F$. The smallest simple case is where $F$ is a line: we write $\PG^{\mathrm{line}}(n-1,q)$ for the matroid formed by adding a point freely to a line of $\PG(n-1,q)$. The ‘largest’ case is when $F$ is the entire ground set, so the extension is free. We write $\PG^{\mathrm{free}}(n-1,q)$ for this matroid. The matroids $\PG^{\mathrm{line}}(m-1,q)$ and $\PG^{\mathrm{free}}(n-1,q)$ coincide for $n = m = 2$, but are not minors of eachother for any $m,n \ge 3$; they will thus occur as separate outcomes in our theorem. On the other hand, it is not hard to show that any simple extension of $\PG(2n-1,q)$ has one of $\PG^{\mathrm{line}}(n-1,q)$ or $\PG^{\mathrm{free}}(n-1,q)$ as a minor; thus, no further single-element extensions are needed as outcomes. Here is the theorem.

Theorem 1 [2]: For every prime power $q$ and all $t \ge 3$, there exists $n \in \mathbb{Z}$ so that, if $M$ is a simple matroid with rank at least $n$ and $|M| > \frac{q^{r(M)}-1}{q-1}$, then $M$ has a minor isomorphic to one of the following:

  •  $U_{2,t}$,
  • $\PG(t-1,q’)$ for some $q’ > q$,
  • $\PG^{\mathrm{free}}(t-1,q)$, or
  • $\PG^{\mathrm{line}}(t-1,q)$.

Like in the quadratic case, we can apply this theorem to identify minor-closed classes that grow no faster than the GF$(q)$-representable matroids. For instance, if $q’$ is the next prime power after $q$, and $\ell$ is an integer so that $q \le \ell < q’$, then, for $t = \ell+2$, all four of the above minors can be shown to contain a $U_{2,\ell}$-minor. We thus have the following:

Corollary 1: Let $q$ and $q’$ be consecutive prime powers and $\ell$ be an integer so that $q \le \ell < q’$. If $M$ is a simple matroid with sufficiently large rank and no $U_{2, \ell+2}$-minor, then $|M| \le \frac{q^{r(M)}-1}{q-1}$.

Spikes and Swirls

Let $X = \{x_1,\dotsc,x_t\}$ and $Y = \{y_1, \dotsc, y_t\}$ be disjoint $t$-element sets. A rank-$t$ free spike is the matroid $\Lambda_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets of the form $\{x_i,x_j,y_i,y_j\}$ for $i  \ne j$. The rank-$t$ free swirl is the matroid $\Delta_t$ with ground set $X \cup Y$ whose non-spanning circuits are exactly the four-element sets $\{x_i,x_{i+1},y_i,y_{i+1}\}$, where addition is modulo $t$.  Both free spikes and free swirls arise as pathologies in matroid representation theory.

Let $q \ge 3$ be a prime power and let $t \ge 3$. One can show (see [1]) that

  • $\Lambda_t$ is GF$(q)$-representable if and only if $q$ is non-prime or $t \le q-2$.
  • $\Delta_t$ is GF$(q)$-representable if and only if $q-1$ is non-prime or $t \le q-3$.

Using this, one can hunt for free spikes and swirls in the list of unavoidable minors in Theorem 1. There is a bit of case analysis to see what theorems fall out, but we get a few different corollaries that give upper bounds on the densities of matroids with out line-, spike-, and/or swirl-minors. All of the upper bounds in these corollaries are the densities of projective geometries, and are best-possible because the geometries themselves are tight examples.

Corollary 2: Let $\ell \ge 2$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor and no $\Lambda_t$-minor, then $|M| \le \frac{p^{r(M)}-1}{p-1}$.

Corollary 3: Let $\ell \ge 3$ and $t \ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\ell+2}$-minor, no $\Lambda_t$-minor and no $\Delta_t$-minor, then $|M| \le \tfrac{1}{2}(3^{r(M)}-1)$.

The next corollary mostly tells you how dense a matroid can be if you exclude a line and a free swirl has a minor. However, it weirdly fails to apply to some $\ell$ because of the oddness of representation of free swirls. The only fields that can’t represent free swirls are are the ones of order $2^p$, where $2^p-1$ is prime. A prime of the form $2^p-1$ for another prime $p$, like $2^3 – 1 = 7, 2^5 – 1 = 31$ or $2^7 – 1 = 127$, is a Mersenne prime; it is not even known if there are infinitely many.

Corollary 4: Let $2^p-1$ and $2^{p’}-1$ be consecutive Mersenne primes, and let $k$ and $\ell$ be integers so that $2^p \le \ell < \min(2^{2p} + 2^p, 2^{p’})$ and $k \ge \max(3,2^p-2)$. If $M$ is a simple matroid of sufficiently large rank with no $U_{2,\ell+2}$ or $\Delta_k$-minor, then $|M| \le \frac{2^{pr(M)}-1}{2^p-1}$.

This fails to apply to some $\ell$, but only if $\ell$ is (roughly) greater than the square of a Mersenne prime but smaller than the next Mersenne primes. The first pair of Mersenne primes this far apart are $2^{127}-1$ and $2^{521}-1$, so for some $\ell$ around this size, the above corollary says nothing. The actual fact of the matter depends on the very poorly understood distribution of the Mersenne primes, so I don’t expect much improvement there in the near future.

Thanks, and see you next time!

[1] J Geelen, J.G. Oxley, D. Vertigan, G. Whittle, Totally free expansions of matroids, J. Combin. Theory. Ser. B 84 (2002), 130-179.

[2] P. Nelson,  Matroids denser than a projective geometry, to appear, SIAM Journal on Discrete Mathematics.