The type of psychological model we consider has three types of variables. Two of them are things one can measure in the lab: independent variables represent factors one can change to affect a subject’s responses, and dependent variables represent the responses. Between these, typically impossible to measure, are *latent variables* — theoretical constructs that can be viewed as depending on the independent variables and determining the dependent variable. For instance, a memory experiment might ask people to memorize words under different conditions (the conditions are independent variables), and then give them a test whose score is the dependent variable. The theoretical construct would describe mental processes involved in memory (the latent variables), which might be changed by changes in the independent variables, and would describe how values of the latent variables determine values of the dependent variables. We assume all latent variables and all dependent variables to be numerical.

If a theory were to propose that the functional relationship between latent and dependent variables has a particular algebraic form, then we could easily test the theory. For instance, if the relationship between the vector $\mathbf{x}$ of latent variables and $\mathbf{y}$ of dependent variables were theorized to be $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{b}$ for some specified matrix $\mathbf{A}$ and vector $\mathbf{b}$, then the theory predicts that each $\mathbf{y}$ will lie in the affine space ${\mathrm{col}}(\mathbf{A})+\mathbf{b}$. If we expanded the theory to leave $\mathbf{b}$ unspecified, then we could still test this theory: it predicts that a set $\{\mathbf{y}_1, \ldots, \mathbf{y}_N\}$ of $N$ measurements of the vector of dependent variables should satisfy $\mathbf{y}_i-\mathbf{y}_j\in{\mathrm{col}}(\mathbf{A})$ for all $i$ and $j$.

But, if you think it seems odd to propose an algebraic relationship between numbers directly describing mental processes and numbers arising as test scores, then you are not alone.

However, in some situations a reasonable theory proposes that the vector of dependent variables $\mathbf{y}$ is related to the vector of latent variables $\mathbf{x}$ by a function \[\mathbf{y}=f(\mathbf{A}\mathbf{x})\]

where $\mathbf{A}$ is a specified matrix and $f$ is a function that the model does not specify but proposes to be *componentwise monotonic*. That is, $f$ is assumed to have the form $f(z_1, \ldots,z_m)=(f_1(z_1),\ldots, f_m(z_m))$, where either each $f_i$ is a strictly monotonically increasing function or each $f_i$ is a strictly monotonically decreasing function. I’ll give some examples of such theories shortly, and I’ll also expand this idea to a broader range of theories. First I’ll discuss how this form of hypothesis leads us to oriented matroids.

**Signed difference analysis**

For a vector $\mathbf{x}\in\mathbb{R}^m$, let $\mathrm{sign}(\mathbf{x})\in\{0,+,-\}^m$ be the componentwise sign. For a vector space $V$, let $\mathcal{V}^*(V)=\{\mathrm{sign}(\mathbf{v}): \mathbf{v}\in V\}$. Thus ${\mathcal{V}}^*(V)$ is the signed covector set of an oriented matroid realized by $V$.

**Proposition 1**([3])

Let $g$ be a function with codomain ${\mathbb{R}^n}$, and let $f:{\mathbb{R}^n}\to{\mathbb{R}^n}$ be a componentwise monotonic function. Then for any $\mathbf{x}$ and $\tilde{\mathbf{x}}$ in the domain of $g$,

\[\mathrm{sign}(f(g(\mathbf{x}))-f(g(\tilde{\mathbf{x}})))=\pm\mathrm{sign}(g(\mathbf{x})-g(\tilde{\mathbf{x}})).\]

This is really more of an observation than a proposition — the proof is immediate. But it tells us that for models of the form I described earlier, oriented matroids provide an appropriate test for the model.

**Corollary 2** Let $\mathbf{A}$ be an $m\times n$ matrix over $\mathbb{R}$, and $f:{\mathbb{R}^n}\to{\mathbb{R}^n}$ a componentwise monotonic function. Then for any $\mathbf{x},\tilde{\mathbf{x}}\in{\mathbb{R}^m}$,

\[\mathrm{sign}(f(\mathbf{A}\mathbf{x})-f(\mathbf{A}\tilde{\mathbf{x}}))\in{\mathcal{V}}^*({\mathrm{col}}(\mathbf{A})).\]

As a very simple example, a theory might propose a single latent variable $x$ such that one’s score at each of several tests is a monotonically increasing function of $x$. Thus one proposes that the vector $\mathbf{y}$ of test scores satisfies

\[\mathbf{y}=f\begin{pmatrix}

\begin{pmatrix}

1\\1\\

\vdots\\1

\end{pmatrix}\mathbf{x}

\end{pmatrix}\]

for some componentwise increasing $f$. Our theory and Corollary 2 says that

if $\mathbf{y}$ is the vector of test scores for Maria and $\tilde{\mathbf{y}}$ is the vector of test scores for Fred, then $\mathrm{sign}(\mathbf{y}-\tilde{\mathbf{y}})^T$ is in $\{(+,\ldots, +), (0,\ldots, 0),(-,\ldots,-)\}$.

This end result is obvious: our original theory was that the test-taker with the larger value of $x$ should do better on all of the tests. The point of bringing this example up is to note that this theory is more realistic than a theory that proposes some specific formula relating latent and dependent variables. By considering only the sign of $\mathbf{y}-\mathbf{y}’$, we discard numerical issues and consider only ordinal relationships between corresponding components of $\mathbf{y}$ and $\mathbf{y}’$.

To add some realism: Perhaps Maria has a larger value of $x$ than Fred, but not all of the tests are sensitive enough to detect her superior skill: on some tests they get the same score. Thus, perhaps $f$ is only componentwise weakly increasing. To encompass this we have the following observation. We order $\{0,+,-\}$ so that 0 is the unique minimum and $+,-$ are incomparable, and we order $\{0,+,-\}^n$ componentwise. For a subset $P$ of $\{0,+,-\}^n$, we will let $P_\downarrow$ be the order ideal of $P$ and $P^\uparrow$ be the filter of $P$. As another easy proposition we have the following.

**Proposition 3** Let $g$ be a function with codomain ${\mathbb{R}^n}$, and let $f:{\mathbb{R}^n}\to{\mathbb{R}^n}$ be a componentwise weakly monotonic function. Then for any $\mathbf{x}$ and $\tilde{\mathbf{x}}$ in the domain of $g$,

\[\mathrm{sign}(f(g(\mathbf{x}))-f(g(\tilde{\mathbf{x}})))\leq\mathrm{sign}(g(\mathbf{x})-g(\tilde{\mathbf{x}})).\]

**Corollary 4** Let $\mathbf{A}$ be an $m\times n$ matrix over ${\mathbb{R}}$, and $f:{\mathbb{R}^n}\to{\mathbb{R}^n}$ a componentwise weakly monotonic function. Then for any $\mathbf{x},\tilde{\mathbf{x}}\in{\mathbb{R}^m}$,

\[\mathrm{sign}(f(\mathbf{A}\mathbf{x})-f(\mathbf{A}\tilde{\mathbf{x}}))\in{\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))_\downarrow.\]

Thus, if we have a theory that proposes that dependent variables $\mathbf{y}$ and latent variables $\mathbf{x}$ are related by $\mathbf{y}=f(\mathbf{A}(\mathbf{x}))$ for some matrix $\mathbf{A}$ and componentwise weakly increasing $f$, and we have data $\{\mathbf{y}_1, \ldots, \mathbf{y}_N\}$, where each $\mathbf{y}_i$ is the vector of dependent variables measured in one trial, then to test our theory we do the following:

- Find all
*signed difference vectors*$\mathrm{sign}(\mathbf{y}_i-\mathbf{y}_j)$. - For each signed difference vector $S$, see if there is a $X\in{\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))$ such that $S$ and $X$ coincide on the support of $S$. Any signed difference vector for which there is no such $X$ is a violation of the model.

We can carry this out more efficiently (at least, when $|{\mathcal{C}}({\mathrm{col}}(\mathbf{A}))|<|{\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))|$) using the following result.

**Proposition 5** ([2]) For any oriented matroid on elements $E$ with signed covector set ${\mathcal{V}}^*$ and signed circuit set ${\mathcal{C}}$, we have that $\{{\mathcal{V}}^*_\downarrow,{\mathcal{C}}^\uparrow\}$ is a partition of $\{0,+,-\}^E$.

Thus Step 2 above can be replaced with

2. For each signed difference vector $S$, see if there is a $Z\in{\mathcal{C}}({\mathrm{col}}(\mathbf{A}))$ such that $S$ and $Z$ coincide on the support of $Z$. Any signed difference vector for which such a $Z$ exists is a violation of the model.

**Example: the Remember-Know problem**

Think about the last time you saw someone and thought, “I know I’ve seen that person before, but I can’t remember where”. Some theories hold that *remembering* — recalling details such as “Oh yeah, I see that person working at the grocery store sometimes” — is an essentially different mental process from *knowing* — having a sense of familiarity without any context around it.

Another theory proposes that the only difference between remembering and knowing is the strength of the recall. More specifically, a *signal detection * model proposes that each of the above questions elicits in your mind a response (a *signal*) of some strength, and that the strength of this signal determines whether you “remember” the answer, merely “know” the answer, or don’t know the answer.

A testable instantiation of this ([2]) is as follows. On Day 1, a subject is given a list of words. On Day 2, the subject is given a new list and is asked, for each word on the new list, whether they “remember” seeing it on the old list, whether they “know” it was there despite not “remembering”, or whether they don’t recall that it was on the list.

A signal detection model theorizes that each word on the new list elicits a signal, so that

- if the word was on the old list, there is a probability distribution $p(s)$ for the strength of this signal, and
- if the word was not on the old list, the probability distribution for the strength of this signal is $p(s+d)$ for some $d$.

The model then says that there are numbers $a<b$ such that the subject will “remember” the word from the list if the strength of the signal is greater than $b$, will merely “know” the word was on the list if the strength was in the interval $[a,b]$, and will not recall the word if the strength is less than $a$.

Often the function $p(x)$ is assumed to be a normal distribution. But there’s frequently little theoretical basis for this assumption, and the use of signed difference analysis allows us to avoid any such assumption. We have latent variables $a$, $b$, and $d$, and we have that

- the probability ${\mathrm{Prob}}(\mbox{rem:true})$ of “remembering” a word that was on the old list is $\int_b^\infty p(t) dt=1-P(b)$. Here $P$ is the cumulative probability distribution for $p$,
- the probability ${\mathrm{Prob}}(\mbox{know:true})$ of either “remembering” or “knowing” a word that was on the old list is $\int_a^\infty p(t) dt=1-P(a)$,
- the probability ${\mathrm{Prob}}(\mbox{rem:false})$ of “remembering” a word that was not on the old list is $\int_b^\infty p(t+d) dt=1-P(b+d)$, and
- the probability ${\mathrm{Prob}}(\mbox{know:false})$ of either “remembering” or “knowing” a word that was not on the old list is $\int_a^\infty p(t+d) dt=1-P(a+d)$.

Let $f(x)=1-P(x)$, a monotonically decreasing function, and let $F:{\mathbb{R}}^4\to R^4$ act by $f$ in each component. Thus our model proposes that

\[\begin{pmatrix}

{\mathrm{Prob}}(\mbox{rem:true})\\

{\mathrm{Prob}}(\mbox{know:true})\\

{\mathrm{Prob}}(\mbox{rem:false})\\

{\mathrm{Prob}}(\mbox{know:false})

\end{pmatrix}

=F\left(\begin{pmatrix}

0&1&0\\

1&0&0\\

0&1&1\\

1&0&1

\end{pmatrix}

\begin{pmatrix}

a\\b\\d

\end{pmatrix}\right).

\]

So, if we conduct this experiment under different conditions (i.e., with different values for the independent variables) and record our data in terms of the four variables on the left-hand side of this equation, the model predicts that the signed differences of data points will be in ${\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))_\downarrow$, where $A$ is the matrix on the right-hand side of the above equation.

This is a pretty low bar: the only two elements of $\{0,+,-\}^4$ which are not in ${\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))_\downarrow$ are $\pm (+,-,-,+)$. But that is part of the point. Previous work had dismissed signal-detection models for the Remember-Know problem based on results of experiments similar to type I’ve described, but their analyses assumed a particular form for the probability distribution $p(x)$, and hence assumed data points must lie on a curve of a certain form. Signed difference analysis suggests that without making such an assumption, a signal-detection model for this problem is very difficult to falsify.

**Nonlinear structure in SDA**

We can broaden signed difference analysis further by considering models of the form $\mathbf{y}=f(g(\mathbf{x}))$, where $\mathbf{y}$ is the vector of dependent variables, $\mathbf{x}$ is the vector of latent variables, $f$ is an unspecified componentwise monotonic function, and $g$ is close enough to some affine function $\mathbf{x}\to\mathbf{A}\mathbf{x}+\mathbf{b}$ that, for all $\mathbf{x}$ and $\tilde{\mathbf{x}}$,

\[\mathrm{sign}(g(\mathbf{x})-g(\tilde{\mathbf{x}}))\in{\mathcal{V}}^*({\mathrm{col}}(A)).\]

Proposition 1 then promises us that for all $\mathbf{x}$ and $\tilde{\mathbf{x}}$,

\[\mathrm{sign}(f(g(\mathbf{x}))-f(g(\tilde{\mathbf{x}})))\in{\mathcal{V}}^*({\mathrm{col}}(A)).\]

For instance, if $g:{\mathbb{R}^m}\to{\mathbb{R}^n}$ is differentiable and the column space $V$ of the Jacobian $Dg$ is constant, then for every $\mathbf{x},\tilde{\mathbf{x}}\in{\mathbb{R}^m}$ and differentiable path $\lambda:[0,1]\to{\mathbb{R}^m}$ from $\mathbf{x}$ to $\tilde{\mathbf{x}}$ we have

\[ g(\tilde{\mathbf{x}})-g(\mathbf{x})=\int_0^1 Dg(\lambda(t))\lambda'(t) dt\in V.\]

For instance, in ([2]) we consider a signal-detection model for inductive and deductive reasoning that predicts data of the form

$\mathbf{y}=f(d,-d,(d-c)/s, -d+c)$, where $d$, $c$, and $s$ are latent variables and $f$ is componentwise monotonic. The Jacobian of the function $g(d,c,s)=(d,-d,(d-c)/s, -d+c)$ is

\[Dg=\begin{pmatrix}

1&0&0\\

-1&0&0\\

1/s&-1/s&{c-d}/s\\

-1&1&0

\end{pmatrix}\]

which has the same column space as

\[\mathbf{A}=\begin{pmatrix}

1&0&0\\

-1&0&0\\

0&0&1\\

0&1&0

\end{pmatrix}\]

and thus for every $(d,c,s)$ and $(\tilde d,\tilde c,\tilde s)$ and every componentwise monotonic $f$, the model proposes that the signed difference $f(g(d,c,s))-f(g(\tilde d,\tilde c,\tilde s))$ is in

${\mathcal{V}}^*({\mathrm{col}}(\mathbf{A}))_\downarrow$.

As another example, one model for reading ([1]) proposes that in reading single words one uses one or both of two skills. To oversimplify a bit, either one sounds out a word phonetically or one compares the word to known words. The model was proposed, in part, to account for cases of acquired dyslexia affecting either ability to read phonetically regular words but not phonetically irregular words or ability to read known words but not phonetically regular unknown words. Let $a$ denote the probability that a particular reader is will be successful at phonetically reading a phonetically regular word, and let $b$ be the probability that this reader will successfully read a word based on comparison to known words. These are the latent variables. Let $\mathbf{y}=(y_1, y_2, y_3)^T$ be the reader’s scores on three tests: $y_1$ is the score on a test of phonetically regular nonsense words, $y_2$ is the score on a test of phonetically irregular common words, and $y_3$ is the score on a test of words that are both phonetically regular and common. The model proposes that $\mathbf{y}=f(a,b,a+b-ab)$, where $f$ is componentwise weakly increasing. The Jacobian of $g(a,b)=(a,b,a+b-ab)$ is

\[Dg=\begin{pmatrix}

1&0\\

0&1\\

1-b&1-a

\end{pmatrix}\]

which no longer has constant column space. However, we can still see that, for all $(a,b)$ and $(\tilde a,\tilde b)\in [0,1]^2$, the sign difference $\mathrm{sign}(g(a,b)-g(\tilde a, \tilde b))$ is in

\[{\mathcal{V}}^*\left({\mathrm{col}}\begin{pmatrix}

1&0\\

0&1\\

1&1

\end{pmatrix}\right)_\downarrow\]

by calculating

\begin{eqnarray*}

g(a,b)-g(\tilde a, \tilde b)&=\int_0^1 Dg(t(\tilde a,\tilde b)+(1-t(a,b))\begin{pmatrix}\tilde a-a\\\tilde b-b\end{pmatrix} dt\\

&=\begin{pmatrix}

1&0\\

0&1\\

\int_0^1 (1-t)b+t\tilde b\ dt&\int_0^1 (1-t)a+t\tilde a\ dt

\end{pmatrix}\begin{pmatrix}\tilde a-a\\\tilde b-b\end{pmatrix}\\

&=\begin{pmatrix}

1&0\\

0&1\\

1-\frac{1}{2}(b+\tilde b)&1-\frac{1}{2}(a+\tilde a)

\end{pmatrix}\begin{pmatrix}\tilde a-a\\\tilde b-b\end{pmatrix}

\end{eqnarray*}

and noting that

\[{\mathcal{V}}^*\left({\mathrm{col}}\begin{pmatrix}

1&0\\

0&1\\

1-\frac{1}{2}(b+\tilde b)&1-\frac{1}{2}(a+\tilde a)

\end{pmatrix}\right)

\subseteq

{\mathcal{V}}^*\left({\mathrm{col}}\begin{pmatrix}

1&0\\

0&1\\

1&1

\end{pmatrix}\right)_\downarrow.\]

As an aside: ${\mathcal{V}}^*({\mathrm{col}}(Dg))$ is constant on $(0,1)^2$, and one might hope that this already implies that all signed differences $\mathrm{sign}(f(g(a,b))-f(g(\tilde a,\tilde b)))$ are in ${\mathcal{V}}^*({\mathrm{col}}(Dg))$. This would render the above integration argument unnecessary. If $Dg$ were rank 1, such a result follows from

the Mean Value Theorem. However, in higher rank this fails — see \cite{DA18} for an example.

**References**

- Coltheart, M., “Cognitive neuropsychology and the study of reading”, in
*Attention and performance XI,*M. I. Posner and O. S. M. Marin, eds. (1985) - Dunn, J. C. and Anderson, L.,
*Signed difference analysis: Testing for structure under monotonicity,*Journal of Mathematical Psychology**85**(2018), 36-54 - Dunn, J. C. and James, R. N.,
*Signed difference analysis: Theory and application,*Journal of Mathematical Psychology**47**(2003), 389–416

Rather than getting into any detail of the proofs, my aim with this post is to give an overview of the motivation (from a connectivity-centric point of view), the results, and give some open questions and conjectures on the topic. Essentially, most of the results follow from repeated use of *orthogonality*: the fact that a circuit and cocircuit of a matroid cannot intersect in a single element.

To start with, let’s consider matroids where every $t$-element subset of the ground set appears in an $\ell$-element circuit and an $\ell$-element cocircuit; for brevity, call these *$(t,\ell)$-matroids*.

For example, wheels and whirls are (1,3)-matroids: every element in a wheel or whirl appears in a triangle (a 3-element circuit) and a triad (a 3-element cocircuit). Excluding the rank-2 wheel, these matroids are 3-connected, and, due to the triangles and triads, deleting or contracting any single element results in a matroid that is no longer 3-connected. Tutte’s Wheels-and-Whirls Theorem states that these are in fact the only 3-connected matroids with no single-element deletion or contraction preserving 3-connectedness.

More generally, one reason why someone might be interested in $(t,\ell)$ matroids is that they would appear as exceptional matroids in chain theorems (results like the Wheels-and-Whirls theorem). For example, any 4-connected (1,4)-matroid has no single-element deletion or contraction that is 4-connected (due to the 4-element circuits and cocircuits), and any 3-connected (2,4)-matroid has no pair of elements whose deletion or contraction remains 3-connected (here we are allowed only to delete both elements, or contract both elements). These may or may not be the only matroids with this property, but they provide a starting point.

So what can we say about (2,4)-matroids? Joel Miller [Miller2014] showed the following:

**Theorem****:**

Let $M$ be a matroid with $|E(M)| \ge 13$. Then $M$ is a (2,4)-matroid if and only if $M$ is a spike.

One way of defining a *spike* (useful for the purposes of this post) is as a matroid with a partition into pairs $(X_1,X_2,\ldots,X_t)$, for some $t \ge 3$, such that for all distinct $i,j \in [t]$, $X_i \cup X_j$ is both a circuit and a cocircuit. Note that all “spikes” in this post are what are sometimes referred to as tipless spikes.

Miller also showed that the bound of 13 is tight, and described all matroids with the (2,4)-property when $|E(M)| \le 12$.

As I mentioned earlier, since spikes are (2,4)-matroids, they have no pair of elements whose deletion or contraction remains 3-connected. In fact, Alan Williams [Williams2015] showed that the only 3-connected matroids having this connectivity property, with $|E(M)| \ge 13$, and no triangles or triads, are spikes. So in this case, (2,4)-matroids are the *only* exceptional matroids appearing in a chain theorem for removing a pair of elements from a 3-connected matroid with no triangles or triads, and retaining 3-connectivity (the caveat being the “no triangles or triads” condition: I’ll touch more on this in the section after next).

With Rutger Campbell, Deborah Chun, Kevin Grace, and Geoff Whittle [BCCGW2018], we generalised Miller’s result as follows.

**Theorem:**

Let $M$ be a matroid, and let $t$ be a positive integer. For each $t$, there exists an $n_t$ such that if $M$ is a matroid with the $(t,2t)$-property and $|E(M)| \ge n_t$, then $M$ has a partition into pairs such that the union of any $t$ pairs is both a circuit and a cocircuit.

We call a matroid a *$t$-spike* if it has a partition $\pi$ into pairs such that the union of any $t$ pairs is both a circuit and a cocircuit.

The infinite family of $t$-spikes is a natural class of $(t,\ell)$-matroids to consider: we also showed there are only finitely many $(t,\ell)$-matroids for $\ell < 2t$. Note that spikes are 2-spikes, and it is not hard to show that 1-spikes are matroids obtained by taking direct sums of $U_{1,2}$. $t$-spikes share some well-known properties of spikes: A $t$-spike $M$ with $r$ legs has rank $r$ (where a *leg* is one of the pairs in the partition $\pi$), and, when $r$ is sufficiently large, $M$ is $(2t-1)$-connected. Moreover, the partition $\pi$ associated with a $t$-spike naturally gives rise to crossing $(2t-1)$-separations (for those familiar with flowers, an appropriate concatenation of $\pi$ is a $(2t-1)$-anemone, following the terminology of [AO2008]).

A $(t+1)$-spike $M_2$ can be obtained from a $t$-spike $M_1$ (with sufficiently many legs), by the following construction. Recall that $M_1’$ is an *elementary quotient* of $M_1$ if there is some single-element extension $M_1^+$ of $M_1$ by an element $e$ such that $M_1^+/e = M_1’$. First, take an elementary quotient of the $t$-spike $M_1$ such that none of the $2t$-element cocircuits (from the union of $t$ legs) are preserved. That is, extend $M_1$ by an element $e$ in such a way that the extension does not preserve any of the $2t$-element cocircuits, and then contract $e$. We then repeat this process in the dual: this corresponds to taking an elementary lift such that none of the $2t$-element circuits are preserved. The resulting matroid is a $(t+1)$-spike. Note that one option for the quotient is to simply truncate (i.e. take a free extension by $e$, and then contract $e$) but there may be others.

For the purposes of this post, I’ll refer to this operation as an *inflation* of a $t$-spike. We showed, in [BCCGW2018], that for $t \ge 1$, any $(t+1)$-spike with $r$ legs can be obtained from a $t$-spike with $r$ legs, by an inflation.

Spikes are ubiquitous in matroid theory; perhaps $t$-spikes may also be an interesting family of matroids.

Recall that spikes (i.e. (2,4)-matroids) are the only 3-connected triangle-and-triad-free matroids with no pair of elements whose deletion or contraction preserves 3-connectivity, when we restrict our attention to matroids on at least 13 elements. What if we want to remove the “triangle-and-triad-free” condition; what additional structures arise? (*)

Certainly wheels and whirls (i.e. (1,3)-matroids) for one, but this is not all. Another example is any matroid where every pair of elements is in a 4-element circuit, and every element is in a triad.

Say that $M$ is a $(t_1,\ell_1,t_2,\ell_2)$-matroid if every $t_1$-element set is in an $\ell_1$-element circuit, and every $t_2$-element set is in an $\ell_2$-element cocircuit (the $(t,\ell)$-matroids considered earlier have $t_1=t_2$ and $\ell_1=\ell_2$). James Oxley, Simon Pfeil, Charles Semple and Geoff Whittle [OPSW2018] showed the following:

**Theorem****:**

For $k=3$ or $k=4$, a $k$-connected matroid with $|E(M)| \ge k^2$ is a $(2,4,1,k)$-matroid if and only if $M \cong M(K_{k,n})$ for some $n \ge k$.

So $M(K_{3,n})$ and $M^*(K_{3,n})$ are answers to (*). But there are other structures that arise that don’t fit the $(t_1,\ell_1,t_2,\ell_2)$-matroid framework, that I won’t go into (for more details, see [BWW2018, Conjecture 7.5]; a conjectured answer to (*)).

Apart from the [OPSW2018] result and the case where $t_1 = t_2$ and $\ell_1 = \ell_2$, these $(t_1,\ell_1,t_2,\ell_2)$-matroids have had little attention, as far as I know. We conjecture the following in [BCCGW2018]:

**Conjecture:**

Any sufficiently large $(t_1,2t_1,t_2,2t_2)$-matroid has a partition into pairs such that the union of any $t_1$ pairs is a circuit, and the union of any $t_2$ pairs is a cocircuit.

If the removing-sets-of-size-$t$-style chain theorems are a bit far-fetched for your taste, I’ll now attempt to return to more traditional single-element deletion/contractions, in a slightly roundabout way.

It seems that obtaining a single-element chain theorem for 4-connectivity in the style of Tutte’s Wheels-and-Whirls Theorem has its difficulties (to put it lightly) — see, for example, [CMO2011] for internally 4-connected binary matroids.

Even if we just consider 4-connected (1,4)-matroids, which we know are matroids with no single-element deletion or contraction that preserves 4-connectedness, this seems like a potentially wild class: it includes $M(K_{4,n})$ and $M^*(K_{4,n})$ for any $n \ge 4$; cycle matroids of grids; or, more generally, take the cycle matroid of any 4-connected 4-regular graph with no 3-cycles, but every edge is in a 4-cycle.

Recall the inflation operation, which we used to obtain a $(t+1)$-spike from a $t$-spike. Using essentially the same operation, we see that (1,6)-matroids are at least as wild as (1,4)-matroids. (I say “essentially the same” here because now we require that the elementary quotient/lift does not preserve the $2t$-element circuits/cocircuits corresponding to consecutive elements in the cyclic ordering.) So any horrors from (1,4)-matroids extend to (1,2t)-matroids for integers $t > 2$. I still reserve some small amount of hope for $(1,2t+1)$-matroids, for $t \ge 2$. But, in general, characterising $(1,t)$-matroids seems difficult, so let’s first look at doing something easier.

Wheels and whirls (that is, (1,3)-matroids) also have the property that there is a cyclic ordering on the elements such that every pair of consecutive elements in the ordering is contained in a triangle, and contained in a triad.

We say that a matroid has the *cyclic $(t-1,t)$-property* if there is an ordering $\sigma$ of the ground set such that every set of $t-1$ consecutive elements in $\sigma$ is contained in a $t$-element circuit and a $t$-element cocircuit.

So wheels and whirls have the cyclic (2,3)-property. Note also that swirls and spikes (i.e. 2-spikes) have the (3,4)-cyclic property. In fact, $t$-spikes have the $(2t-1,2t)$-cyclic property.

Together with Deborah Chun, Tara Fife, and Charles Semple, we proved a characterisation of matroids with the $(t-1,t)$-cyclic property [BCFS2018]. Before I state this, let me give some intuition. Essentially, the result shows that one can think of wheels and whirls as a canonical example of matroids with the $(t-1,t)$-property when t is odd; and swirls as a canonical example when $t$ is even — at least, with regards to how the 3- or 4-element circuits/cocircuits appear in either case. These matroids have not only an ordering that certifies they are $(t-1,t)$-cyclic, but an ordering with a stronger property: for whirls and whirls, any set of $t$ consecutive elements in the ordering is either a (coindependent) circuit or (independent) cocircuit, and these alternate; or for swirls, each set of $t$ consecutive elements in the ordering alternates between being both a circuit and a cocircuit, and being independent and coindependent.

We say that a matroid $M$ is *$t$-cyclic* if there is an ordering $(e_1,e_2,\ldots,e_n)$ of $E(M)$ such that, when $t$ is odd, each set of $t$-consecutive elements $\{e_i,\ldots,e_{i+t-1}\}$ is a (coindependent) circuit when $i$ is odd, and a (independent) cocircuit when $i$ is even; and when $t$ is even, each set of $t$-consecutive elements $\{e_i,\ldots,e_{i+t-1}\}$ is a circuit and a cocircuit when $i$ is odd (and is independent and coindependent when $i$ is even). (Indices are interpreted modulo n.)

**Theorem [BCFS2018]:**

Let $M$ be a matroid with the $(t-1,t)$-property, where $t \ge 3$ and $n \ge 6t-10$. Then $M$ is $t$-cyclic.

A $t$-cyclic matroid with rank $r$ has $2r$ elements, and $t$-cyclic matroids have crossing $t$- or $(t-1)$-separations (when $t$ is odd or even respectively) that can be described in terms of flowers. (For those familiar with flowers: when $t$ is odd, these are daisies; when $t$ is even it is possible, depending on the matroid, to have either daisies or anemones.) One interesting thing to observe is the effect of the parity of $t$.

We can use the construction referred to as inflation to obtain $(t+2)$-cyclic matroids from $t$-cyclic matroids. Maybe we can get all $t$-cyclic matroids this way:

**Conjecture [BCFS2018]:**

Let M be a $t$-cyclic matroid for some $t \ge 2$.

If $t$ is even, then M can be obtained from a spike or a swirl by a sequence of inflations.

If $t$ is odd, then M can be obtained from a wheel or a whirl by a sequence of inflations.

I would be surprised if the odd $t$ case of this conjecture does not hold; I am a bit less confident about the case where $t$ is even.

If you’ve made it this far in the post, the reward is a potentially foolhardy conjecture or two.

As touched on earlier, I think perhaps there is some hope for a “nice” characterisation of $(1,t)$-matroids for odd $t \ge 5$. Here is an optimistic conjecture:

**Conjecture:**

Let $t$ be an odd integer, with $t \ge 3$. There exists an $n_t$ such that whenever $|E(M)| \ge n_t$, $M$ is $t$-cyclic if and only if $M$ is a $(1,t)$-matroid.

In fact, I’m not even aware of sporadic examples.

**Question:**

For odd t, does there exist a matroid $M$ where every element is in a $t$-circuit and $t$-cocircuit, but $M$ is not $t$-cyclic?

[AO2008] J. Aikin, J. Oxley. The structure of crossing separations in matroids. Adv. in Appl. Math. **41** (2008), 10-26.

[BCCGW2018] N. Brettell, R. Campbell, D. Chun, K. Grace, G. Whittle. On a generalisation of spikes. arXiv:1804.06959.

[BCFS2018] N. Brettell, D. Chun, T. Fife, C. Semple. Matroids with a cyclic arrangement of circuits and cocircuits. arXiv:1806.03625.

[BWW2018] N. Brettell, G. Whittle, A. Williams. N-detachable pairs in 3-connected matroids III: the theorem. arXiv:1804.06588.

[CMO2011] C. Chun, D. Mayhew, J. Oxley. A chain theorem for internally 4-connected binary matroids. J. Combin. Theory Ser. B **101** (2011), 141-189.

[Miller2014] J. Miller. Matroids in which every pair of elements belongs to a 4-circuit and a 4-cocircuit. M.Sc. thesis, Victoria University of Wellington, 2014.

[OPSW2018] J. Oxley, S. Pfeil, C. Semple, G. Whittle. Matroids with many small circuits and cocircuits. Submitted.

[Williams2015] A. Williams. Detachable pairs in 3-connected matroids. Ph.D. thesis, Victoria University of Wellington, 2015.

The aim today is to understand the deepest and most important unproved conjecture about infinite matroids, the infinite matroid intersection conjecture. We won’t be looking at progress towards the conjecture today, just approaching the statement from a number of angles and getting a sense of its connections to various very different-looking problems in infinite combinatorics. I hope that by the end of the post you will be convinced, as I am, that it is a deep and compelling problem. Here it is:

*Conjecture (Nash-Williams):* Let $M$ and $N$ be (possibly infinite) matroids on the same ground set $E$. Then there are a subset $I$ of $E$ and a partition of $E$ into sets $P$ and $Q$ such that $I$ is independent in both $M$ and $N$, $I \cap P$ spans $P$ in $M$ and $I \cap Q$ spans $Q$ in $N$.

Like a TARDIS, at a first glance this statement seems simple and perhaps a little odd, and its deeper significance is hidden. To get a sense of that significance, we must go on a long journey and see how it materialises within apparently widely separated worlds.

Our journey begins with the observation that finding good infinite versions of theorems about finite combinatorial objects is hard. All too often, the obvious generalisation is either straightforwardly false or else is a simple consequence of the finite version of the theorem, and as such has no new content.

An example of the latter phenomenon is Menger’s Theorem. If $G$ is a graph and $A$ and $B$ are sets then an $A$-$B$ separator in $G$ is defined to be a set $S$ of vertices of $G$ such that there is no path from $A$ to $B$ in $G – S$. Menger’s theorem states that if $G$ is finite then the minimal size of an $A$-$B$ separator in $G$ is the same as the maximal size of a set of disjoint paths from $A$ to $B$ in $G$.

The obvious way to generalise this statement to infinite graphs would be to simply replace the word ‘size’ with the word ‘cardinality’ in both places where it appears. However, the statement obtained in this way has no more content than the finite version of the theorem. We can see this by considering an $A$-$B$ separator $S$ of minimal cardinality.

If $S$ is infinite, then any set of fewer than $|S|$ paths from $A$ to $B$ uses fewer than $|S|$ vertices, and so cannot be maximal. So in that case the statement is clear, and we can suppose instead that $|S|$ is some natural number $n$. Now for each $m \leq n$ we can easily build a finite subgraph $G_m$ of $G$ in which any $A$-$B$ separator has size at least $m$: we may take $G_0$ to be empty, and build $G_{m+1}$ from $G_m$ by adding a path $P_X$ of $G$ from $A$ to $B$ avoiding each set $X$ of $m$ vertices of $G_m$. Then by Menger’s theorem $G_n$ already contains $n$ disjoint paths from $A$ to $B$.

It was Paul Erdős who saw how to get a much deeper infinite generalisation by first reformulating Menger’s theorem as a structural statement. Suppose that we consider an $A$-$B$ separator $S$ of minimal size and a set $\cal P$ of disjoint paths from $A$ to $B$ of maximal size. Then each path in $\cal P$ contains at least one vertex in $S$, and these vertices must all be distinct since the paths are disjoint. But by Menger’s theorem there can only be as may paths in $\cal P$ as there are vertices in $S$. So $S$ must consist of one vertex on each path in $\cal P$.

So it follows from Menger’s theorem that in a finite graph $G$ we can always find a set $\cal P$ of disjoint $A$-$B$ paths together with an $A$-$B$ separator $S$ consisting of one vertex from each path in $\cal P$. On the other hand, this structural statement also implies Menger’s theorem. After all, if ${\cal P}’$ is a set of disjoint paths from $A$ to $B$ of maximal size and $S’$ is an $A$-$B$ separator of minimal size then $|S’| \leq |S| = |{\cal P}| \leq |{\cal P}’|$. But also $|{\cal P}’| \leq |S’|$ since each path in ${\cal P}’$ must contain a different point of $S’$. So $|{\cal P}’| = |S’|$, as desired.

Erdős’ generalisation of Menger’s theorem is therefore the following structural statement:

*Theorem (Aharoni and Berger):* Let $G$ be a (possibly infinite) graph and let $A$ and $B$ be sets. Then there is a set ${\cal P}$ of disjoint $A$-$B$ paths together with an $A$-$B$ separator $S$ consisting of one vertex from each path in ${\cal P}$.

This statement contains some serious content about the structure of infinite graphs, and it remained open for almost half a century before finally being proved by Aharoni and Berger in 2009 [AB09]. Their proof remains one of the deepest ever given in infinite combinatorics.

Another example of the difficulties of generalisation from finite to infinite objects is given by the tree packing and covering theorems. The tree covering theorem states that a connected graph $G$ is a union of $k$ spanning trees if and only if for any set $X$ of vertices of $G$ the induced subgraph $G[X]$ has at most $k(|X| – 1)$ edges, and the tree packing theorem states that a connected graph $G$ includes $k$ edge-disjoint spanning trees if and only if for any partition $P$ of the vertex set of $G$, the quotient graph $G/P$ has at least $k(|P|-1)$ edges. Here $G/P$ is the graph whose vertices are the partition classes and whose edges are those of $G$ which go between partition classes, with endpoints the partition classes which they join.

Once more, the obvious generalisation of the tree covering theorem to infinite graphs has no more content than the finite version of the theorem; it can be proved from it by a straightforward compactness argument. On the other hand the obvious generalisation of the tree packing theorem to infinite graphs is false; there is a counterexample due to Aharoni and Thomassen [AT89]. And once more, to find the correct infinite version of the theorems we must begin by finding a structural version in the finite case. Indeed, it turns out that the tree packing and covering theorems have a unifying structural generalisation:

*Theorem ([D17, Theorem 2.4.4]):* Let $G$ be a connected finite graph and $k$ a natural number. Then there is a partition $P$ of the vertex set of $G$ such that $G/P$ is a union of $k$ spanning trees and $G[X]$ is connected and has $k$ edge-disjoint spanning trees for each partition class $X$ of $P$.

This tree packing/covering theorem implies both the tree packing theorem and the tree covering theorem. For tree packing, the necessity of the condition is clear, so it suffices to prove sufficiency. We can do this by applying the condition to the partition $P$ given by the tree packing/covering theorem. This gives that $G/P$ has at least $k(|P|-1)$ edges. Since it is a union of $k$ spanning trees, those trees must be edge disjoint. Combining these with the edge-disjoint spanning trees in each $G[X]$ gives $k$ edge-disjoint spanning trees in $G$. The derivation of the tree covering theorem from the packing/covering theorem is similar.

This gives us a nontrivial common generalisation of the tree packing and covering theorems to infinite graphs: we can simply omit the word ‘finite’ from the tree packing/covering theorem. The proof of this generalisation, though much simpler than that for the infinite version of Menger’s theorem, goes beyond the scope of this post.

We have now seen two examples where, to find the correct infinite generalisation of a theorem about finite graphs, it was necessary to first reformulate the finite theorem as a structural result. The same is true for theorems about finite matroids, but in this case something remarkable happens. The infinite structural statement you get is usually just the infinite matroid intersection conjecture!

This is not too surprising for the matroid intersection theorem, since Nash-Williams formulated the intersection conjecture to be an infinite structural generalisation of that statement. Recall that the matroid intersection theorem states that the largest size of a common independent set of two matroids $M$ and $N$ on the same ground set $E$ is the same as the minimum value over all partitions of $E$ into sets $P$ and $Q$ of $r_M(P) + r_N(Q)$. The inequality one way around is clear, since if $I$ is independent in both $M$ and $N$ and $\{P, Q\}$ is a partition of $E$ then $|I| = |I \cap P| + |I \cap Q| \leq r_M(P) + r_N(Q)$. For this inequality to be an equality, we must have that $I \cap P$ spans $P$ in $M$ and $I \cap Q$ spans $Q$ in $N$, just as in the conjecture.

There are some less expected cases. Let’s consider Tutte’s linking theorem, the closest matroidal analogue of Menger’s theorem. Let $M$ be a finite matroid with ground set $E$, and let $A$ and $B$ be disjoint subsets of $E$. Let $E’ := E \setminus (A \cup B)$. Then the *connectivity $\lambda_M(A, B)$ from $A$ to $B$ in $M$* is defined to be the minimal value of $\kappa_M(A \cup P)$ over all bipartitions of $E’$ into sets $P$ and $Q$. Here $\kappa_M$ is the connectivity function of $M$, given by $\kappa_M(X) := r_M(X) + r_M(E \setminus X) – r(M)$. The linking theorem states that the maximum value of $\kappa_N(A)$ over all minors $N$ of $M$ with ground set $A \cup B$ is $\lambda_M(A,B)$.

It turns out that there is a structural analogue of this statement. Each such minor $N$ must have the form $M/I\backslash J$, where $I$ and $J$ form a partition of $E’$. By moving loops of $M/I$ into $J$ if necessary, we may suppose that $I$ is independent. We may now calculate as follows:

$\kappa_{M/I \setminus J}(A) = (r(A \cup I) – |I|) + (r(B \cup I) – |I|) – (r(M) – |I|) \\= (r(A \cup I) – |Q \cap I|) + (r(B \cup I) – |P \cap I|) – r(M) \\ \leq r(A \cup (I \cap P)) + r(B \cup (I \cap Q)) – r(M) \\ \leq r(A \cup P) + r(B \cup Q) – r(M) \\ = \kappa_M(A \cup P)$

So equality of the left and right sides is equivalent to the statement that each inequality in the above calculation is an equality, giving the following four conditions:

- $I \cap P$ spans $P$ in $M/A$
- $I \cap Q$ spans $Q$ in $M/B$
- $I \cap P$ is independent in $M/(B \cup (I \cap Q))$
- $I \cap Q$ is independent in $M/(A \cup (I \cap P))$

The outlines of our TARDIS are beginning to materialise. Indeed, consider a minimal set $I$ satisfying these conditions. By minimality, $I \cap P$ will be independent in $M/A$ and $I \cap Q$ will be independent in $M/B$. Thus $I$ itself will be independent in both matroids. To put it another way, $I$, $P$ and $Q$ will witness that $M/A \backslash B$ and $M \backslash A/B$ satisfy the matroid intersection conjecture.

Thus the infinite generalisation of Tutte’s linking theorem is the statement that, for any (possibly infinite) matroid $M$ and any disjoint sets $A$ and $B$ of elements of $M$, the matroids $M/A\backslash B$ and $M \backslash A/B$ satisfy the infinite matroid intersection conjecture. Given this connection, it should not be too surprising that Aharoni and Berger’s infinite generalisation of Menger’s theorem follows from the infinite matroid intersection conjecture. Precise details of the derivation can be found in [ACF18].

What about the tree packing and covering theorems? Their matroidal analogues are the base packing and covering theorems, which in their full generality apply to a list $M_1, M_2, \ldots M_k$ of finite matroids on a common ground set $E$. A *base packing* for such a list is a collection of disjoint bases, one from each $M_i$. A *base covering* for such a list is a collection of bases, one from each $M_i$, whose union is the whole of $E$. The base packing theorem states that there is a base packing precisely when for any subset $Q$ of $E$ we have $\sum_{i = 1}^k r(M_i.Q) \leq |Q|$, and the base covering theorem states that there is a base covering precisely when for any subset $P$ of $E$ we have $\sum_{i = 1}^k r(M_i | P) \geq |P|$.

Once more we can combine these statements into a unified structural statement, the base packing/covering theorem, which states that given such a list of finite matroids on $E$ we can find a bipartition of $E$ into sets $P$ and $Q$ such that the matroids $M_1 | P, \ldots M_k | P$ have a packing and the matroids $M_1.Q, \ldots M_k.Q$ have a covering. The derivations of the base packing and covering theorems from this statement are analogous to the derivation of the tree packing theorem from the tree packing/covering theorem above. So the infinite version of the base packing and covering theorems is given by the same statement applied to a family of infinite matroids. We shall call this the base packing/covering conjecture.

Let’s consider the special case $k = 2$ in more detail. The existence of a packing for $M_1 | P$ and $M_2 | P$ is equivalent to the existence of a subset $I_P$ of $P$ such that $I_P$ spans $P$ in $M_1$ and $P \setminus I_P$ spans $P$ in $M_2$. Similarly the existence of a covering for $M_1.Q$ and $M_2.Q$ is equivalent to the existence of a subset $I_Q$ of $Q$ such that $I_Q$ is independent in $M_1/P$ and $Q \setminus I_Q$ is independent in $M_2/P$. Since a set is independent in a matroid precisely when its complement is spanning in the dual matroid, we can rephrase these conditions as follows:

- $I_P$ spans $P$ in $M_1$
- $I_Q$ spans $Q$ in $M_2^*$
- $I_P$ is independent in $M_2^*/Q$
- $I_Q$ is independent in $M_1/P$

Once again, as if from nowhere, the TARDIS appears. If we choose $I_P$ and $I_Q$ minimal subject to conditions (i) and (ii) then they will still satisfy conditions (iii) and (iv), which will guarantee that $I:=I_P \cup I_Q$ is independent in both $M_1$ and $M_2^*$, meaning that $I$, $P$ and $Q$ witness that $M_1$ and $M_2^*$ satisfy the infinite matroid intersection conjecture.

The TARDIS not only appears in unexpected places, it is also bigger on the inside than it seems. For example, the remarks in the last couple of paragraphs only apply to pairs of matroids, that is, to lists of length 2. But in fact it is possible to derive the full base packing/covering conjecture from the special case of pairs, and hence from the infinite matroid intersection conjecture. We will see the reasons for this when we look at the structure of the conjecture more closely in the next post in the series. For now we just note the consequence that the tree packing/covering theorem mentioned earlier also follows from the infinite matroid intersection conjecture.

We have seen how the infinite matroid intersection conjecture arises naturally as the infinite structural analogue of the matroid intersection theorem, the linking theorem, and the base packing and covering theorems. The same also holds for the matroid union theorem, which we do not have space to discuss here [BC15]. Thus the process of finding an infinite generalisation of all these statements reveals their unified structural heart. In the next post we will examine that structural heart more closely, looking at just what sort of structure the conjecture gives us, and we will survey the special cases for which the conjecture is already known.

Bibliography:

[AB09] R. Aharoni and E. Berger, Menger’s Theorem for Infinite Graphs, Inventiones mathematicae 176(1):1–62 (2009).

[ACF18] E. Aigner-Horev, J. Carmesin and J.-O. Fröhlich, On the Intersection of Infinite Matroids, Discrete Mathematics 341(6):1582-1596 (2018).

[AT89] R. Aharoni and C. Thomassen, Infinite, highly connected digraphs with no two arc-disjoint spanning trees. J. Graph Theory, 13:71–74 (1989).

[BC15] N. Bowler and J. Carmesin, Matroid Intersection, Base Packing and Base Covering for Infinite Matroids, Combinatorica 35(2):153-180 (2015).

[D17] R. Diestel, Graph Theory, 5th edition, Springer-Verlag (2017).

]]>Decomposition-width has a very natural motivation if you are familiar with matroids representable over finite fields, and matroid branch-width. Consider the following geometric illustration of the binary matroid $AG(3,2)$. The ground set has been partitioned into the sets $U$ and $V$. Let $X$ stand for the set of points coloured purple, and let $X’$ stand for the set of orange points. In the lefthand diagram, $V$ can distinguish between $X$ and $X’$. By this I mean that there is a subset $Z\subseteq V$ (we colour the points in $Z$ green) such that $X\cup Z$ is a circuit while $X’\cup Z$ is independent. However, in the righthand diagram, no subset of $V$ can distinguish $X$ and $X’$ in this way. Geometrically, this is because $X$ and $X’$ span exactly the same subset of the three-point line that lies in the spans of both $U$ and $V$ in the ambient binary space.

In general, let $M$ be a matroid on the ground set $E$, and let $(U,V)$ be a partition of $E$. We define the equivalence relation $\sim_{U}$ on subsets of $U$. We write $X\sim_{U} X’$ to mean that whenever $Z$ is a subset of $V$, both $X\cup Z$ and $X’\cup Z$ are independent, or neither is. This is clearly an equivalence relation.

Now we consider branch-width and decomposition-width. A *decomposition* of a matroid, $M=(E,\mathcal{I})$, consists of a pair $(T,\varphi)$, where $T$ is a binary tree (by this I mean that every vertex has degree one or three), and $\varphi$ is a bijection from $E$ to the set of leaves of $T$. If $e$ is an edge of $T$ joining vertices $u$ and $v$, then let $U_{e}$ be the subset containing elements $z\in E$ such that the path in $T$ from $\varphi(z)$ to $u$ does not contain $v$. Define $V_{e}$ symmetrically. We say that $U_{e}$ and $V_{e}$ are *displayed* by the decomposition. Define $\operatorname{bw}(M;T,\varphi)$ to be the maximum of $r(U_{e})+r(V_{e})-r(M)+1$, where the maximum is taken over all edges $e$ with end-vertices $u$ and $v$. Now I will define $\operatorname{dw}(M;T,\varphi)$ to be the maximum number of equivalence classes under the relation $\sim_{U_{e}}$, where we again take the maximum over all displayed sets $U_{e}$. The *branch-width* of $M$ is the minimum of $\operatorname{bw}(M;T,\varphi)$, where the minimum is taken over all decompositions $(T,\varphi)$. We define the *decomposition-width* of $M$ in the same way: as the minimum value taken by $\operatorname{dw}(M;T,\varphi)$. We write $\operatorname{bw}(M)$ and $\operatorname{dw}(M)$ for the branch- and decomposition-widths of $M$.

The notion of decomposition-width is clearly motivated by matroids over finite fields, but I won’t discuss those applications now. Instead we will continue to look at more abstract properties of decomposition-width. Král proved this next result for matroids representable over finite fields.

**Proposition 1.** Let $M$ be a matroid. Then $\operatorname{dw}(M)\geq \operatorname{bw}(M)$.

*Proof.* Let $E$ be the ground set of $M$, and let $U$ be a subset of $E$. Recall that $\lambda(U)$ is $r(U)+r(E-U)-r(M)$. We will start by proving that $\sim_{U}$ has at least $\lambda(U)+1$ equivalence classes. Define $V$ to be $E-U$. Let $B_{V}$ be a basis of $M|V$, and let $B$ be a basis of $M$ that contains $B_{V}$. Then $B\cap U$ is independent in $M|U$, and

\begin{align*}

r(U)-|B\cap U| &=r(U)-(|B|-|B_{V}|)\\

&=r(U)-(r(M)-r(V))\\

&=r(U)-(r(U)-\lambda(U))\\

&=\lambda(U).

\end{align*}

Therefore we let $(B\cap U)\cup\{x_{1},\ldots, x_{\lambda(U)}\}$ be a basis of $M|U$, where $x_{1},\ldots, x_{\lambda(U)}$ are distinct elements of $U-B$. Next we construct a sequence of distinct elements, $y_{1},\ldots, y_{\lambda(U)}$ from $B_{V}$ such that $(B-\{y_{1},\ldots, y_{i}\})\cup\{x_{1},\ldots, x_{i}\}$ is a basis of $M$ for each $i\in\{0,\ldots, \lambda(U)\}$. We do this recursively. Let $C$ be the unique circuit contained in\[(B-\{y_{1},\ldots, y_{i}\})\cup\{x_{1},\ldots, x_{i}\}\cup x_{i+1}\] and note that $x_{i+1}$ is in $C$. If $C$ contains no elements of $B_{V}$, then it is contained in $(B\cap U)\cup\{x_{1},\ldots, x_{\lambda(U)}\}$, which is impossible. So we simply let $y_{i+1}$ be an arbitrary element in $C\cap B_{V}$.

We complete the claim by showing that $(B\cap U)\cup\{x_{1},\ldots,x_{i}\}$ and $(B\cap U)\cup\{x_{1},\ldots, x_{j}\}$ are inequivalent under $\sim_{U}$ whenever $i< j$. Indeed, if $Z=B_{V}-\{y_{1},\ldots, y_{i}\}$, then $(B\cap U)\cup\{x_{1},\ldots, x_{i}\}\cup Z$ is a basis of $M$, and is properly contained in $(B\cap U)\cup\{x_{1},\ldots, x_{j}\}\cup Z$, so the last set is dependent, and we are done.
Now assume for a contradiction that $\operatorname{bw}(M)>\operatorname{dw}(M)$. Let $(T,\varphi)$ be a decomposition of $M$ such that if $U$ is any set displayed by an edge of $T$, then $\sim_{U}$ has at most $\operatorname{dw}(M)$ equivalence classes. There is some edge $e$ of $T$ displaying a set $U_{e}$ such that $\lambda(U_{e})+1>\operatorname{dw}(M)$, for otherwise this decomposition of $M$ certifies that

$\operatorname{bw}(M)\leq \operatorname{dw}(M)$. But $\sim_{U_{e}}$ has at least $\lambda_{M}(U_{e})+1$ equivalence classes by the previous claim. As $\lambda_{M}(U_{e})+1>\operatorname{dw}(M)$, this contradicts our choice of $(T,\varphi)$. $\square$

Král states the next result without proof.

**Proposition 2.** Let $x$ be an element of the matroid $M$. Then $\operatorname{dw}(M\backslash x) \leq \operatorname{dw}(M)$ and

$\operatorname{dw}(M/x) \leq \operatorname{dw}(M)$.

*Proof.* Let $(T,\varphi)$ be a decomposition of $M$ and assume that whenever $U$ is a displayed set, then $\sim_{U}$ has no more than $\operatorname{dw}(M)$ equivalence classes. Let $T’$ be the tree obtained from $T$ by deleting $\varphi(x)$ and contracting an edge so that every vertex in $T’$ has degree one or three. Let $U$ be any subset of $E(M)-x$ displayed by $T’$. Then either $U$ or $U\cup x$ is displayed by $T$. Let $M’$ be either $M\backslash x$ or $M/x$. We will show that in $M’$, the number of equivalence classes under $\sim_{U}$ is no greater than the number of classes under $\sim_{U}$ or $\sim_{U\cup x}$ in $M$. Let $X$ and $X’$ be representatives of distinct classes under $\sim_{U}$ in $M’$. We will be done if we can show that these representatives correspond to distinct classes in $M$. Without loss of generality, we can assume that $Z$ is a subset of $E(M)-(U\cup x)$ such that $X\cup Z$ is independent in $M’$, but $X’\cup Z$ is dependent. If $M’=M\backslash x$, then $X\cup Z$ is independent in $M$ and $X’\cup Z$ is dependent, and thus we are done. So we assume that $M’=M/x$. If $U$ is displayed by $T$, then we observe that $X\cup (Z\cup x)$ is independent in $M$, while $X’\cup (Z\cup x)$ is dependent. On the other hand, if $U\cup x$ is displayed, then $(X\cup x)\cup Z$ is independent in $M$ and $(X’\cup x)\cup Z$ is dependent. $\square$

When we combine Propositions 1 and 2, we see that the class of matroids with decomposition-width at most $k$ is a minor-closed subclass of the matroids with branch-width at most $k$. The class of matroids with branch-width at most $k$ has finitely many excluded minors [GGRW03]. In contrast to this, Mike and I convinced ourselves that there are classes of the form $\{M\colon \operatorname{dw}(M) \leq k\}$ with infinitely many excluded minors. I guess we’d had a couple of beers by that point, but I think our argument holds up. I’ll eventually add that argument to this post. If anyone presents a proof in the comments before I do then I will buy them a drink at the next SIGMA meeting.

**References**

[GGRW03] J. F. Geelen, A. M. H. Gerards, N. Robertson, and G. P. Whittle. On the excluded minors for the matroids of branch-width $k$. *J. Combin. Theory Ser. B* **88** (2003), no. 2, 261–265.

[Kra12] D. Král. Decomposition width of matroids. *Discrete Appl. Math.* **160** (2012), no. 6, 913–923.

[Str10] Y. Strozecki. *Enumeration complexity and matroid decomposition.* Ph.D. thesis, Université Paris Diderot (2010).

[Str11] Y. Strozecki. Monadic second-order model-checking on decomposable matroids. *Discrete Appl. Math.* **159** (2011), no. 10, 1022–1039.

The team of core contributors has changed a little; we’re sorry to say goodbye to Stefan van Zwam and Irene Pivotto, who put a lot of energy into making this blog what it is. But we have some fresh new contributors: Laura Anderson and Nick Brettell. You can get some idea of what topics we are each hoping to cover here. A variety of other topics will be covered by guest posts. If you have any ideas for topics which you would like to see on the blog, or even which you would like to write about yourself, then please get in touch.

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

]]>