Google Summer of Code

As you might know, SageMath is a software system for mathematical computation. Built on Python, it has extensive libraries for numerous areas of mathematics. One of these areas is Matroid Theory, as has been exhibited several times on this blog.

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!

The Template Theorem

Geelen, Gerards, and Whittle are still working on the write-up of their Herculean effort to build a matroid minor structure theory generalizing the work that Robertson and Seymour did for graphs. One of the consequences of their work has been published, namely a discussion of the highly connected members of a minor-closed class of matroids [1]. This work was mentioned by Peter in passing here and in more detail here. What Peter didn’t talk about was the most detailed version of that structure theorem. Today I will do just that. To keep things light, I will focus on binary matroids, but [1] has results for matroids representable over any finite field.

1. Low-rank perturbations

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.

1.1 Adding a row

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.

1.2 Adding a column

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

1.3 Adding a few elements to a low-rank flat

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.

2. Frame templates

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:

  1. Finite pairwise disjoint sets $C, X, Y_0, Y_1$;
  2. A matrix $A_1$ with rows labeled by $X$ and columns labeled by $Y_0\cup Y_1 \cup C$;
  3. A set of row vectors $\Delta$ closed under addition, with entries labeled by $Y_0 \cup Y_1 \cup C$;
  4. 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

  1. Taking each column from $Z$ and adding to it some column labeled by an element of $Y_1$;
  2. Deleting the columns labeled by $Y_1$;
  3. 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:

  1. Every matroid conforming to $\Phi_i$ is in $\mathcal{M}$ for $i = 1, \ldots, t$;
  2. Every matroid whose dual conforms to $\Psi_j$ is in $\mathcal{M}$ for $j = 1, \ldots, s$;
  3. 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.

References

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

Google Summer of Code

Aside

I’m happy to announce that SageMath’s matroid functionality will be improved again this summer: Zach Gershkoff, a PhD student at Louisiana State University, will work on a dedicated Graphic Matroid class, among other improvements. See the project overview here.

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.

Partial Fields, III. Universal partial fields

I’ve talked about partial fields before here and, earlier, here. A quick refresher:

Definition 1. partial field is a pair $\mathbb{P} = (R,G)$ of a commutative ring $R$ and a subgroup $G$ of the invertible elements of $R$ such that $-1 \in G$.

Definition 2. A matrix $A$ over $R$ is a (strong) $\mathbb{P}$-matrix if every square submatrix has a determinant in $G\cup \{0\}$.

Definition 3. An $r\times n$ matrix $A$ over $R$ is a weak $\mathbb{P}$-matrix if every $r\times r$ square submatrix has a determinant in $G\cup \{0\}$, and at least one such matrix has nonzero determinant.

One can check that, if $D$ is a submatrix with nonzero determinant as in the latter definition, then $D^{-1}A$ represents the same matroid, and is a strong $\mathbb{P}$-matrix. The following was Theorem 10 in Part I:

Proposition 4. If $A$ is a weak $\mathbb{P}$-matrix with columns labeled by a set $E$, then $\mathcal{B} = \{ B \subseteq E : |B| = r, \det(A[B]) \neq 0\}$ is the set of bases of a matroid $M$, denoted $M = M[A]$.

Today, we are interested in the following question: given a matroid $M$, can we find a partial field $\mathbb{P}_M$ that is a “best fit” for $M$? The qualities we are looking for are:

  • $M$ is representable over $\mathbb{P}_M$;
  • We can find (information about) other representations of $M$;
  • We can compute (with) $\mathbb{P}_M$;
  • The representation of $M$ over $\mathbb{P}_M$ is unique.

The fourth property turns out to be impractical, but we can get the first three. This post is based on Section 4 of [PvZ10]; see also Section 3.3 of my thesis [vZ09].

Constructing the universal partial field

Let $M$ be a rank-$r$ matroid with ground set $E$. Fix a basis $B$ of $M$. First, let $D^\#$ be the $B$-fundamental-circuit incidence-matrix (see [Oxl11, p.182]). Recall that any representation of $M$ of the form $[I\ D]$ will have the same zero/nonzero pattern in $D$ as in $D^\#$, and that we can scale rows and columns of $D$ to make certain nonzero entries equal to $1$. Let $T$ be the set of coordinates of a maximal set of coordinates that we can scale to be $1$ (see [Oxl11, Theorem 6.4.7] for details).

Next, for each $x \in B$ and $y \in E-B$ introduce a variable $a_{xy}$; also introduce variables $i_{B’}$ for every basis $B’$ of $M$. Let $\mathcal{Y}$ be the set of all these variables, and consider the ring of polynomials $\mathbb{Z}[\mathcal{Y}]$. Let $\hat D$ be the $B\times (E-B)$ matrix with entries $a_{xy}$, and let $\hat A = [I\ \hat D]$.

Now consider the ideal $I_{M,B,T}$ in $\mathbb{Z}[\mathcal{Y}]$ generated by the following relations:

  • $\det(\hat A[Z])$ for all $r$-subsets $Z\subseteq E$ that are nonbases of $M$;
  • $\det(\hat A[Z])i_Z – 1$ for all bases $Z$ of $M$;
  •  $a_{xy} – 1$ for all $xy \in T$.

Finally, we set $\mathbb{B}_M = \mathbb{Z}[\mathcal{Y}] / I_{M,B,T}$ and the partial field

$$\mathbb{P}_M = (\mathbb{B}_M, \langle \{-1\}\cup \{ i_{B’} : B’ \text{ basis of } M\}\rangle),$$

where $\langle\cdot\rangle$ denotes “multiplicative group generated by”. Note that this formalism is nothing other than introducing notation for the steps you would already take to produce a representation of a given abstract matroid. We have the following nice properties (which I won’t prove):

Proposition 5. Let $M$ be a matroid and $\mathbb{P}_M$, $\hat A$, etc. as above.

  1. The partial field $\mathbb{P}_M$ does not depend on the choice of $B$ or $T$.
  2. If $\mathbb{P}_M$ is not the trivial partial field (that is, if $1 \neq 0$), then $M$ is represented over $\mathbb{P}_M$ by the image $A$ of $\hat A$ under the obvious map from $\mathbb{Z}[\mathcal{Y}] \to \mathbb{Z}[\mathcal{Y}] / I_{M,B,T}$.
  3. If $M$ is represented over a (partial) field $\mathbb{P}$ by a matrix $A’$, then there is a partial field homomorphism $\phi:\mathbb{P}_M\to\mathbb{P}$ with $\phi(A) = A’$.

Here a partial field homomorphism $\phi: (R_1, G_1) \to (R_2, G_2)$ is a ring homomorphism $\phi:R_1 \to R_2$ such that $\phi(G_1) \subseteq G_2$. Such homomorphisms preserve matroids, i.e. $M[A] = M[\phi(A)]$ if $A$ is a $\mathbb{P}$-matrix. This third property earns $\mathbb{P}_M$ the name universal partial field: every representation of $M$ can be obtained from it!

Computation: Baines and Vámos and the set of characteristics

The set of characteristics of a matroid is the subset of $\{p: p = 0$ or $p$ is prime $\}$ such that $M$ has a representation over some field of that characteristic. It is known that the set of characteristics can be any finite subset not containing 0, and any infinite subset containing 0 (see [Oxl11, Section 6.8]). In [BV03], Baines and Vámos gave an algorithm to compute the set of characteristics from the ideal $I_{M,B,T}$ defined above. A brief summary is as follows:

  1. Compute a Gröbner basis $G$ over the integers for $I_{M,B,T}$.
  2. If the $G$ contains 1, then $M$ is not representable.
  3. If the $G$ contains a constant $k > 1$, then the prime factors of $k$ are exactly the characteristics over which $M$ is representable.
  4. Otherwise, let $\gamma$ be the least common multiple of the leading coefficients of the polynomials in $G$. Compute the Gröbner basis for the ideal generated by $G \cup \{\gamma\}$, and let $k$ be its constant member. Then $M$ is representable over characteristic 0 and all prime characteristics, except those dividing $\gamma$ but not $k$.

Note that Gröbner basis computations are notoriously difficult to compute and can take up huge amounts of memory. But for small examples this works well. The Gröbner basis generates the same ideal as the one we started with, and these computations often give a simpler representation of the partial field.

Examples

The universal partial field of $\text{PG}(2,q)$ is $\text{GF}(q)$. The non-Fano matroid and $P_8$ both have the dyadic partial field as their universal partial field, as do the ternary Dowling geometries. The Betsy Ross matroid can be shown to yield the Golden Ratio partial field (that is, it’s representable over $\text{GF}(4)$ and $\text{GF}(5)$), and the matroid represented by the following diagram is representable over the partial field $\mathbb{P}_4$, and is the source of Conjecture 15 in Part I. The matroid was obtained from Gordon Royle, out of his database of matroids with up to 9 elements, through a certain query regarding matroids with only 1 representation over $\text{GF}(5)$.

p4-matroid

Related results and concepts

Many people have devoted attention to the theory of generic representations of a matroid. In [PvZ10] we discuss a construction of the universal partial field that does not rely on the choice of a special basis and scaling set. This construction is built on the idea of a bracket ring, introduced by White [Whi75], where we introduce a variable for each $r$-tuple of elements of $E$, followed by relations that make these $r$-tuples behave like determinants (alternating, 0 for repeated columns, 0 for nonbases, and relations encoding basis exchange). In addition to White’s construction we introduce symbols to make the bracket of each basis invertible.

Dress and Wenzel [DW89] introduce the Tutte Group, which again introduces a symbol for each basis, but only takes multiplicative relations into account. This group has received a considerable amount of attention. In particular the torsion of this group can give information on characteristics over which $M$ is not representable. Dress and Wenzel give a number of constructions of their group, based on various matroid axiomatizations.

Problems

I’ll conclude with some (computational) questions I’ve recently been asking myself.

  • Can we employ scaling techniques as in the definition of $\mathbb{P}_M$ to obtain a (quotient of the) Tutte-group that is faster to compute?
  • Can we combine computations of the Tutte-group with Gröbner basis techniques for a faster computation of the set of characteristics, or to determine whether $M$ is representable over any given finite field?

Unfortunately, $M$ is not always uniquely representable over $\mathbb{P}_M$ (up to partial field automorphisms, row- and column-scaling). The only obstacles I know involve partial fields $\mathbb{P}_M$ with an infinite set of cross ratios, such as the “near-regular-mod-2” partial field. Perhaps unique representability is recovered when the set of cross ratios is finite?

References

[BV03] R. Baines, P. Vámos, An algorithm to compute the set of characteristics of a system of polynomial equations over the integers. J. Symbolic Computat. 35, pp. 269-279 (2003).

[DW89] A.W.M. Dress, W. Wenzel, Geometric Algebra for Combinatorial Geometries. Adv. in Math. 77, pp. 1-36 (1989).

[Oxl11] J. Oxley, Matroid Theory. Second Edition. Oxford University Press (2011).

[PvZ10] R.A. Pendavingh, S.H.M. van Zwam, Confinement of matroid representations to subsets of partial fields. J. Comb. Th. Ser. B, vol. 100, pp. 510-545 (2010).

[Whi75] N.L. White. The bracket ring of a combinatorial geometry. I. Trans. Amer. Math. Soc. 214, pp. 233-248 (1975).

[vZ09] S.H.M. van Zwam, Partial Fields in Matroid TheoryPhD Thesis, Eindhoven University of Technology (2009).