Google Summer of Code is a program where Google pays students to work on open-source software during the summer.

Once again, SageMath has been selected as a mentoring organization for the Google Summer of Code. We’ve had students work on aspects of the Matroid Theory functionality for the past four years. Maybe this year, YOU can join those illustrious ranks! Check out the call for proposals and ideas list. Read the instructions on both pages carefully. Applications open on March 12, so it’s a good idea to start talking to potential mentors and begin writing your proposal!

]]>In this post I’d like to explain a new generalization of **matroids** developed in this recent paper with Nathan Bowler (referred to henceforth as [BB]). We show that by working over certain algebraic structures which we call **tracts**, *linear subspaces, matroids, valuated matroids, oriented matroids, and matroids over partial fields* all become special cases of a single general concept. Actually, there are at least **two** natural notions of matroids over tracts, which we call **weak** and **strong** matroids, but in many cases of interest (such as all the ones mentioned above) the two notions coincide.

Two important special cases of tracts are **hyperfields** and **partial fields**. We assume familiarity with the theory of partial fields (see for example this post and its sequels by Stefan van Zwam).

**Hyperfields**

Roughly speaking, a hyperfield is an algebraic structure satisfying similar axioms to a field, but where addition is allowed to be multi-valued. Like fields, hyperfields come equipped with an additive identity element called zero and a negation map $x \mapsto -x$. However, one does not require that the hypersum of $ x$ and $ -x$ is zero, only that zero is *contained in* the hypersum. Before giving a precise axiomatic definition, let us give some motivating examples.

- (Fields) Any field $ K$ is in particular a hyperfield.
- (The Krasner hyperfield) The Krasner hyperfield $ {\mathbb K}$ records the arithmetic of “zero” versus “nonzero”. Specifically, define $ {\mathbb K} = \{ 0,1 \}$ together with the binary operation $ 0 \odot 0 = 0, 0 \odot 1 = 0, 1 \odot 1 = 1$ and the binary hyperoperation $ 0 \boxplus 0 = \{ 0 \}, 0 \boxplus 1 = \{ 1 \}, 1 \boxplus 1 = \{ 0,1 \}$. If we think of $ 1$ as representing “nonzero”, the hyperaddition rules just say that zero plus zero is zero and zero plus something nonzero is always nonzero, but the sum of two things which are nonzero could be either zero or nonzero. The negation operator is the identity map, since negative zero is zero and the negative of something nonzero is again nonzero.
- (The hyperfield of signs) The hyperfield of signs $ {\mathbb S}$ records the arithmetic of “zero”, “positive”, and “negative”, represented by the symbols $ 0, 1, -1$, respectively. The product $ x \odot y$ is defined in the obvious way for $ x,y \in {\mathbb S} := \{ 0, 1, -1 \}$. Addition is also defined in the “obvious” way except we have $ 1 \boxplus -1 = \{ 0, 1, -1 \}$ since the sum of a positive number and a negative number could be either zero, positive, or negative. The negation operator takes $ 0$ to itself and interchanges $ 1$ and $ -1$.
- (The tropical hyperfield) The tropical hyperfield $ {\mathbb T}$ records the arithmetic of valuations. More precisely, if $ v : K \to {\mathbb T} := {\mathbb R} \cup \{ \infty \}$ is the valuation map on a valued field $ K$ with value group $ {\mathbb R}$, the hypersum $ a \boxplus b$ consists of all possible values of $ v(\alpha+\beta)$ where $ \alpha,\beta$ are elements of $ K$ with $ v(\alpha)=a$ and $ v(\beta)=b$. (Note that the axioms for a valuation tell us that $ v(\alpha \cdot\beta) = a + b$.) Concretely, this means that we should define $ a \odot b := a + b$ (with the evident conventions when one of $ a,b$ equals $ \infty$), and we define $ a \boxplus b := {\rm min}(a,b)$ if $ a \neq b$ and $ a \boxplus a := \{ z \in {\mathbb T} \; : \; z \geq a \}$. The multiplicative identity element is $ 0$ and the additive identity element is $ \infty$. The negation operator is the identity map, since the unique value of $ b$ such that $ \infty \in a \boxplus b$ is $ b = a$.

The above examples all have an additional property not shared by all hyperfields: they are **doubly distributive **(see below for the definition)**. **Here are two examples of hyperfields which are not doubly distributive:

5. (The triangle hyperfield) Let $ {\mathbb V}$ be the set $ {\mathbb R}_{\geq 0}$ of nonnegative real numbers with the usual multiplication and the hyperaddition rule $ a \boxplus b := \{ c \in {\mathbb R}_{\geq 0} \; : \; |a-b| \leq c \leq a+b \}.$ In other words, $ a \boxplus b$ is the set of all real numbers $ c$ such that there exists a (possibly degenerate) Euclidean triangle with side lengths $ a, b, c$. Then $ {\mathbb V}$ is a hyperfield.

6. (The phase hyperfield) The phase hyperfield $ {\mathbb P}$ records the arithmetic of phases of complex numbers. If $ \pi : {\mathbb C} \to {\mathbb P} := S^1 \cup \{ 0 \}$ is the map taking 0 to 0 and $ z \in {\mathbb C}^*$ to $ z/|z|$, and if $ a,b \in {\mathbb P}$, the hypersum $ a \boxplus b$ consists of all possible values of $ \pi(\alpha + \beta)$ where $ \alpha,\beta$ are elements of $ {\mathbb C}$ with $ \pi(\alpha)=a$ and $ \pi(\beta)=b$. More precisely, multiplication in $ {\mathbb P}$ is defined as usual, and the hyperaddition law is defined for $ x,y \neq 0$ by setting $ x \boxplus -x := \{ 0, x, -x \}$ and $ x \boxplus y := \{ \frac{\alpha x + \beta y}{\| \alpha x + \beta y \|} \; | \; \alpha, \beta \in {\mathbb R}_{>0} \}$ otherwise.

Motivated by Proposition 1, if $ F$ is a tract we define a **strong** **$ F$-matroid** (or **strong** **matroid over $ F$**) of rank $ r$ on $ E$ to be a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to F$. Thus strong matroids over fields are the same as linear subspaces, and strong matroids over the Krasner hyperfield are the same as matroids in the usual sense. (By a matroid over a partial hyperfield $ F$, we mean a matroid over the corresponding tract.) One can also show that strong matroids over a partial field $ P$ are the same as matroids representable over $ P$ in the usual sense.

**Definition of hyperrings and hyperfields**

A **hyperoperation** on a set $ S$ is a map $ \boxplus$ from $ S \times S$ to the collection of non-empty subsets of $ S$.

If $ A,B$ are non-empty subsets of $ S$, we define $ A \boxplus B := \bigcup_{a \in A, b \in B} (a \boxplus b)$ and we say that $ \boxplus$ is **associative** if $ a \boxplus (b \boxplus c) = (a \boxplus b) \boxplus c$ for all $ a,b,c \in S$.

A (commutative) **hyperring** is a set $ R$ together with:

- A commutative and associative binary operation $ \odot$
- A commutative and associative binary hyperoperation $ \boxplus$
- Distinguished elements $ 0,1 \in R$

such that:

- $ (R, \odot, 1)$ is a commutative monoid.
- $ 0 \odot x = x \odot 0 = 0$ and $ 0 \boxplus x = x \boxplus 0 = \{ x \}$ for all $ x \in R.$
- For every $ x \in R$ there is a
**unique**element of $ R$ (denoted $ -x$) such that $ 0 \in x\boxplus -x.$ - $ a \odot (x \boxplus y) = (a \odot x) \boxplus (a \odot y)$ for all $ a,x,y \in R.$

A hyperring $ R$ is called a **hyperdomain **if $ xy=0$ in $ R$ implies that $ x=0$ or $ y=0$.

A hyperring $ R$ is called **doubly distributive** if it satisfies $ (a \boxplus b)\odot (c \boxplus d) = (a\odot c) \boxplus (a \odot d) \boxplus (b \odot c) \boxplus (b\odot d)$ for all $ a,b,c,d \in R$.

A hyperring $ F$ is called a **hyperfield** if $ 0 \neq 1$ and every non-zero element of $ F$ has a multiplicative inverse.

**Partial hyperfields**

A **partial hyperfield** is a pair $ (G,R)$, where $ G$ is a subgroup of the group of units of a hyperdomain $ R$ such that $ -1 \in R$ and $ G$ generates $ R$ as a hyperring.

We set $ P := G \cup \{ 0 \}$, and denote the partial hyperfield $ (G,R)$ simply by $ P$ when no confusion is likely to arise.

Partial hyperfields generalize both hyperfields and partial fields in a natural way. When $ R$ is a ring, $ P$ is just a partial field, and when $ G = R \backslash \{ 0 \}$ is a group, $ P$ is just a hyperfield.

A partial hyperfield is called **doubly distributive** if the ambient hyperring $ R$ is doubly distributive.

**Tracts**

Partial hyperfields are special cases of still more general objects called **tracts**, which appear to be a natural setting for matroid theory.

We define a **tract** to be an abelian group $ G$ (written multiplicatively), together with a subset $ N_G$ of the group semiring $ {\mathbb N}[G]$ satisfying:

(T0) The zero element of $ {\mathbb N}[G]$ belongs to $ N_G$.

(T1) The identity element 1 of $ G$ is not in $ N_G$.

(T2) There is a unique element $ \epsilon$ of $ G$ with $ 1 + \epsilon \in N_G$.

(T3) $ N_G$ is closed under the natural action of $ G$ on $ {\mathbb N}[G]$.

We set $ F := G \cup \{ 0 \} \subset {\mathbb N}[G]$, and refer to the tract $ (G,N_G)$ simply as $ F$ when no confusion is likely to arise. We will also sometimes write $ F^\times$ instead of $ G$, and $ -1$ instead of $ \epsilon$.

One thinks of $ N_G$ as those linear combinations of elements of $ G$ which “sum to zero” (the $ N$ in $ N_G$ stands for “null”).

**Tracts from partial hyperfields**

We can associate a tract to a partial hyperfield $ (G,R)$ by declaring that a formal sum $ \sum a_i g_i \in {\mathbb N}[G]$ belongs to $ N_G$ if and only if $ 0 \in \boxplus a_i g_i$ in $ R$.

We note, for the experts, that one can associate a tract to any **fuzzy ring** in the sense of Dress and Dress-Wenzel, and that if $ P$ is a doubly distributive partial hyperfield there is an associated fuzzy ring whose realization as a tract coincides with the realization of $ P$ itself as a tract.

**Grassmann-Plücker functions over tracts
**

Now let $ F$ be a **tract**. A function $ \varphi : E^r \to F$ is called a **Grassmann-Plücker function **if it is nonzero, alternating (meaning that $ \varphi(x_1,\ldots,x_i, \ldots, x_j, \ldots, x_r)= -\varphi(x_1,\ldots,x_j, \ldots, x_i, \ldots, x_r)$ and $ \varphi(x_1,\ldots, x_r) = 0$ if $ x_i = x_j$ for some $ i \neq j$), and it satisfies the following generalization of the classical Grassmann-Plücker relations:

(GP) For any two subsets $ X := \{ x_1,\ldots,x_{r+1} \}$ and $ Y := \{ y_1,\ldots,y_{r-1} \}$ of $ E$,

$ \sum_{k=1}^{r+1} (-1)^k \varphi(x_1,x_2,\ldots,\hat{x}_k,\ldots,x_{r+1}) \cdot \varphi(x_k,y_1,\ldots,y_{r-1}) \in N_G.$

If $ F=K$ is a **field** then a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to K$ is the same thing as an $ r$-dimensional subspace of $ K^m$. This is essentially just the assertion that the usual Grassmannian variety is cut out by the Plücker equations.

On the other hand:

Proposition 1:If $ F = {\mathbb K}$ is the Krasner hyperfield, a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to {\mathbb K}$ is the same thing as a rank $ r$matroidon $ E$.

Indeed, if $ \varphi : E^r \to {\mathbb K}$ is a nonzero alternating function and $ {\mathbf B}_\varphi$ denotes the set of $ r$-element subsets $ \{ e_1,\ldots, e_r \}$ of $ E$ such that $ \varphi(e_1,\ldots,e_r) \neq 0$, it is easy to see that $ {\mathbf B} := {\mathbf B}_\varphi$ satisfies the Grassmann-Plücker relations (GP) if and only if

(BE) Given $ B,B’ \in {\mathbf B}$ and $ b \in B \backslash B’$, there exists $ b’ \in B’ \backslash B$ such that both $ (B \cup \{ b’ \}) \backslash \{ b \}$ and $ (B’ \cup \{ b \}) \backslash \{ b’ \}$ are in $ {\mathbf B}$.

But condition (BE) is well-known to be equivalent to the usual Basis Exchange property for matroids! In other words, $ {\mathbf B}_\varphi$ is the set of bases of a rank $ r$ matroid $ M_{\varphi}$ on $ E$. Conversely, given such a matroid $ M$, we can define $ \varphi_M : E^r \to {\mathbb K}$ by setting $ \varphi_M(e_1,\ldots,e_r) = 1$ if $ \{ e_1,\ldots,e_r \}$ is a basis of $ M$ and $ \varphi_M(e_1,\ldots,e_r) = 0$ if not. By the exchange property (BE), the function $ \varphi_M(e_1,\ldots,e_r)$ will satisfy (GP).

Motivated by Proposition 1, if $ F$ is a tract we define a **strong** **$ F$-matroid** (or **strong** **matroid over $ F$**) of rank $ r$ on $ E$ to be a projective equivalence class of Grassmann-Plücker functions $ \varphi : E^r \to F$. Thus strong matroids over fields are the same as linear subspaces, and strong matroids over the Krasner hyperfield are the same as matroids in the usual sense. (By a matroid over a partial hyperfield $ F$, we mean a matroid over the corresponding tract.) One can also show that strong matroids over a partial field $ P$ are the same as matroids representable over $ P$ in the usual sense.

We have the following additional interesting examples of (strong) matroids over tracts:

Proposition 2:If $ F = {\mathbb S}$ is the hyperfield of signs, a matroid over $ {\mathbb S}$ is the same thing as anorientedmatroid.

Proposition 3:If $ F = {\mathbb T}$ is the tropical hyperfield, a matroid over $ {\mathbb T}$ is the same thing as avaluatedmatroid.

Proposition 4:If $ F = {\mathbb U}_0$ is theregular partial field$ (\{ \pm1 \}, {\mathbb Z})$, a matroid over $ {\mathbb U}_0$ is the same thing as aregular matroid.

**Weak matroids over tracts **

It is also of interest to consider objects which satisfy a weaker version of (GP), where we consider only the three-term Grassmann-Plücker relations. Specifically, a **weak $ F$-matroid** is a projective equivalence class of nonzero alternating functions $ \varphi : E^r \to F$ such that (a) $ {\mathbf B}_\varphi$ is the set of bases for a (classical) matroid on $ E$, and (b) $ \varphi$ satisfies (GP) for all $ X,Y$ with $ |X \backslash Y| = 3$.

It will turn out that in Propositions 1-4 above, **strong and weak $ F$-matroids are the same.**

**Circuit axioms for matroids over tracts**

Let $ {\mathcal C}$ be a collection of pairwise incomparable nonempty subsets of $ E$. We say that $ C_1,C_2 \in {\mathcal C}$ form a **modular pair** in $ {\mathcal C}$ if $ C_1 \neq C_2$ and $ C_1 \cup C_2$ does not properly contain a union of two distinct elements of $ {\mathcal C}$.

If $ F$ is a tract and $ X \in F^m$, we write $ \underline{X}$ for the **support** of $ X$, i.e., the set of $ i \in \{ 1,\ldots,m \}$ such that $ X_i \neq 0$. If $ {\mathcal C} \subset F^m$ and $ X,Y \in {\mathcal C}$, we say that $ X,Y$ are a modular pair in $ {\mathcal C}$ if $ \underline{X},\underline{Y}$ are a modular pair in $ \underline{\mathcal C} := \{ \underline{X} \; : \; X \in {\mathcal C} \}.$

Theorem 1:Let $ F$ be a tract and let $ E = \{ 1,\ldots,m \}$. There is a natural bijection betweenweak $ F$-matroidson $ E$ and collections $ {\mathcal C} \subset F^m$ satisfying:(C0) $ 0 \not\in {\mathcal C}$.

(C1) If $ X \in {\mathcal C}$ and $ \alpha \in F^\times$, then $ \alpha \cdot X \in {\mathcal C}$.

(C2) [Incomparability] If $ X,Y \in {\mathcal C}$ and $ \underline{X} \subseteq \underline{Y}$, then there exists $ \alpha \in F^\times$ such that $ X = \alpha \cdot Y$.

(C3) [Modular Elimination] If $ X,Y \in {\mathcal C}$ are amodular pairin $ {\mathcal C}$ and $ e \in E$ is such that $ X_e= -Y_e \neq 0$, there exists $ Z \in {\mathcal C}$ such that $ Z_e=0$ and $ X_f + Y_f – Z_f \in N_G$ for all $ f \in E$.

We call $ {\mathcal C}$ the set of **$ F$-circuits** of the weak $ F$-matroid $ M$.

In [BB], there is also a stronger version of the circuit elimination axiom (C3) which gives a cryptomorphic characterization of **strong $ F$-matroids** in terms of circuits. Let’s say that a family of atomic elements of a lattice is **modular** if the height of their join in the lattice is the same as the size of the family. If $ \mathcal C$ is a subset of $ F^m$, a **modular family** of elements of $ \mathcal C$ is one such that the supports give a modular family of elements in the lattice of unions of supports of elements of $ \mathcal C$.

Then there is a natural bijection between **strong $ F$-matroids** on $ E$ and collections $ {\mathcal C} \subset F^m$ satisfying (C0),(C1),(C2), and the following stronger version of the modular elimination axiom (C3):

**[Strong modular elimination]** Suppose $ X_1,\ldots,X_k$ and $ X$ are $ F$-circuits of $ M$ which together form a modular family of size $ k+1$ such that $ \underline X \not \subseteq \bigcup_{1 \leq i \leq k} \underline X_i$, and for $ 1 \leq i \leq k$ let $ e_i \in (X \cap X_i) \setminus \bigcup_{\substack{1 \leq j \leq k \\ j \neq i}} X_j$ be such that $ X(e_i) = -X_i(e_i) \neq 0$. Then there is an $ F$-circuit $ Z$ such that $ Z(e_i) = 0$ for $ 1 \leq i \leq k$ and $ X_1(f) + \cdots + X_k(f) + X(f) – Z(f) \in N_G$ for every $ f \in E$.

**Duality**

There is a duality theory for matroids over tracts which generalizes the known duality theories for matroids, oriented matroids, valuated matroids, etc., and which corresponds to orthogonal complementation for matroids over fields.

Let $ F$ be a tract. The **inner product** of two vectors $ X,Y \in F^m$ is $ X \cdot Y := \sum_{i=1}^m X_i \cdot Y_i.$ We call $ X$ and $ Y$ **orthogonal**, denoted $ X \perp Y$, if $ X \cdot Y \in N_G$. If $ S \subset F^m$, we denote by $ S^\perp$ the orthogonal complement of $ S$, i.e., the set of all $ X \in F^m$ such that $ X \perp Y$ for all $ Y \in S$.

If $ M$ is a (weak or strong) $ F$-matroid on $ E$ whose collection of circuits is denoted $ {\mathcal C}$, then $ \underline{M} := \{ \underline{X} \; : \; X \in {\mathcal C} \}$ is the collection of circuits of a matroid in the usual sense on $ E$, which we call the **underlying matroid** of $ M$.

Theorem 2:Let $ F$ be a tract, and let $ M$ be a (weak, resp. strong) $ F$-matroid of rank $ r$ on $ E=\{ 1,\ldots,m \}$ with $ F$-circuit set $ {\mathcal C}$ and Grassmann-Plücker function $ \varphi.$

Then there is a (weak, resp. strong) $ F$-matroid $ M^*$ of rank $ m-r$ on $ E$, called thedual $ F$-matroidof $ M$, with the following properties:1. The $ F$-circuits of $ M^*$ are the elements of $ {\mathcal C}^\perp$ of minimal non-empty support.

2. $ M^*$ has the Grassmann-Plücker function $ \varphi^*(x_1,\ldots,x_{m-r}) = {\rm sign}(x_1,\ldots,x_{m-r},x_1′,\ldots,x_r’) \varphi(x_1′,\ldots,x_r’),$ where $ x_1′,\ldots,x_r’$ is any ordering of $ E \backslash \{ x_1,\ldots,x_{m-r} \}.$

3. The underlying matroid of $ M^*$ is the dual of the underlying matroid of $ M$.

4. $ M^{**} = M$.

The deepest part of Theorem 2 is the fact that the elements of $ {\mathcal C}^\perp$ of minimal non-empty support satisfy the circuit elimination axiom (C3) (or its strong variant).

**Dual pair axioms for matroids over hyperfields**

One can give another cryptomorphic characterization of $ F$-matroids using the notion of dual pairs. It is perhaps the simplest of all descriptions of matroids over tracts, but it presupposes that one already knows what a (usual) matroid is.

Let $ M$ be a (classical) matroid on $ E$. We call a subset $ {\mathcal C}$ of $ F^m$ an **$ F$-signature of $ M$** if it is closed under multiplication by nonzero elements of $ F$ and $ \underline{\mathcal C} := \{ \underline{X} \; : \; X \in {\mathcal C} \}$ is the set of circuits of $ M$.

We call $ ({\mathcal C},{\mathcal D})$ a **dual pair of $ F$-signatures of $ M$** if:

(DP1) $ {\mathcal C}$ is an $ F$-signature of $ M$.

(DP2) $ {\mathcal D}$ is an $ F$-signature of the dual matroid $ M^*$.

(DP3) $ {\mathcal C} \perp {\mathcal D}$, meaning that $ X \perp Y$ for all $ X \in {\mathcal C}$ and $ Y \in {\mathcal D}$.

Theorem 3:Let $ F$ be a tract and let $ E = \{ 1,\ldots,m \}$. There is a natural bijection betweenstrong $ F$-matroidson $ E$ and matroids $ M$ on $ E$ together with a dual pair of $ F$-signatures of $ M$.

An analogous theorem holds for weak $ F$-matroids if we only require that (DP3) holds when $ |\underline{X} \cap \underline{Y}| \leq 3$.

**Vectors, perfection, and double distributivity**

Given a tract $ F$ and a strong $ F$-matroid $ M$ on $ E$ with $ F$-circuit set $ \mathcal C$ and $ F$-cocircuit set $ \mathcal C^*$, a **vector** of $ M$ is an element of $ F^m$ which is orthogonal to everything in $ \mathcal C^*$. Similarly a **covector** of $ M$ is an element of $ F^m$ which is orthogonal to everything in $ \mathcal C$. We say that $ F$ is **perfect** if, for any strong matroid $ M$ over $ F$, all vectors are orthogonal to all covectors.

Theorem 4:Let $ F$ be a tract.1. If $ F$ is perfect, then the notions of weak and strong $ F$-matroids coincide.

2. Every doubly distributive partial hyperfield is perfect.

As a consequence, we see that the notions of weak and strong $ F$-matroids coincide for doubly distributive partial hyperfields $ F$. This holds, in particular, when $ F=P$ is a partial field or when $ F$ is the Krasner hyperfield, the tropical hyperfield, or the hyperfield of signs.

There are examples in [BB] which show that weak and strong $ F$-matroids do **not** coincide when $ F$ is either the triangle hyperfield or the phase hyperfield.

**Some directions for future research**

There are many things one would like to know about matroids over tracts which aren’t yet well-understood. Here are some concrete problems which come to mind:

- Does the theory developed in [BB] also work for tracts in which multiplication is not assumed to be commutative? It would be nice, for example, if one could fold the theory of representations of matroids over skew partial fields (as developed in this paper by Pendavingh and van Zwam) into our framework.
- Laura Anderson has developed a theory of vectors and covectors for matroids over hyperfields. It would be interesting to resolve some of the conjectures in her paper, for example the Elimination Conjecture 7.2 or Conjecture 6.4 concerning
**flats**. - Can one extend the Lift Theorem from this paper by Pendavingh and van Zwam to matroids over tracts?
- Can one give an “algebraic” characterization of perfect tracts?

We can make Problem #4 a bit more precise. For any perfect tract, the matroids which are strongly representable over the tract are the same as the weakly representable ones, so they are determined by the set $ N_G^{(3)}$ of elements of $ N_G$ which are sums of at most 3 terms. On the other hand, any set of 3-term relations in $ N_G$ can be extended to a perfect tract by just including everything of size at least 4 in $ N_G$. The problem is that this includes a lot of extra stuff in $ N_G$ which might not be needed for strong representability. This motivates looking at the smallest tract extending $ N_G^{(3)}$ which could possibly be perfect, namely the set of all combinations which appear as sums in the GP relations (or the orthogonality relations) for weak matroids over $ N_G^{(3)}$. Could it be that if this tract is perfect then it must satisfy certain algebraic conditions which are also sufficient to guarantee perfection?

]]>\begin{align*}

&r(A\cup B) + r(A \cup C) + r(A \cup D) + r(B \cup C) + r(B \cup D) \\

\ge & \ r(A) + r(B) + r(A \cup B \cup C) + r(A \cup B \cup D) + r(C \cup D)

\end{align*}

As difficult to typeset as it may be, this is an intriguing fact. The problem of characterizing which matroids are representable is difficult; various authors [2][3] have considered whether it is possible to extend one of the usual axiom systems in a natural way to capture precisely the representable matroids. Ingleton’s inequality suggests the kind of extra axiom that might need to be added to the rank axioms if thinking along these lines. Perhaps more importantly, the Ingleton inequality gives a concise way to certify that a matroid is not representable; if $(A,B,C,D)$ is a $4$-tuple in a matroid $M$ violating the inequality, then $M$ is non-representable. This has been useful to many authors that wish to construct non-representable matroids, in particular in a result of Mayhew, Newman, Welsh and Whittle [4] that constructs a very rich family of excluded minors for the real-representable matroid, all violating Ingleton’s inequality.

Finally, the Ingleton inequality is closely related to everyone’s favourite non-representable matroid, the Vámos matroid $V_8$. This rank-$4$ matroid has eight elements and ground set $E$ that is the disjoint union of four two-element sets $P_1,P_2,P_3,P_4$, in which the dependent four-element sets are precisely the pairs $P_i \cup P_j$ with $i < j$ and $(i,j) \ne (3,4)$. The tuple $(A,B,C,D) = (P_1,P_2,P_3,P_4)$ violates the inequality in this case: the left-hand and right-hand sides are $15$ and $16$ respectively. On the other hand, satisfying Ingleton’s inequality for all choices of $A,B,C,D$ is not enough to imply representability; for example, the non-Desargues matroid satisfies Ingleton’s inequality but is still non-representable, as is the direct sum of the Fano and non-Fano matroids.

**Counting**

This post is about a recent result [7] I’ve obtained with Jorn van der Pol that answers what we consider to be a natural question: how `close’ is the class of matroids that satisfy Ingleton’s inequality to the class of representable matroids? For convenience, we will call a matroid *Ingleton* if Ingleton’s inequality is satisfied for all choices of $(A,B,C,D)$. It might not be immediatley clear what the answer should be. Some (weak) positive evidence is the fact that the Ingleton matroids are closed under minors and duality (see [5], Lemmas 3.9 and 4.5) and that $V_8$ is non-Ingleton. However, I think the natural educated guess goes in the other direction; Ingleton’s inequality seems too coarse to capture, even approximately, a notion as intricate as linear representability In fact, Mayhew, Newman and Whittle [3] have in fact shown that it is impossible to define the class of representable matroids by adding *any* finite list of rank inequalities to the usual rank axioms, let alone a single inequality.

Our result confirms this suspicion.

**Theorem 1:** For all sufficiently large $n$, the number of Ingleton matroids with ground set $\{1,\dotsc,n\}$ is at least $2^{\frac{1.94 \log n}{n^2}\binom{n}{n/2}}$.

To view this result in context, the lower bound should be compared to the counts of representable matroids and of all matroids. On a fixed ground set $[n] = \{1,\dotsc, n\}$ The number of representable matroids is at most $2^{n^3/4}$ for all $n \ge 12$ [6], and the number of matroids is at least $2^{\tfrac{1}{n}\binom{n}{n/2}}$. (Both these upper and lower bounds are in fact correct counts up to a constant factor in the exponent). This first expression is singly exponential in $n$, having the form $2^{\mathrm{poly}(n)}$, while the second is doubly exponential, having the form $2^{2^n/\mathrm{poly}(n)}$. The lower bound in our theorem is of the second type, showing that the Ingleton matroids asymptoticlaly dwarf the representable matroids in number. In other words, knowing that a matroid is Ingleton tells you essentially nothing about whether it is representable. (In fact, our techniques show that the number of *rank-$4$* Ingleton matroids on $[n]$ is asymptotically larger than the class of all representable matroids on $[n]$, which seems surprising.) The ideas in the proof of the above theorem are simple and we obtain a nice excluded minor result on the way; I briefly sketch them below. For the full proof, see https://arxiv.org/abs/1710.01924 .

**Ingleton Sparse Paving Matroids**

Our proof actually constructs a large number of Ingleton matroids of a specific sort: *sparse paving*. These matroids, which have come up in previous matroidunion posts, play a very special role in the landscape of all matroids; they are matroids that, while having a somewhat trivial structure, are conjectured to comprise almost all matroids. For the definition, it is easier to talk about the nonbases of a matroid than its bases. Let $\binom{[n]}{r}$ denote the collection of $r$-element subsets of $[n]$. Given a rank-$r$ matroid on $[n]$, call a dependent set in $\binom{[n]}{r}$ a *nonbasis *of $M$.

A rank-$r$ matroid is *sparse paving* if for any two nonbases $U_1,U_2$ of $M$, we have $|U_1 \cap U_2| < r-1$. Equivalently, no two nonbases of $M$ differ by a single exchange, or every dependent set of $M$ is a circuit-hyperplane of $M$. In fact, this condition itself implies that the matroid axioms are satisfied; given any collection $\mathcal{K}$ of $r$-element subsets of $[n]$, if no two sets in $K$ intersect in exactly $r-1$ elements, then $\mathcal{K}$ is the set of nonbases of a sparse paving matroid on $[n]$. Thus, an easy way to guarantee that a set $\mathcal{K}$ is actually the set of nonbases of a matroid is to prove that no two of its members intersect in $r-1$ elements.

Our key lemma gives a simpler way to understand Ingleton’s inequality for sparse paving matroids. In general, it is very hard to mentally juggle the $A$’s, $B$’s, $C$’s and $D$’s while working with the inequality, but for sparse paving matroids, things are much simpler.

**Lemma 1:** If $M$ is a rank-$r$ sparse paving matroid, then $M$ is Ingleton if and only if there do not exist pairwise disjoint sets $P_1,P_2,P_3,P_4,K$ where $|P_1| = |P_2| = |P_3| = |P_4| = 2$ and $|K|=r-4$, such that the five $r$-element sets $K \cup P_i \cup P_j: i < j, (i,j) \ne (3,4)$ are nonbases, while the set $K \cup P_3 \cup B_4$ is a basis.

This statement may look technical, but it should also look familiar. If $P_1,P_2,P_3,P_4,K$ are sets as above, then the minor $N = (M / K)|(P_1\cup P_2 \cup P_3 \cup P_4)$ is an eight-element sparse paving matroid having a partition $(P_1,P_2,P_3,P_4)$ into two-element sets, where precisely five of the six sets $P_i \cup P_j$ are nonbases, and the last is a basis. This is a structure very similar to that of the Vámos matroid. Call an eight-element, rank-$4$ matroid $N$ having such a property* Vámos-like*. (Such an $N$ need not be precisely the Vámos matroid, as there may be four-element sets of other forms that are also nonbases of $N$). In *any* Vámos-like matroid, $(A,B,C,D) = (P_1,P_2,P_3,P_4)$ will violate Ingleton’s inequality. We can restate Lemma 1 as follows.

**Lemma 1 (simplified):** If $M$ is a sparse paving matroid, then $M$ is Ingleton if and only if $M$ has no Vámos-like minor.

There are evidently only finitely many Vámos-like matroids, since they have eight elements; in fact, thanks to Dillon Mayhew and Gordon Royle’s excellent computational work [8], we know all $39$ of them; as well as the Vámos matroid itself, they include the matroid AG$(3,2)^-$ obtained by relaxing a circuit-hyperplane of the rank-$4$ binary affine geometry. It is easy to show that the sparse paving matroids are themselves a minor-closed class with excluded minors $U_{1,1} \oplus U_{0,2}$ and $U_{0,1} \oplus U_{2,2}$. Combined with Lemma 1, this gives us a nice excluded minor theorem:

**Theorem 2:** There are precisely $41$ excluded minors for the class of Ingleton sparse paving matroids: the $39$ Vámos-like matroids, as well as $U_{1,1} \oplus U_{0,2}$ and $U_{0,1} \oplus U_{2,2}$.

**The Proof**

Armed with Lemma 1, we can now take a crack at proving our main theorem. For simplicity, we will prove a slightly weaker result, with a worse constant of $0.2$ and no logarithmic factor in the exponent. The stronger result is obtained by doing some counting tricks a bit more carefully. The good news is that the proof of the weaker theorem is short enough to fit completely in this post.

**Theorem 3:** For all sufficiently large $n$, there are at least $2^{0.2n^{-2}\binom{n}{n/2}}$ Ingleton sparse paving matroids with ground set $[n]$

**Proof**

Let $n$ be large and let $r = \left\lfloor n/2 \right\rfloor$ and $N = \binom{n}{r}$. Let $c = 0.4$. We will take a uniformly random subset $\mathcal{X}$ of $\left\lfloor c n^{-2}\binom{n}{r}\right\rfloor$ of the $\binom{n}{r}$ sets in $\binom{[n]}{r}$. We then hope that $\mathcal{X}$ is the set of nonbases of an Ingleton sparse paving matroid. If it is not, we remove some sets in $\mathcal{X}$ so that it is.

We consider two possibilities that, together, encompass both ways $\mathcal{X}$ can fail to be the set of nonbases of a sparse paving matroid. They are

- $\mathcal{X}$ is not the set of nonbases of a sparse paving matroid. (That is, there are sets $U_1,U_2 \in \mathcal{X}$ whose intersection has size $r-1$.)
- $\mathcal{X}$ is the set of nonbases of a sparse paving matroid, but this matroid fails to be Ingleton. (That is, there are pairwise disjoint subsets $P_1,P_2,P_3,P_4,K$ of $[n]$ where $|P_1| = |P_2| = |P_3| = |P_4| = 2$ and $|K|=r-4$, such that at least five of the six $r$-element sets $K \cup P_i \cup P_j: i < j, (i,j)$ are nonbases.)

Let $a(\mathcal{X}),b(\mathcal{X})$ denote the number of times each of these types of failure occurs. The condition in (2) is slightly coarser than required, for reasons we will see in a minute. So $a(X)$ is the number of pairs $(U_1,U_2)$ with $|U_1 \cap U_2| = r-1$ and $U_1,U_2 \in X$, and $b(X)$ is the number of $5$-tuples $(P_1,P_2,P_3,P_4,K)$ satisfying the condition in (2).

**Claim:** If $n$ is large, then $\mathbf{E}(a(\mathcal{X}) + 2b(\mathcal{X})) < \tfrac{1}{2}|\mathcal{X}|$.

**Proof of claim:** The number of pairs $U_1,U_2$ intersecting in $r-1$ elements is $\binom{n}{r}r(n-r) < n^2\binom{n}{r}$. For each such pair, the probability that $U_1,U_2 \in X$ is at most $(|\mathcal{X}|/\binom{n}{r})^2 \le c^2n^{-4}$. Therefore \[\mathbf{E}(a(\mathcal{X})) \le c^2n^{-2}\binom{n}{r} = (1+o(1))c|\mathcal{X}|.\]

The number of $5$-tuples $(K,P_1,P_2,P_3,P_4)$ pf disjoint sets where $|K| = r-4$ and $|P_i| = 2$ is at most $\binom{n}{2}^4\binom{n-8}{r-4} < \tfrac{n^8}{16}\binom{n}{r}$. The probability that, for some such tuple, at least five of the sets $K \cup P_i \cup P_j$ are in $X$ is at most $6(|\mathcal{X}|/\binom{n}{r})^5 \le 6c^5n^{-10}$. Therefore

\[\mathbf{E}(b(\mathcal{X})) \le \frac{n^8}{16}\binom{n}{r}\cdot 6c^5 n^{-10} = (1+o(1))\tfrac{3}{8}c^4|\mathcal{X}|.\]

By linearity of expectation, the claim now holds since $c = 0.4$ gives $c + \tfrac{3}{4}c^4 < \tfrac{1}{2}$.

Now, let $\mathcal{X}_0$ be a set of size $\left\lfloor c n^{-2}\binom{n}{r}\right\rfloor$ for which $a(\mathcal{X}) + 2b(\mathcal{X}) < \tfrac{1}{2}|\mathcal{X}_0|$. We now remove from $\mathcal{X}_0$ one of the two sets $U_1,U_2$ for each pair contributing to $a(\mathcal{X}_0)$, and two of the sets $K \cup P_i \cup P_j$ for each tuple $(K,P_1,P_2,P_3,P_4)$ contributing to $b(\mathcal{X}_0)$. This leaves a subset $\mathcal{X}_0’$ of $\mathcal{X}_0$ of size $\tfrac{1}{2}|\mathcal{X}_0| \approx \tfrac{1}{2}cn^{-2}\binom{n}{r} = 0.2n^{-2}\binom{n}{r}$. By construction and Lemma 1, $\mathcal{X}_0’$ is the set of nonbases of a rank-$r$ Ingleton sparse paving matroid on $[n]$. However (and this is where condition (2) needed to be strengthened slightly), so are all subsets of $\mathcal{X}_0’$. This puts the size of $\mathcal{X}_0’$ in the exponent; there are therefore at least $2^{0.2n^{-2}\binom{n}{n/2}}$ Ingleton sparse paving matroids on $[n]$, as required.

**References**

- A.W. Ingleton. Representation of matroids. In D.J.A Welsh, editor,
*Combinatorial mathematics and its applications (Proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969).*Academic Press, 1971. - P. Vámos. The missing axiom of matroid theory is lost forever.
*J. London Math. Soc. 18 (1978), 403-408* - D. Mayhew, M. Newman and G. Whittle. Yes, the “missing axiom” of matroid theory is lost forever,
*arXiv:1412.8399* - D. Mayhew, M. Newman and G. Whittle. On excluded minors for real-representability.
*J. Combin. Theory Ser. B 66 (2009), 685-689.* - A. Cameron. Kinser inequalities and related matroids.
*Master’s Thesis, Victoria University of Wellington.*Also available at*arXiv:1401.0500* - P. Nelson. Almost all matroids are non-representable.
*arXiv:1605.04288* - P. Nelson and J. van der Pol. Doubly exponentially many Ingleton matroids.
*arXiv:1710.01924* - D. Mayhew and G.F. Royle. Matroids with nine elements.
*J. Combin. Theory Ser. B 98 (2008), 882-890.*

In this post we will spend a little more time discussing this diagram.

We let $H=(S,\mathcal{A})$ be a clutter. This means that $S$ is a finite set, and the members of $\mathcal{A}$ are subsets of $S$, none of which is properly contained in another. We let $M$ stand for the incidence matrix of $H$. This means that the columns of $M$ are labelled by the elements of $S$, and the rows are labelled by members of $\mathcal{A}$, where an entry of $M$ is one if and only if the corresponding element of $S$ is contained in the corresponding member of $\mathcal{A}$. Any entry of $M$ that is not one is zero. Let $w$ be a vector in $\mathbb{R}^{S}$ with non-negative values. We have two fundamental linear programs:

(1) Find $x\in \mathbb{R}^{S}$ that minimises $w^{T}x$ subject to the constraints $x\geq \mathbf{0}$ and $Mx\geq \mathbf{1}$.

The vectors $\mathbf{0}$ and $\mathbf{1}$ have all entries equal to zero and one, respectively. When we write that real vectors $a$ and $b$ with the same number of entries satisfy $a\geq b$, we mean that each entry of $a$ is at least equal to the corresponding entry in $b$.

(2) Find $y\in\mathbb{R}^{\mathcal{A}}$ that maximises $y^{T}\mathbf{1}$ subject to the constraints $y\geq \mathbf{0}$ and $y^{T}M\leq w$.

**Lemma 1.** *Any clutter with the Max Flow Min Cut property also has the packing property.*

*Proof.* Let $H$ be a clutter with the Max Flow Min Cut property. This means that for any choice of vector $w$ with non-negative integer entries, the programs (1) and (2) both have optimal solutions with integer values.

We will show that $H$ has the packing property. According to the definition in the literature, this means that for any choice of vector $w$ with entries equal to $0$, $1$, or $+\infty$, there are optimal solutions to (1) and (2) with integer entries. I think there is a problem with this definition. Assume that $r$ is a row of $M$, and every member of the support of $r$ receives a weight of $+\infty$ in the vector $w$. Then (2) cannot have an optimal solution. If $y$ is a purported optimal solution, then we can improve it by adding $1$ to the entry of $y$ that corresponds to row $r$. We are instructed that if entry $i$ in $w$ is $+\infty$, then this means when $x$ is a solution to (1), then entry $i$ of $x$ must be $0$. Again, we have a problem, for if $r$ is a row of $M$, and the entire support of $r$ is weighted $+\infty$, then (1) has no solution: if $x$ were a solution, then it would be zero in every entry in the support of $r$, meaning that $Mx$ has a zero entry.

The literature is unanimous in saying that $H$ has the packing property if (1) and (2) both have integral optimal solutions for **any** choice of vector $w$ with entries $0$, $1$, and $+\infty$. As far as I can see, this means that any clutter with $\mathcal{A}$ non-empty does not have the packing property: simple declare $w$ to be the vector with all entries equal to $+\infty$. Then neither (1) nor (2) has an optimal solution at all. I think the way to recover the definition is to say that whenever $w$ with entries $0$, $1$, or $+\infty$ is chosen in such a way that (1) and (2) have solutions, they both have optimal solutions that are integral. This is the definition that I will use here.

After this detour, we return to our task, and assume that $H$ has the Max Flow Min Cut property. Assume that $w$ is a vector with entries equal to $0$, $1$, or $+\infty$, and that (1) and (2) both have solutions. This means that any row in $M$ has a member of its support which is not weighted $+\infty$ by $w$. We obtain the vector $u$ by replacing each $+\infty$ entry in $w$ with an integer that is greater than $|S|$. Now because $H$ has the Max Flow Min Cut property, it follows that there are optimal integral solutions, $x$ and $y$, to (1) and (2) (relative to the vector $u$). We will show that $x$ and $y$ are also optimal solutions to (1) and (2) relative to the vector $w$.

We partition $S$ into $S_{0}$, $S_{1}$, and $S_{+\infty}$ according to whether an element of $S$ receives a weight of $0$, $1$, or $+\infty$ in $w$. We have assumed that no member of $\mathcal{A}$ is contained in $S_{+\infty}$. We note that if $z\in \mathbb{Z}^{S}$ is a vector which is equal to zero for each element of $S_{+\infty}$, and one everywhere else, then $z$ is a solution to (1), by this assumption. Moreover, $w^{T}z=u^{T}z\leq |S|$. Now it follows that $x$ must be zero in every entry in $S_{+\infty}$, for otherwise $u^{T}x>|S|$, and therefore $x$ is not an optimal solution to (1) relative to $u$. Since $x$ is integral and optimal, it follows that we can assume every entry is either one or zero. If $x$ is not an optimal solution to (1) relative to $w$, then we let $z$ be an optimal solution with $w^{T}z < w^{T}x$. But by convention, $z$ must be zero in every entry of $S_{+\infty}$. Therefore $u^{T}z=w^{T}z < w^{T}x=u^{T}z$, and we have a contradiction to the optimality of $x$. Thus $x$ is an optimal solution to (1) relative to the $\{0,1,+\infty\}$-vector $w$.

Now for problem (2). Since $y$ is integral and non-negative, and $y^{T}M\leq w$, where every member of $\mathcal{A}$ contains an element of $S_{0}$ or $S_{1}$, it follows that each entry of $y$ must be either one or zero. Let $z$ be any solution of (2) relative to $w$. Exactly the same argument shows that each entry of $z$ is between zero and one. Therefore $z^{T}\mathbf{1}\leq y^{T}\mathbf{1}$ so $y$ is an optimal solution to (2).

We have shown that relative to the vector $w$, both (1) and (2) have optimal solutions that are integral. Hence $H$ has the packing property. $\square$

**Lemma 2.** *A clutter with the packing property packs.*

*Proof.* This one is easy. In order to prove that $H$ packs, we merely need to show that (1) and (2) have optimal integral solutions when $w$ is the vector with all entries equal to one. But this follows immediately from our revised definition of clutters with the packing property. $\square$

The final containment we should show is that clutters with the packing property are ideal. Idealness means that (1) has an optimal integral solution for all vectors $w\in \mathbb{R}^{S}$. This proof is difficult, so I will leave it for a future post. Usually we prove it by using a theorem due to Lehman [Leh].

**Theorem** (Lehman). The clutter $H$ is ideal if and only if (1) has an optimal integral solution for all choices of vector $w\in\{0,1,+\infty\}^{S}$.

**Question.** Is there a short proof that clutters with the packing property are ideal? One that does not rely on Lehman’s (quite difficult) theorem?

We will conclude with some examples showing that various containments are proper.

Let $C_{3}^{2}$ and $C_{3}^{2+}$ be the clutters with incidence matrices

\[

\begin{bmatrix}

1&1&0\\

0&1&1\\

1&0&1

\end{bmatrix}

\quad\text{and}\quad

\begin{bmatrix}

1&1&0&1\\

0&1&1&1\\

1&0&1&1

\end{bmatrix}.

\]

Let $Q_{6}$ and $Q_{6}^{+}$ be the clutters with incidence matrices

\[

\begin{bmatrix}

1&1&0&1&0&0\\

1&0&1&0&1&0\\

0&1&1&0&0&1\\

0&0&0&1&1&1

\end{bmatrix}

\quad\text{and}\quad

\begin{bmatrix}

1&1&0&1&0&0&1\\

1&0&1&0&1&0&1\\

0&1&1&0&0&1&1\\

0&0&0&1&1&1&1

\end{bmatrix}

\]

**Exercise.** Check that:

- $C_{3}^{2}$ is not ideal and does not pack,
- $C_{3}^{2+}$ packs, but is not ideal,
- $Q_{6}$ is ideal, but does not pack,
- $Q_{6}^{+}$ is ideal and packs, but does not have the packing property.

This leaves one cell in the Venn diagram without a clutter: the clutters with the packing property that do not have the Max Flow Min Cut property. In fact, Conforti and Cornuéjols [CC] have speculated that no such clutter exists.

**Conjecture** (Conforti and Cornuéjols). A clutter has the packing property if and only if it has the Max Flow Min Cut property.

[CC] M. Conforti and G. Cornuéjols, *Clutters that Pack and the Max Flow Min Cut Property: A Conjecture*, The Fourth Bellairs Workshop on Combinatorial Optimization, W.R. Pulleyblank and F.B. Shepherd eds. (1993).

[Leh] A. Lehman, *On the width-length inequality.* *Mathematical Programming* December 1979, Volume 16, Issue 1, pp 245–259.

I would like to thank Jim Geelen, Peter Nelson, Luke Postle, and Stefan van Zwam (the organizers of this year’s workshop) who did an excellent job in choosing the program and making sure everything ran smoothly. They even helped fellow Matroid Union blogger Nathan Bowler overcome Canadian Visa issues in time to give his (very nice) plenary talk (thanks also go to Alan).

This year the workshop was held in commemoration of William T. Tutte, who would have turned 100 this year. See here for a short biography of Professor Tutte. Some matroid theorists may not be aware of Tutte’s extremely important contributions as a code breaker at Bletchley Park during the Second World War. The C&O Department at Waterloo has also been hosting a Distinguished Lecture Series in honour of Tutte this summer. Click on this link for the list of speakers and to watch the videos on YouTube. SiGMa 2017 also featured a rare conference dinner speech by Jim Geelen on Tutte’s work.

In case you were not able to attend, all the talks from SiGMa 2017 were recorded and are now viewable on the C&O Department’s YouTube Channel. The overall quality of talks was very high. I won’t bias you with all of my personal favourites, but for example, all the plenaries and Paul Seymour were excellent.

]]>The key concept is that of a *perturbation *of a representable matroid. If $M = M[A]$, and $T$ is a matrix with the same dimensions as $A$, then $M[A+T]$ is a perturbation of $M$. The hope is that, if we know a lot about $M$ and $T$ has low rank, then the resulting matroid still resembles $M$ to a large extent. We will study perturbations of *graphic matroids*, and start with a few examples. It will be convenient to drop the restriction that the perturbed matroid has the same size as $M$, and therefore we will allow the addition of a bounded number of elements.

Let $A$ be the vertex-edge incidence matrix of a graph, and let $A’$ be the matrix obtained from $A$ by adding an arbitrary row. The matroid $M[A’]$ is known as an *even-cycle matroid.* It is an instance of the class of lift matroids frequently discussed on this blog, such as by Irene (here, here, and here) and two weeks ago by Daryl (here). Note that it can be obtained from $M$ by coextending the matroid by one element, and then deleting that element. They can be visualized by coloring the edges of the graph, calling an edge *even* if its corresponding column in the matrix has a 0 in the new row, and *odd* if it has a 1. This class of matroids is closed under minors.

Let $A$ again be the vertex-edge incidence matrix of a graph, and this time let $A’$ be the matrix obtained from $A$ by adding an arbitrary column. The matroid $M[A’]$ will have one extra element, and is known as a *graft*. Grafts played a crucial role in the proofs of many fundamental results in matroid theory, including Seymour’s Decomposition Theorem for regular matroids [2]. They can be visualized by coloring the vertices of the graph whose corresponding matrix row has a 1 in the new column.

Note that the class of grafts is *not* closed under minors (contracting the graft element destroys the graphic structure). However, a closely related class, where we add an element to the graphic matroid *and* immediately contract that element, is closed under minors. The duals of these matroids are known as the *even cut matroids*. They have been extensively studied by Guenin, Pivotto, and Wollan (see, for instance, Irene’s PhD thesis [3]).

Let $G$ be a graph with $t$ distinguished vertices. We take the vertex-edge incidence matrix, and add a few columns, but now these columns are only allowed to have nonzero entries corresponding to the $t$ distinguished vertices. The resulting class of matroids will resemble a graphic matroid everywhere but in a low-rank set. Note that this can be seen as a variation of the “adding a column” construction, but sometimes it is useful to consider the operation separately.

Next, we ask ourselves what happens if we allow several of the above operations in a row. Can there be fundamentally different ways to perturb a graphic matroid? Geelen, Gerards, and Whittle answered this question in full generality through the introduction of *templates.*

**Definition. ***A (binary) *frame template* is a tuple $\Phi = (C, X, Y_0, Y_1, A_1, \Delta, \Lambda)$ with the following elements:
*

*Finite pairwise disjoint sets $C, X, Y_0, Y_1$;**A matrix $A_1$ with rows labeled by $X$ and columns labeled by $Y_0\cup Y_1 \cup C$;**A set of row vectors $\Delta$ closed under addition, with entries labeled by $Y_0 \cup Y_1 \cup C$;**A set of column vectors $\Lambda$ closed under addition, with entries labeled by $X$.*

**Definition. ***A matrix $A’$ is said to *respect *the template $\Phi$ if it is of this form:*

*Here, a *unit column* is a column with exactly one nonzero. The incidence matrix and the columns labeled by $Z$ can be of arbitrary size.*

**Definition. ***Let $A’$ be a matrix respecting the template $\Phi$. Let $A$ be obtained from $A’$ by*

*Taking each column from $Z$ and adding to it some column labeled by an element of $Y_1$;**Deleting the columns labeled by $Y_1$;**Contracting the elements labeled by $C$ in the corresponding matroid.*

*Then $A$ and $M[A]$ are said to *conform to *the template $\Phi$. *

One should think about templates as recipes for constructing families of matroids.

**Exercise. ***Describe the examples from sections 1.1 – 1.3 using templates.*

The main result from [1] is that templates can be used to describe all sufficiently large, sufficiently highly connected matroids in any minor-closed class. Highly connected means the following:

**Definition. ***A matroid $M$ is *vertically $k$-connected* if, for all separations $(X,Y)$ with $\lambda(X) < k$, either $r(X) = r(M)$ or $r(Y) = r(M)$. In other words, one side of the separation is *spanning.

The precise result is:

**Theorem (Geelen, Gerards, Whittle [1]). ***Let $\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist constants $k, l$ and frame templates $\Phi_1, \ldots, \Phi_t, \Psi_1, \ldots, \Psi_s$ such that:*

*Every matroid conforming to $\Phi_i$ is in $\mathcal{M}$ for $i = 1, \ldots, t$;**Every matroid whose dual conforms to $\Psi_j$ is in $\mathcal{M}$ for $j = 1, \ldots, s$;**For every vertically $k$ connected matroid $M \in \mathcal{M}$ with at least $l$ elements, there either exists an $i$ such that $M$ conforms to $\Phi_i$ or a $j$ such that $M^*$ conforms to $\Psi_j$.*

The third property says that the structure of the highly connected matroids in the class is completely described by a finite list of templates. The first two properties put some quite strict constraints on those templates: *any* matroid we can build using the template must be a member of the class!

The third property is reminiscent of the result by Robertson and Seymour that the “torsos” of a tree-decomposition are nearly-embeddable in some surface of bounded genus (see [4, Theorem 12.6.6]). But in the graph minors theorem there is no analog of the converse: most graphs nearly-embeddable on that surface won’t be members of the class being studied.

The first two properties can be used to determine the full set of templates $\Phi_1, \ldots, \Phi_t, \Psi_1, \ldots, \Psi_s$ for a given class of matroids. I have worked on several such results with my PhD student Kevin Grace [5, 6]. For instance, let’s consider Seymour’s 1-flowing conjecture, discussed by Dillon here. With Kevin I proved the following:

**Theorem (Grace, vZ [5]). ***There exist constants $k, l$ such that every vertically $k$-connected 1-flowing matroid on at least $l$ elements is either graphic or cographic. *

In other words, any counterexample to Seymour’s conjecture will have to be small, or have a low-order vertical separation. The proof proceeds by considering an arbitrary frame template, and showing that it either has to be trivial, or it can be used to build an excluded minor for the class of 1-flowing matroids. In the process we develop some tools to help with proofs by induction on templates, and to clean up the matrix $A_1$, but those will have to wait for another day.

Other applications of templates include *growth rate* results, and finding sufficient sets of excluded minors to characterize the highly connected members of a minor-closed class of matroids.

- J. Geelen, B. Gerards and G. Whittle,
*The highly connected matroids in minor-closed classes*, Ann. Comb. 19 (2015), 107–123. - P. D. Seymour,
*Decomposition of regular matroids,*J. Combin. Theory Ser. B 28(3) (1980), 305-359. - I. Pivotto,
*Even Cycle and Even Cut Matroids.*PhD Thesis, University of Waterloo (2011). - R. Diestel,
Springer GTM 173, 5th edition (2016).*Graph Theory,* - K. Grace, S. H. M. van Zwam,
*Templates for Binary Matroids,*SIAM J. Disc. Mathem. 31(1) (2017), 254 — 282. - K. Grace, S. H. M. van Zwam,
*The highly connected even-cycle and even-cut matroids,*Submitted (2016).

*Biased graphs*, and the *frame* and *lifted-graphic* (or simply, *lift*) matroids associated with them, have been discussed several times already in The Matroid Union blog. Irene Pivotto introduced them in a series of posts, *Biased graphs and their matroids* I, II, and III. In part II, Irene offered to put money on the truth of the following two conjectures.

**Conjecture 1.** * The class of frame matroids has only a finite number of excluded minors. *

**Conjecture 2.** * The class of lift matroids has only a finite number of excluded minors. *

If anyone took her up on her offer, you may now collect on your bet. In [CG17], Rong Chen and Jim Geelen exhibit an infinite family of excluded minors for the class of frame matroids, and another for the class of lift matroids. (It is unfair of me to pick on Irene like this — last I heard, bookies were giving 10:1 odds on). These families of excluded minors belong to a third class of matroids having graphical-type structure. So before discussing Rong and Jim’s counter-examples to Conjectures 1 and 2, we had better learn about this new class.

In his post, *Graphical representations of matroids*, Jim Geelen discussed a preliminary formulation for a new class of “graphical” matroids, which he there called *framework* matroids. The goal was to define a single minor-closed class that contains both the classes of frame and lift matroids, and to do so in a way such that (1) the new class maintains or captures the fundamental underlying graphic structure of these matroids, and (2) recognising membership in the new class is tractable — that is, there should be a polynomial-time algorithm to test membership via a rank oracle.

Jim’s goal has largely been realised, with his introduction, along with Bert Gerards and Geoff Whittle, of the class of *quasi-graphic* matroids, in [GGW17]. There should certainly be a post wholly devoted to this wonderful class of matroids soon. Here, I will tantalise you with just the definition and an example.

Let $M$ be a matroid. A graph $G$ is a *framework* for $M$ if

- $E(G)=E(M)$,
- for each component $H$ of $G$, $r_M(E(H)) \leq |V(H)|$,
- for each vertex $v$ of $G$, \[\operatorname{cl}_M(E(G-v)) \subseteq E(G-v) \cup \{e: e\ \text{is a loop incident to}\ v\},\] and
- for each circuit $C$ of $M$, the subgraph $G[C]$ induced by $C$ has at most two components.

A matroid is *quasi-graphic* if it has a framework. The definition is motivated by the following theorem of Paul Seymour, which yields a polynomial-time algorithm to test, via a rank oracle, if a given matroid is graphic. A *star* of a graph $G$ is the set of edges incident to a vertex $v \in V(G)$ each of whose other endpoint is in $V(G)-v$ (so while $G$ may have loops, loops are not included in any star); $c(G)$ denotes the number of components of $G$.

** Theorem 1** [S81]**.** *Let $M$ be a matroid, and let $G$ be a graph. Then $M$ is the cycle matroid of $G$ if and only if*

- $E(G)=E(M)$,
- $r(M) \leq |V(G)| – c(G)$, and
*every star of $G$ is a union of cocircuits of $M$.*

One can readily see that the requirements for a framework are inspired by the conditions of Theorem 1. One can also see that generalising these conditions to encompass a larger minor-closed class that includes all frame and lift matroids, is not quite straightforward (hopefully, we may learn more about this in a future post). In [GGW17], Jim, Bert, and Geoff show (among other things) that the class of quasi-graphic matroids has the following nice properties:

- It is minor-closed.
- If $(G,\mathcal B)$ is a biased graph, then $G$ is a framework for the lift matroid $LM(G,\mathcal B)$, and $G$ is a framework for the frame matroid $FM(G,\mathcal B)$; thus all lift and all frame matroids are quasi-graphic.
- Given a 3-connected matroid $M$ and a graph $G$, one can check in polynomial time whether $G$ is a framework for $M$.

Jim, Bert, and Geoff conjecture in [GGW17] that there is a polynomial-time algorithm to test, via a rank oracle, if a given matroid is quasi-graphic. In contrast, Rong Chen and Geoff Whittle have recently shown that for each of the classes of frame and lift matroids, testing for membership in the class is intractable [CW16]. More on this in a moment. But first, let us try to get a bit of a feel for what a typical quasi-graphic matroid might look like.

Let us recall some required preliminary concepts. Every frame and every lift matroid may be represented by a biased graph $(G,\mathcal B)$ with $E(G)=E(M)$. For clarity’s sake, I’ll reserve the word *circuit* for matroids, and use the word *cycle* for a 2-regular connected subgraph. Recall how the circuits of frame and lift matroids appear in their biased graph representations: they are precisely the edge sets of subdivisions of certain biased subgraphs. Recall, a cycle $C$ of a graph whose edge set is a circuit of the matroid is *balanced*; otherwise $E(C)$ is independent and $C$ is said to be *unbalanced*. The figures in Sections 2 and 3 of Irene’s first post on biased graphs, reproduced here for your convenience, illustrate these biased subgraphs.

Let us call a subdivision of one of these five biased subgraphs (1), (2), (3F), (3L), (4), a *circuit-subgraph*. Note that the frame and lift matroids associated with a given biased graph differ on just one pair of these circuit-subgraphs, namely, (3F) and (3L) — a pair of vertex disjoint unbalanced cycles forms a circuit of the lift matroid, but is independent in the frame matroid. As Irene has explained in her previous posts, given a biased graph, we get a frame matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3F), and (4), we get a lift matroid by taking as circuits just circuit-subgraphs of the forms (1), (2), (3L), and (4), and Tom Zaslavsky has shown that in fact all frame matroids, and all lift matroids, are obtained this way.

What about quasi-graphic matroids? Here is an example. The Vámos matroid (shown below left as a cube, in which the only 4-circuits are the 4 “sides” and just the one “diagonal” plane 2468) is neither a frame matroid, nor a lift matroid, but it is quasi-graphic, with the graph below right providing a framework. (Check that it satisfies the definition!)

Consider the 4-circuits of Vámos, and the subgraphs they form in the framework graph.

The four planes given by the front, back, and sides of the cube each form a circuit-subgraph of type (2), which is a circuit-subgraph for both frame and lift matroids. But together the circuit 2468 and the independent set 1357 prevent this graph from being either a frame or a lift representation for Vámos: circuit 2468 appears as a type (3L) circuit-subgraph, but so does the independent set 1357.

It turns out that (here I’m summarising results of [GGW17]), just as with biased graph representations of frame and lift matroids, the edge set of every cycle in a framework $G$ for a quasi-graphic matroid $M$ is either a circuit of $M$ or is independent in $M$. Further, declaring each cycle of $G$ to be *balanced* or *unbalanced* accordingly, just as for frame and lift matroids, yields a biased graph $(G,\mathcal B)$, where $\mathcal B$ denotes the collection of balanced cycles of $G$ (that is, the collection of balanced cycles satisfies the theta property: no theta subgraph contains exactly two balanced cycles). Moreover, every circuit of $M$ appears in $G$ as one of our five circuit-subgraphs (1), (2), (3F), (3L), (4). Conversely, the edge set of each circuit-subgraph of $G$ of one of the forms (1), (2), or (4) is a circuit of $M$, and each of the form of (3F) is either a circuit or contains a circuit of the form (3L).

Thus frameworks for matroids behave very much like biased graph representations for frame and lift matroids. Given a biased graph, taking $\{(1),(2),(3$F$),(4)\}$ as our circuit-subgraphs gives us a frame matroid, taking $\{(1),(2),(3$L$),(4)\}$ as our circuit-subgraphs gives us a lift matroid; and allowing all of $\{(1), (2), (3$F$), (3$L$), (4)\}$ as circuit-subgraphs gives the class of quasi-graphic matroids. This phenomenon is illustrated in the framework for the Vámos matroid above: 2468 is a (3L) circuit-subgraph, while each of the four circuits $1357 \cup e$ for $e \in \{2,4,6,8\}$ are (3F) circuit-subgraphs. Put another way, if a matroid $M$ has a framework having no circuit-subgraphs of type (3F), then we have a biased graph representation for $M$ as a lift matroid; if $M$ has a framework with no circuit-subgraphs of type (3L), then we have a biased graph representation for $M$ as a frame matroid; the Vámos matroid shows that (3F) and (3L) type circuit-subgraphs can coexist in a framework.

As mentioned above, Rong and Geoff have shown that there can be no algorithm that can determine, via a rank oracle, in time polynomial in the size of the ground set, whether or not a given matroid is a frame matroid. They also show no such algorithm can exist for recognising lift matroids. They do so using two particular families of quasi-graphic matroids, one for frame and one for lift, arising from the same infinite family of framework graphs. More precisely, they prove the following two theorems.

**Theorem 2 **[CW16]**. ** *For any polynomial $p(\cdot)$, there is a frame matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not frame, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$. *

**Theorem 3 **[CW16]**. ** *For any polynomial $p(\cdot)$, there is a lift matroid $M$ such that, for any collection $\mathcal A$ of subsets of $E(M)$ with $|\mathcal A| \leq p(|E(M)|)$, there is a quasi-graphic matroid $N$ that is not lift, such that $E(N)=E(M)$ and for each $A \in \mathcal A$, $r_k(A) = r_M(A)$. *

The proofs go like this. Construct an infinite family of biased graphs $(W_k, \emptyset)$. Relaxation of a particular circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$ yields a quasi-graphic matroid that is no longer lift, but which agrees with $LM(W_k,\emptyset)$ on almost all subsets. Performing the reverse tweak to the frame matroid $FM(W_k, \emptyset)$ yields a quasi-graphic matroid that is no longer frame, but which agrees with $FM(W_k,\emptyset)$ on almost all subsets. The operation reverse to relaxation of a circuit-hyperplane is that of *tightening a free basis*. A *free basis* of a matroid is a basis $B$ such that $B \cup e$ is a circuit for each $e \in E(M)-B$. If $B$ is a free basis of $M$, then removing $B$ from the set of bases of $M$ results in a matroid, which we say is obtained by *tightening* $B$.

Here is the family of biased graphs. For each even integer $k \geq 4$, let $W_k$ be the graph consisting of 4 edge-disjoint $k$-cycles on vertices $u_1, \ldots, u_k, v_1, \ldots, v_k$: one cycle on the $u_i$’s, one cycle on the $v_i$’s (the vertex disjoint pair of blue cycles in the drawing of $W_6$ at below left), and two cycles (red and green in figure) alternating between $u_i$’s and $v_i$’s hitting every second vertex of the blue cycles as shown (below left).

Call a green edge and a red edge that cross in this drawing a *crossing pair*. Observe that $W_k$ has $k$ crossing pairs, and that for every collection $S$ of an even number of crossing pairs, there is a pair of disjoint cycles $C_S^1, C_S^2$ which use precisely these crossing pairs, each of which has length $k$, and which between them traverse all vertices of $W_k$. (See figure below: choosing the 2nd and 4th crossing pair defines the pair of cycles highlighted green and yellow.)

The graph $W_k$ has exponentially many collections of crossing pairs: there are $2^{k-1}$ collections consisting of an even number of crossing pairs. Hence $W_k$ has $2^{k-1}$ pairs of disjoint cycles, each pair having the property that together they contain all vertices of $W_k$. Each such pair of cycles is a circuit-hyperplane of the lift matroid $LM(W_k,\emptyset)$, and a free basis of the frame matroid $FM(W_k,\emptyset)$. Let $Z$ be the edge set of a pair of cycles obtained as above from a chosen set of crossing pairs of even cardinality. Let $M_L^Z$ be the matroid obtained from $LM(W_k,\emptyset)$ by relaxing the circuit-hyperplane $Z$. Let $M_F^Z$ be the matroid obtained from $FM(W_k,\emptyset)$ by tightening the free basis $Z$. To distinguish $LM(W_k,\emptyset)$ from $M_L^Z$, and to distinguish $FM(W_k,\emptyset)$ from $M_F^Z$, requires checking the rank of $2^{k-1}$ subsets. This, of course, will be greater than any polynomial in $|E(W_k)|$ for sufficiently large $k$. Since $W_k$ remains a framework for both $M_L^Z$ and $M_F^Z$, both these matroids are quasi-graphic. The proofs are completed by showing that $M_L^Z$ is not a lift matroid, and that $M_F^Z$ is not frame (which takes just another couple of pages in Rong and Geoff’s paper).

The Chen-Whittle graph’s usefulness does not stop here.

To disprove Conjectures 1 and 2, Rong and Jim exhibit an infinite family of quasi-graphic matroids, each of which is minor-minimally not frame, and another infinite family of quasi-graphic matroids, each of which is minor-minimally not lifted-graphic. As in Rong and Geoff’s proofs of Theorems 2 and 3, these two families share a common framework. In fact, they again use the Chen-Whittle graphs!

Here is Rong and Jim’s construction. For each odd positive integer $k \geq 5$, let $G_k$ be the graph obtained from the Chen-Whittle graph $W_{k+1}$ defined above by deleting exactly one crossing pair (at right in figure above is shown the Chen-Geelen graph $G_5$). It is convenient to describe the collection of balanced cycles of $G_k$ by group-labelling (group-labelled graphs are described in Irene’s first post on biased graphs, Section 1, 4th bullet point).

For each odd positive integer $k \geq 5$, we obtain a quasi-graphic excluded minor for the class of frame matroids, with framework $G_k$, as follows. Label $G_k$ using the multiplicative group of $\mathbb R$. Referring to the drawing of $G_5$ above: orient each of $e_1$ and $e_2$ “up” from the bottom vertex to the top vertex of the vertical path making up its “side” of the crossing ladder, and assign to both $e_1$ and $e_2$ the label 2. Orient all remaining edges arbitrarily, and assign each label 1. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, ${\mathcal B}_k$ consists of those cycles $C$ for which the product of edge labels, taken while traversing $C$ in a cyclic order, is 1, where we take the multiplicative inverse of each label whose edge is traversed against its orientation). Let $P$ be the paths forming the two vertical sides of the ladder, so $P \cup \{e_1, e_2\}$ is the pair of blue disjoint cycles in the figure, and let $Q$ be the union of the red and green paths. Then $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$ are free bases of $FM(G_k, \mathcal B_k)$. Let $M_k^F$ be the matroid obtained from $FM(G_k, \mathcal B_k)$ by tightening $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^F/\{e_1, e_2\}$, while quasi-graphic (with framework $G_k/\{e_1,e_2\}$), is an excluded minor for the class of frame matroids.

An excluded minor for the class of lift matroids is obtained in a similar manner. Again orient $e_1$ and $e_2$ up from the bottom to the top vertex of the vertical paths of the ladder. This time, label $G_k$ using elements of the additive group of integers, labelling $e_1$ with $1$, $e_2$ by $-1$, and all remaining edges with $0$. Let $\mathcal B_k$ be the collection of balanced cycles defined by this labelling (that is, $C \in \mathcal B_k$ if and only if when traversing $C$ in a chosen cyclic direction, taking the sum of the labels on its edges, subtracting the label on each edge traversed against its orientation, yields $0$). Let $P$ and $Q$ be as before. Then $P \cup \{e_1,e_2\}$ and $Q \cup \{e_1, e_2\}$ are circuit-hyperplanes of $LM(G_k, \mathcal B_k)$. Let $M_k^L$ be the matroid obtained from $LM(G_k, \mathcal B_k)$ by relaxing $P \cup \{e_1, e_2\}$ and $Q \cup \{e_1, e_2\}$. Then $M_k^L / \{e_1, e_2\}$, while quasi-graphic, is an excluded minor for the class of lift matroids.

Rong and Jim make the following conjecture.

**Conjecture 3 **[CG17]**.** *The class of quasi-graphic matroids has only a finite number of excluded minors. *

Dillon Mayhew and I have recently proved the following three theorems.

**Theorem 4 ** [FM17]**.** * The class of frame matroids has only a finite number of excluded minors of any fixed rank. *

**Theorem 5 ** [FM17]**.** * The class of lift matroids has only a finite number of excluded minors of any fixed rank. *

**Theorem 6 ** [FM17]**.** * The class of quasi-graphic matroids has only a finite number of excluded minors of any fixed rank. *

Rong and Jim’s counterexamples to Conjecture 1 and 2 are both infinite families of excluded minors of ever increasing, arbitrarily large rank (if $G$ is a connected framework for a non-graphic quasi-graphic matroid $M$, then the rank of $M$ is $|V(G)|$). Theorems 4 and 5 say that any such collections of excluded minors for these classes must have this property. Theorem 6 provides evidence toward Conjecture 3 — though no more evidence than Theorems 4 and 5, respectively, provide toward Conjectures 1 and 2! What is perhaps interesting about Theorems 4, 5, and 6 is that — in contrast to what we’ve just seen in the results of Rong, Geoff, and Jim above — the same strategy works for all three classes. Dillon and I set out to prove Theorem 4, and having done so, realised that essentially the same proof also gives us Theorems 5 and 6. Perhaps we can take a look at this strategy in a subsequent post.

[CG17] Rong Chen and Jim Geelen. *Infinitly many excluded minors for frame matroids and for lifted-graphic matroids.* arXiv:1703.04857

[CW16] Rong Chen and Geoff Whittle. *On recognising frame and lifted-graphic matroids.* arXiv:1601.01791

[FM17] Daryl Funk and Dillon Mayhew. *On excluded minors for classes of graphical matroids.* Forthcoming.

[GGW17] Jim Geelen, Bert Gerards, and Geoff Whittle. *Quasi-graphic matroids.* arXiv:1512.03005

[S81] Paul Seymour. *Recognizing graphic matroids.* Combinatorica (1981). MR602418

The analogous question for matroids is much more pleasant. We’ll stick to binary matroids here, but in [2], we prove versions of theorem I discuss for all prime fields. For binary matroids, projective geometries play the same role that cliques do in graphs. Our main theorem is the following:

**Theorem 1:*** Let $t$ be a nonnegative integer. If $n$ is sufficiently large, and $M$ is a simple rank-$n$ binary matroid with no $\mathrm{PG}(t+2,2)$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$. Furthermore, there is a unique simple rank-$n$ binary matroid for which equality holds.*

Unlike for graphs, we can write down a nice function. Note that for $t = 0$, the function above is just $\binom{n+1}{2}$; in fact, in this case, the cycle matroid of a clique on $n+1$ vertices is the one example for which equality holds and in fact the result specialises to an old theorem of Heller [3] about the density of matroids without an $F_7$-minor. This was the only previously known case.

The case for $t = 1$ was conjectured by Irene in her post from 2014. Irene also conjectured the extremal examples; they are all *even cycle matroids*. These can be defined as the matroids having a representation of the form $\binom{w}{A}$, where $A$ is a matrix having at most two nonzero entries per column, and $w$ is any binary row vector. The largest simple rank-$n$ even cycle matroids can be shown to have no $\mathrm{PG}(3,2)$-minor and have $2\binom{n}{2}-1$ elements; this agrees with the expression in our theorem for $t = 1$.

These first two examples suggest a pattern allowing us to construct the extremal matroids more generally; we want a matrix with $n$ rows and as many columns as possible, having distinct nonzero columns, that is obtained from a matrix with at most two nonzero entries per column by appending $t$ rows. For a given column, there are $2^t$ choices for the first $t$ entries, and $\binom{n-t}{0} + \binom{n-t}{1} + \binom{n-t}{2}$ for the last $n-2$ (as we can choose zero, one or two positions where the column is nonzero). Since we can’t choose the zero vector both times, the total number of possible columns is $2^t(\binom{n-t}{0} + \binom{n-t}{1} + \binom{n-t}{2})-1 = 2^t\binom{n-t+1}{2} + 2^t-1$, the bound in our theorem. Let’s call this maximal matroid $G^t(n)$. Note that $G^0(n)$ is just the cycle matroid $M(K_{n+1})$

We can prove by induction that $G^t(n)$ has no $\mathrm{PG}(t+2,2)$-minor; the $t = 0$ case is obvious since $\mathrm{PG}(2,2)$ is nongraphic. Then, one can argue that appending a row to a binary representation of a matroid with no $\mathrm{PG}(k,2)$-minor gives a matroid with no $\mathrm{PG}(k+1,2)$-minor; since (for $t > 1$) $G^{t}(n)$ is obtained from $G^{t-1}(n-1)$ by taking parallel extensions of columns and then appending a row, inductively it has no $\mathrm{PG}(t+2,2)$-minor as required.

All I have argued here is that equality holds for the claimed examples. The proof in the other direction makes essential use of the structure theory for minor-closed classes of matroids due to Geelen, Gerards and Whittle [4]; essentially we reduce Theorem 1 to the case where $M$ is very highly connected, then use the results in [4] about matroids in minor-closed classes that have very high connectivity to argue the bound. I discussed a statement that uses these structure theorems in similar ways back in this post.

We can actually say things about excluding matroids other than just projective geometries. The machinery in [2] also gives a result about excluding affine geometries:

**Theorem 2: ***Let $t \ge 0$ be an integer and $n$ be sufficiently large. If $M$ is a simple rank-$n$ binary matroid with no $\mathrm{AG}(t+3,2)$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$. Furthermore, if equality holds, then $M$ is isomorphic to $G^t(n)$.*

This was proved for $t = 0$ in [5] but was unknown for larger $t$. Again, the examples where equality holds are these nice matroids $G^t(n)$. Our more general result characterizes precisely which minors we can exclude and get similar behaviour. To state it, we need one more definition. Let $A$ be the binary representation of $G^t(n+1)$ discussed earlier (where each column has at most two nonzero entries in the last $n+1-t$ positions) and let $A’$ be obtained from $A$ by appending a single column, labelled $e$, whose nonzero entries are in the last three positions. Let $G^t(n)’$ be the simplification of $M(A’) / e$; so $G^t(n)’$ is a rank-$n$ matroid obtained by applying a single `projection’ to $G^t(n+1)$. I will conclude by stating the most general version of our theorem for binary matroids; with a little work, it implies both the previous results.

**Theorem 3:** *Let $t \ge 0$ be an integer and $N$ be a simple rank-$k$ binary matroid. The following are equivalent:*

*For all sufficiently large $n$, if $M$ is a simple rank-$n$ binary matroid with no $N$-minor, then $|M| \le 2^t\binom{n+1-t}{2} + 2^t-1$, and $M \cong G^t(n)$ if equality holds.**$N$ is a restriction of $G^t(k)’$ but not of $G^t(k)$.*

**References:**

[1] A. Thomason: *The extremal function for complete minors,* J. Combinatorial Theory Ser. B 81 (2001), 318–338.

[2] P. Nelson, Z. Walsh, *The extremal function for geometry minors of matroids over prime fields*, arXiv:1703.03755 [math.CO]

[3] I. Heller, On linear systems with integral valued solutions, Pacific. J. Math. 7 (1957) 1351–1364.

[4] J. Kung, D. Mayhew, I. Pivotto, and G. Royle, *Maximum size binary matroids with no AG(3,2)-minor are graphic**, *SIAM J. Discrete Math. 28 (2014), 1559–1577.

[5] J. Geelen, B. Gerards and G. Whittle, *The highly connected matroids in minor-closed classes*, Ann. Comb. 19 (2015), 107–123.

]]>

This marks the fourth year in a row that a Matroid project was selected by SageMath for the Google Summer of Code program. Previous participants are Tara Fife, Chao Xu, and Jayant Apte.

]]>The polymath projects are a sort of mathematical experiment proposed by Tim Gowers to see if massively collaborative mathematics is possible. The proposed proof proceeds via a sequence of public comments on a blog. The general idea is to blurt out whatever idea comes into your head to allow for rapid public dissemination.

Polymath 12 is hosted by Timothy Chow and you can click here to follow the progress or to contribute.

]]>In that construction we used 2-sums to stick the matroids together. Suppose that we have a finite collection of matroids arranged in a tree, so that their ground sets overlap (always in single edges) if and only if they are adjacent in the tree. Then because 2-sums are associative we have an unambiguously defined 2-sum of that collection. In the previous post in this series, we saw that this construction also works if we allow the tree to be infinite, but that we have to specify a little extra information the set $\Psi$ of ends of the tree which the circuits are allowed to use.

The same trick can be used for other kinds of associative sum of finite matroids. In this post we’ll see how it works for sums of representable matroids, and why that is useful for understanding the topological spaces associated to infinite graphs.

To see how the addition of representable matroids works, we need to look at them from a slightly unusual angle. Let’s say that we have a matroid $M$ on a ground set $E$, and suppose that we have vectors $\{v_e | e \in E\}$ in some vector space over a field $k$, giving us a representation of $M$ over $k$. Then we can capture all the essential information about this representation by forgetting the details of the vector space and focusing just on the linear relationships amongst the vectors. More formally, we say that an element $\lambda$ of the space $k^E$ is a *linear dependence* of the $v_e$ if $\sum_{e \in E} \lambda(e)v_e = 0$. Then the linear dependences form a subspace $V$ of $k^E$, and this subspace is enough to recover the matroid $M$; the circuits of $M$ are precisely the minimal nonempty supports of vectors in $V$. For those who prefer to think of representations in terms of matrices rather than families of vectors, the subspace we’re working with is just the orthogonal complement of the row space of the matrix.

So we can encode representations of matroids on $E$ over $k$ as subspaces of $k^E$. This way of seeing representations fits well with matroid duality, in that if $V \subseteq k^E$ represents a matroid $M$ on $E$ then the orthogonal complement $V^{\bot}$ represents the dual matroid $M^*$. If we define $M(V)$ to be the matroid whose circuits are the minimal nonempty supports of elements of $V$, then we can express this as $M(V^{\bot}) = (M(V))^*$.

The advantage of this perspective is that there is a natural way to glue together such subspaces, which we can use to build a self-dual gluing operation for represented matroids. Suppose that we have two sets $E_1$ and $E_2$ and subspaces $V_1$ and $V_2$ of $k^{E_1}$ and $k^{E_2}$, respectively. We now want to glue these together to give a subspace $V_1 \oplus V_2$ of $E_1 \triangle E_2$. As with the 2-sum, we throw away the `gluing edges’ in the overlap $E_1 \cap E_2$. The idea is to take pairs of vectors which match on the gluing edges, patch them together and throw away the part supported on the gluing edges. More precisely, we set $V_1 \oplus V_2 := \{v \mathord{\upharpoonright}_{E_1 \triangle E_2} | v \in k^{E_1 \cup E_2}, v \mathord{\upharpoonright}_{E_i} \in V_i\}$.

Like the 2-sum, this definition is self-dual in the sense that $(M(V_1 \oplus V_2))^* = M(V_1^{\bot} \oplus V_2^{\bot})$. It is also associative, in that if $V_1$, $V_2$ and $V_3$ are subspaces of $k^{E_1}$, $k^{E_2}$ and $k^{E_3}$ respectively and the sets $E_1$ and $E_3$ are disjoint then $(V_1 \oplus V_2) \oplus V_3 = V_1 \oplus (V_2 \oplus V_3)$. So if we have a finite collection of such representations on ground sets $E_t$ arranged in a finite tree, such that the ground sets only overlap if they are adjacent in the tree, then we have an unambiguous sum of all these subspaces.

Just as for 2-sums, we can also glue together infinite trees of represented matroids in this way, as long as we are careful to specify which ends of the tree the circuits are allowed to use. Formally, we do this as follows. Suppose that we have a tree $T$, a family of sets $E_t$ indexed by the nodes of $T$, such that $E_s \cap E_t$ is only nonempty if $s = t$ or $s$ and $t$ are adjacent in $T$, a family of subspaces $V_t \subseteq k^{E_t}$ and a Borel subset $\Psi$ of the set $\Omega(T)$ of ends of $T$. Then we can build a subspace of $k^{\bigtriangleup_{t}E_t}$ by setting

$\bigoplus^{\Psi}_t V_t := \{v \mathord{\upharpoonright}_{\bigtriangleup_t E_t} | v \in k^{\bigcup_t E_t}, v \mathord{\upharpoonright}_{E_t} \in V_t \text{ and } \Omega(T) \cap \overline{\{t | v \upharpoonright_{E_t} = 0\}} \subseteq \Psi\}$

and $M(\bigoplus^{\Psi}_t V_t)$ will be an infinite matroid.

What are these infinite sums good for? Well, if we have a representable matroid and we have a $k$-separation of that matroid then we can split it up as a sum of two matroids in this way such that there are fewer than $k$ gluing edges. We can use this to break problems about bigger matroids down into problems about smaller matroids. Similarly, if we have a nested collection of finite separations in an infinite matroid, cutting the ground set up into a tree of finite parts, then we can cut the matroid up into a sum of finite matroids and analyse its properties in terms of their properties. This kind of chopping up and reconstruction can also be helpful to show that the infinite object is a matroid in the first place.

Let’s see how that might work for a more concrete problem. Suppose that we have a locally finite graph $G$. Then we can build a topological space $|G|$ from it by formally adding its ends as new points at infinity (see for example [D10]). These spaces and their subspaces are key elements of topological infinite graph theory, which was where this series of posts started.

At first, it was hoped that these subspaces would have the nice property that if they are connected then they are path connected. But Agelos Georgakopoulos eventually found a counterexample to this claim [G07]. However, the set of ends used by the counterexample he constructed was topologically horrible, so we might still hope that if we have a connected subspace $X$ of $|G|$ such that the set $\Psi$ of ends contained in $X$ is topologically nice, then $X$ will be path-connected. Well, if we take `topologically nice’ to mean `Borel’, then the ideas above let us show that this is true.

We can do this by considering the matroid whose circuits are the edge sets of those topological circles in $|G|$ which only go through ends in $\Psi$. More precisely, we need to show that this really does give the circuit set of a matroid $M(G, \Psi)$. If we can do that, then we can argue as follows:

Let $P$ be the set of edges which, together with both endpoints, are completely included in $X$. Let $u$ and $v$ be vertices in $X$. Build a new graph $G + e$ with an extra edge $e$ joining $u$ to $v$. Then since $X$ is connected, there can be no cocircuit of $M(G + e, \Psi)$ which contains $e$ and is disjoint from $P$ (such a cocircuit would induce a topological separation of $X$ with $u$ and $v$ on opposite sides). So $e$ is not a coloop in the restriction of $M(G + e, \Psi)$ to $P \cup \{e\}$. Hence there is a circuit through $e$ in that matroid, and removing $e$ from the corresponding topological circle gives an arc from $u$ to $v$ through $X$ in $|G|$. So any two vertices are in the same path-component of $X$. Similar tricks show the same for ends and interior points of edges.

What this argument shows is that the connection between connectivity and path-connectivity is encoded in the statement that $M(G, \Psi)$ is a matroid. To prove that statement, we can build $M(G, \Psi)$ as the sum of an infinite tree of graphic matroids in the sense described above. First of all, since $G$ is locally finite, we can cut it up into an infinite tree of finite connected parts using disjoint finite separators. Then we define the torso corresponding to a part to consist of that part together with new edges forming complete graphs on each of the separators. This gives us an infinite tree of finite graphs, and the ends of the tree correspond precisely to the ends of $G$. Now we take the graphic matroids corresponding to those graphs, take the standard binary representations of those matroids, and glue them together along this tree, taking the ends in $\Psi$ to be allowed for circuits. And presto! We have build the matroid $M(G, \Psi)$.

The details of this argument are explained in [BC15].

I can’t resist mentioning that the matroids we’ve just built in a bottom-up way also have a top-down characterisation. Consider the class of matroids whose ground set is the set of edges of $G$, and in which every circuit is a topological circuit of $G$ and every cocircuit is a bond of $G$. Let’s call such matroids $G$-matroids.

For some graphs $G$, we can find $G$-matroids which are not of the form $M(G, \Psi)$. For example, in the following graph $Q$ we can define an equivalence relation on the (edge sets of) double rays by saying that two double rays are equivalent if they have finite symmetric difference. Then the set of finite circuits together with any collection of double rays closed under this equivalence relation gives the set of circuits of an infinite matroid.

The matroids I just described are a bit pathological, and they hover on the boundary between being binary and non-binary. None of them has a $U_{2,4}$-minor. They also still have the familiar property that any symmetric difference of two circuits is a disjoint union of circuits. But symmetric differences of *three* circuits might not be disjoint unions of circuits!

For example, there is such a matroid in which the first three sets depicted below are circuits, but the fourth, their symmetric difference, is not.

The problem is that these matroids are wild. This means that there are circuits and cocircuits which intersect in infinitely many elements. We only have a good theory of representability for tame matroids, those in which every intersection of a circuit with a cocircuit is finite. I hope to discuss this in more detail in a future post.

If we only consider tame $G$-matroids, then this proliferation of pathological matroids disappears. For the graph $Q$, for example, there are only 2 tame $Q$-matroids, namely the finite cycle matroid and the topological cycle matroid. Remarkably, for any locally finite graph $G$ it turns out that the tame $G$-matroids are precisely the matroids of the form $M(G, \Psi)$. So our top-down and bottom up characterisations meet, and any matroid associated to a graph can be built up from finite parts in a way which mirrors the structure of that graph. The reasons for this correspondence go far beyond the scope of this post, but they can for example be found in [BC16].

Now that we’ve seen the standard ways to build infinite matroids and their relationship to infinite graphs, in the next post we’ll examine the most important open problem about them: the Infinite Matroid Intersection Conjecture.

[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, preprint here.

[BC16] N. Bowler and J. Carmesin, The ubiquity of Psi-matroids, preprint here.

[D10] R. Diestel, Locally finite graphs with ends: a topological approach I–III, Discrete Math 311–312 (2010–11).

[G07] A. Georgakopoulos. Connected but not path-connected subspaces of infinite graphs, Combinatorica, 27(6) 683–698 (2007).

The version of this game where $G$ is the $5 \times 5$ grid was produced in the real world by Tiger Electronics, and has a bit of a cult following. For example, there is a dedicated wikipedia page and this site (from which I borrowed the image below) even has the original user manuals.

The goal of this post is to prove the following theorem.

**Theorem.** Let $G=(V,E)$ be a graph for which all the lights are initially ON. Then it is always possible to press a sequence of vertices to switch all the lights OFF.

(Note that if not all the lights are ON initially, it will not always be possible to switch all the lights OFF. For example, consider just a single edge where only one light is ON initially.)

**Proof. **Evidently, there is no point in pressing a vertex more than once, and the sequence in which we press vertices does not matter. Thus, we are searching for a subset $S$ of vertices such that $|S \cap N[v]|$ is odd for all $v \in V$, where $N[v]$ is the *closed neighbourhood of $v$* (the neighbours of $v$ together with $v$ itself). We can encode the existence of such a set $S$ by doing linear algebra over the binary field $\mathbb{F}_2$.

Let $A$ be the $V \times V$ adjacency matrix of $G$, and let $B=A+I$. Note that the column corresponding to a vertex $v$ is the characteristic vector of the closed neighbourhood of $v$. Thus, the required set $S$ exists if and only if the all ones vector $\mathbb{1}$ is in the column space of $B$. Since $B$ is symmetric, this is true if and only if $\mathbb{1}$ is in the row space of $B$. Let $B^+$ be the matrix obtained from $B$ by adjoining $\mathbb{1}$ as an additional row. Thus, we can turn all the lights OFF if and only if $B$ and $B^+$ have the same rank.

Since this is a matroid blog, let $M(B)$ and $M(B^+)$ be the column matroids of $B$ and $B^+$ (over $\mathbb{F}_2$). We will prove the stronger result that $M(B)$ and $M(B^+)$ are actually the same matroid. Every circuit of $M(B^+)$ is clearly a dependent set in $M(B)$. On the other hand let $C \subseteq V$ be a circuit of $M(B)$. Then $\sum_{v \in C} \chi(N[v])=\mathbb{0}$, where $\chi(N[v])$ is the characteristic vector of the closed neighbourhood of $v$. Therefore, in the subgraph of $G$ induced by the vertices in $C$, each vertex has odd degree. By the Handshaking Lemma, it follows that $|C|$ is even, and so $C$ is also dependent in $M(B^+)$.

**Reference**

Anderson, M., & Feil, T. (1998). Turning lights out with linear algebra. *Mathematics Magazine*, *71*(4), 300-303.

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

]]>**Definition 1. **A *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].

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

*The partial field $\mathbb{P}_M$ does not depend on the choice of $B$ or $T$.**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}$.**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!

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:

- Compute a Gröbner basis $G$ over the integers for $I_{M,B,T}$.
- If the $G$ contains 1, then $M$ is not representable.
- If the $G$ contains a constant $k > 1$, then the prime factors of $k$ are exactly the characteristics over which $M$ is representable.
- 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.

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

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.

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?

[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 Theory. *PhD Thesis, Eindhoven University of Technology (2009).

]]>

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

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

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

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

]]>