1. Introduction

In this post I’ll highlight some new constructions related to matroid lifts as detailed in the recent papers [Wal22] and [BW23]. If a matroid $M$ is represented by a matrix $A$, one can naturally obtain a new matroid $L$ by adding rows to $A$ as in Figure 1.

Certainly $M$ and $L$ have a special relationship, which can be defined for general matroids as follows.

Definition 1: Given matroids $M$ and $L$ on a common ground set $E$, we say that $L$ is a lift of $M$ (and $M$ is a projection or quotient of $L$) if there exists a matroid $K$ on ground set $E \cup F$ such that $M = K / F$ and $L = K \setminus F$. We say that $L$ is a rank-$k$ lift of $M$ if $r(L) – r(M) = k$.

Continuing with the example in Figure 1, the matroid $K$ could be represented by the matrix obtained from $A’$ by appending the first $k$ unit column vectors. Rank-$1$ lifts, called elementary lifts, are well understood. A classical theorem of Brylawski [Bry86], which was previously stated in the dual by Crapo [Cra65], says that elementary lifts of a matroid $M$ are in bijection with special sets of circuits of $M$.

Theorem 1 (Crapo-Brylawski): Let $M$ be a matroid on ground set $E$ and let $\mathcal C$ be a set of circuits of $M$ so that

• if $C_1,C_2$ are circuits in $\mathcal C$ for which $|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$, then each circuit $C$ of $M$ contained in $C_1 \cup C_2$ is also in $\mathcal C$.

Then the function $r \colon 2^E \to \mathbb Z$ defined, for all $X \subseteq E$, by

$$r(X) = \bigg\{\begin{array}{cc}  r_M(X) & \textrm{if each circuit of $M|X$ is in $\mathcal C$} \\r_M(X) + 1 & \textrm{otherwise} \end{array}$$

is the rank function of an elementary lift of $M$. Moreover, every elementary lift of $M$ can be obtained in this way.

The set $\mathcal C$ is a linear class of circuits of $M$, and the pair $(C_1, C_2)$ is a modular pair of circuits. This theorem was famously used by Zaslavsky to define the lift matroid of a biased graph [Zas91]. A wonderful introduction to biased graphs and their associated matroids can be found elsewhere on this blog. Since Theorem 1 has proved to be an important characterization of elementary lifts, [Wal22] and [BW23] focused on the following questions.

Question 1: Is there a construction that generalizes the Crapo-Brylawski construction to non-elementary lifts? If so, can every matroid lift be obtained via this construction?

We shall see that the answer to the first question is “yes”, the answer to the second question is “no”, and the matroids used to certify the “no” answer form an interesting infinite antichain of non-representable sparse paving matroids.

2. The construction

The Crapo-Brylawski construction was generalized to non-elementary lifts in [Wal22, Theorem 2], and this construction was stated in the following simpler form in [BW23, Theorem 2].

Theorem 2: Let $M$ be a matroid on ground set $E$ and let $N$ be a matroid whose ground set is the circuit set of $M$ so that

• $(*)$ if $C_1,C_2$ are circuits of $M$ for which $|C_1 \cup C_2| – r_M(C_1 \cup C_2) = 2$, then each circuit $C$ of $M$ contained in $C_1 \cup C_2$ satisfies $C \in \textrm{cl}_N(\{C_1, C_2\})$.

Then the function $r \colon 2^E \to \mathbb Z$ defined, for all $X \subseteq E$, by

$$r(X)=  r_M(X) + r_N(\{C \colon \textrm{$C$ is a circuit of $M|X$}\})$$

is the rank function of a rank-$r(N)$ lift of $M$. 

Roughly speaking, the matroid $N$ tells us the rank increase of each set in the lift of $M$, and condition $(*)$ is necessary because certain triples of circuits are naturally `dependent’. Condition $(*)$ also implies that the set of loops of $N$ is a linear class of circuits of $M$, and so the case when $r(N) = 1$ is precisely the Crapo-Brylawski construction. We write $M^N$ for the matroid constructed in Theorem 2. There are natural choices for a matroid $N$ satisfying the hypothesis of Theorem 2, such as the derived matroids of [Lon80], [OW22], and [FJK22], and rank-$2$ uniform matroids. However, the motivation for Theorem 2 was its application to gain graphs, as illustrated in the following example.

Example 1. Let $G$ be a graph with edges labeled by elements of $\mathbb Z_2^j$ (the direct sum of $j$ copies of the cyclic group of order $2$), or equivalently with vectors in the binary vector space $\mathbb F_2^j$ (see Figure 2). Then associating each cycle of $G$ with the sum of the vectors on its edges defines a (binary) matroid $N$ on the set of cycles of $G$. It is straightforward to check that $N$ satisfies $(*)$, and so Theorem 2 gives a rank-$r(N)$ lift of $M(G)$, the graphic matroid of $G$.

 

The previous example works more generally for groups of the form $\mathbb Z_p^j$ for a prime $p$ and integer $j \ge 1$ [Wal22, Theorem 3], and generalizes Zaslavsky’s construction of the lift matroid of a gain graph [Zas91] for these special groups. And, surprisingly, non-elementary lifts with a certain natural property only exist for gain graphs over groups of this special form [WB23, Theorem 6]. But we shall save this discussion for a future blog post!

3. The converse

Now that we have Theorem 2 as a generalization of the Crapo-Brylawski construction to non-elementary lifts, we move on to the second part of Question 1: can every lift be obtained via this construction? It was conjectured in [Wal22, Conjecture 6] that the answer is “yes”; i.e. that for every matroid $K$ and subset $X$ of $E(K)$, there is a matroid $N$ on the circuits of $K/X$ so that $(K/X)^N \cong K \backslash X$. This is true when $K$ is representable, and straightforward to prove [WB23, Proposition 9].

Proposition 1. Let $K$ be an $\mathbb F$-representable matroid and let $X$ be a subset of its ground set. Then there exists an $\mathbb F$-representable matroid $N$ on the circuits of $K/X$ such that $(K/X)^N \cong K \backslash X$.

However, it is false in general! We next construct a family of sparse paving matroids to show this. (A rank-$r$ matroid is sparse paving if every $r$-element subset is a basis or a circuit-hyperplane.) As we shall see, these matroids generalize the cyclic arrangement of the circuit-hyperplanes of the Vámos matroid.

Definition 2. Let $r \ge 4$ and $t \ge 3$ be integers satisfying $r \le 2t-2$. For $i = 1,\dots, t$, let $C_i \subseteq [2t]$ be defined as $C_i = \{1+2(i-1),\dots, (r-2) + 2(i-1)\}$ with numbers taken cyclically modulo $2t$. Then define:

• $X = \{2t+1,2t+2\}$,
• $\mathcal C'(r,t) = \{C_i \cup X \colon i \in [t]\}$, and
• $\mathcal C^{”}(r,t) = \{C_i \cup C_{i+1} \colon i \in [t – 1]\}$.

Then $\mathcal C'(r,t) \cup \mathcal C^{”}(r,t)$ is the set of circuit-hyperplanes of a sparse paving matroid $K(r,t)$ [WB23, Proposition 11]. 

The key feature is that $C_1 \cup C_t$ is not a circuit-hyperplane of $K(r,t)$. As a concrete example, when $r = 4$ and $t = 3$ we have $\mathcal C'(r,t) = \{1278, 3478, 5678\}$ and $\mathcal C^{”}(r,t) = \{1234, 3456\}$, and we leave it to the reader to check that $K(4,3)$ is isomorphic to the Vámos matroid. Figure 3 illustrates the cyclic nature of the sets $C_i$ in $K(r,t)$ (which are also the circuit-hyperplanes of $K(r,t)/X$).

We now use $K(r,t)$ to show that the construction of Theorem 2 is not a characterization of matroid lifts [WB23, Theorem 12].

Theorem 3. Let $r \ge 4$ and $t \ge 3$ be integers satisfying $r \le 2t-2$. There is no matroid $N$ on the circuits of $K(r,t)/X$ for which $K(r,t)\backslash X$ is isomorphic to $(K(r,t)/X)^N$. Moreover, $K(r,t)$ is not representable over any field.

proof. Let $K = K(r,t)$, $M = K/X$, and $L = K \backslash X$, so $L$ is a rank-$2$ lift of $M$.
It is straightforward to check the following properties from Definition 2.

1. $(C_i , C_{i+1})$ is a modular pair of circuits of $M$ for each $i \in [t-1]$,

2. $(C_1, C_t)$ is a modular pair of circuits of $M$,
   
   

3. $r_L(C_i \cup C_{i+1}) – r_M(C_i \cup C_{i+1}) = 1$ for each $i \in [t-1]$, and

4. $r_L(C_1 \cup C_{t}) – r_M(C_1 \cup C_{t}) = 2$.

Suppose $N$ exists. For each $i \in [t]$, the set $C_i$ is a circuit of $M$ and is independent in $L$ and is therefore a non-loop of $N$ by the rank function of $M^N$. Properties (a) and (c) and the rank function of $M^N$ imply that $C_i$ and $C_{i+1}$ are parallel in $N$ for all $i \in [t-1]$, and so $C_1$ and $C_t$ are parallel in $N$. But (b) and (d) and the rank function of $M^N$ imply that $C_1$ and $C_t$ are independent in $N$, a contradiction. Proposition 1 now implies that $K(r,t)$ is non-representable. $\Box$

We have now answered Question 1. We comment that while $K(r,t)$ is constructed using rank-$2$ lifts, related constructions using rank-$k$ lifts with $k > 2$ are likely possible as well, and we hope that this method can be used to construct interesting classes of non-representable matroids. To illustrate this, we mention a few interesting properties of $K(r,t)$. Note that when $r \ge 5$ and $r \le 2t – 3$, the matroid $K(r,t)$ has rank and corank at least $5$. The following is [BW23, Propositions 13, 15] and can be proved using techniques from [NV18].

Proposition 2. $\{K(r,t) \colon t \ge 3 \textrm{ and } 5 \le r \le 2t – 3\}$ is an infinite antichain of non-representable sparse paving matroids that do not violate Ingleton’s inequality.

This is interesting because while $K(r,t)$ is inspired by the Vámos matroid, the Vámos matroid violates Ingleton’s inequality. We also conjecture that any matroid obtained from $K(r,t)$ by relaxing a circuit-hyperplane into a basis is representable [BW23, Conjecture 14]. This may not even be difficult to prove for an expert on sparse paving matroids.

Finally, the fact that the converse of Theorem 2 is true for representable matroids but false in general leads to the following question. 

Question 2: Which matroids $K$ have the property that for every set $X \subseteq E(K)$ there is a matroid $N$ on the circuits of $K/X$ so that $(K/X)^N \cong K \backslash X$?

For example, if every algebraic matroid has this property then $K(r,t)$ would be non-algebraic for all $r \ge 4$ and $t \ge 3$. This may be a promising direction since the Vámos matroid is non-algebraic [IM75] and isomorphic to $K(4,3)$.

References

[BW23] D. I. Bernstein, Z. Walsh. Matroid lifts and representability. arXiv preprint arXiv:2306.12543.

[Bry86] T. H. Brylawski. Constructions. In Theory of matroids (ed. N. White), pp. 127-223. Cambridge University Press, Cambridge, 1986.

[Cra65] H. H. Crapo. Single-element extensions of matroids. J. Res. Nat. Bur. Standards Sect. B, 69B:55–65, 1965.

[Ing71] A. W. Ingleton. Representations of matroids. In D. J. A. Welsh, editor, Combinatorial mathematics and its applications (Proceedings of a conference held at theMathematical Institute, Oxford, from 7-10 July, 1969). Academic Press, 1971.

[IM75] A. W. Ingleton and R. A. Main. Non-algebraic matroids exist. Bull. London Math. Soc., 7:144-146, 1975.

[Lon80] J. Q. Longyear. The circuit basis in binary matroids. J. Number Theory, 12:71-76, 1980.

[NV18] P. Nelson and J. van der Pol. Doubly exponentially many Ingleton matroids. SIAM J. Disc. Math., 32(2):1145-1153, 2018.

[OW19] J. Oxley, S. Wang. Dependencies among dependencies in matroids. Electron. J. Combin., 26, 2019.

[FJK22] Freij-Hollanti, R. Jurrius, and O. Kuznetsova. Combinatorial derived matroid. arXiv preprint arXiv:2206.06881, 2022.

[Wal22] Z. Walsh. A new matroid lift construction and an application to group-labeled graphs. Electr. J. Combin., 29, 2022.

[Zas91] T. Zaslavsky. Biased graphs. II. The three matroids. J. Combin. Theory Ser. B, 51:46-72, 1991.