Happy New Year from all of us at the Matroid Union!

Decomposition of objects into smaller or simpler objects is a central theme in combinatorics. Think about decomposing a graph into its connected components or blocks, or into forests. In today’s post, I discuss decomposing finite projective geometries into projective geometries of smaller rank.

Definition: Let $q$ be prime power, let $n \ge t \ge 1$ be integers and let $M = \text{PG}(n-1,q)$ be the projective geometry over the field with $q$ elements. A $t$-spread of $G$ is a collection of rank-$t$ flats of $M$ that partition the points of $M$—that is, these flats are pairwise disjoint and their union is the set of all points of $M$.

(Geometers often use dimension instead of rank; the dimension of a projective geometry is one less than its rank. Their $t$-spreads are collections of $t$-dimensional subspaces of an $n$-dimensional space. We will however stick to the terminology that is more familiar in the matroid theory setting.)

Every projective geometry has a 1-spread: the flats making up the spread are simply the points of the geometry. It is much more interesting to look into the existence of $t$-spreads when $t \ge 2$.

The Fano plane $F_7 = \text{PG}(2,2)$ does not admit a decomposition into triangles. The quickest argument to see this is based on counting the number of points: any matroid that can be decomposed into triangles necessarily has a number of points that is a multiple of 3, but the Fano plane has seven points. By contrast, the projective geometry $\text{PG}(3,2)$, which has fifteen points, can be partitioned into five triangles (as encoded using different colours in the following representation:

The counting argument above can be generalised. In order for $M = \text{PG}(n-1,q)$ to have any hope of admitting a $t$-spread, the number of points in a projective geometry of rank $t$ should evenly divide the number of points in $M$, or $\frac{q^t-1}{q-1} \bigg| \frac{q^n-1}{q-1}$. It is a nice exercise to show that the latter happens precisely when $n$ is a multiple of $t$. So, if $\text{PG}(n-1,q)$ can be decomposed into rank-$t$ subgeometries, we must have $t|n$.

It turns out that this divisibility criterion is not only necessary—it is sufficient as well. We end this blog post with a slick proof of this fact. The proof can be found in many introductory texts on projective geometry.

Theorem: The projective geometry $M=\text{PG}(n-1,q)$ admits a $t$-spread if and only if $t|n$.

Proof: We already proved the implication from left to right. The implication in the other direction follows from a construction.

Suppose that $n = kt$ for some integer $k$. The points of $M$ can be identified with the 1-dimensional subspaces of the vector space $\mathbb{F}_q^n$. We will show that $\mathbb{F}_q^n$ can be decomposed into $t$-dimensional subpspaces that are pairwise disjoint (except that they all contain the zero-vector). As the 1-dimensional subspaces of $\mathbb{F}_q^t$ can be identified with the points of a $\text{PG}(t-1,q)$, this immediately implies the theorem.

Consider the $k$-dimensional $\mathbb{F}_{q^t}$-vector space $\mathbb{F}_{q^t}^k$. Its 1-dimensional subspaces intersect only in the zero-vector. These 1-dimensional subspaces give us our spread, as each such subspace can alternatively be viewed as a $t$-dimensional $\mathbb{F}_q$-vector space. $\Box$

Looking back over the series of all posts so far on infinite matroids, you might notice (as I did) that there is a central theme which has not yet been covered: that of representability. What should it mean for an infinite matroid to be representable over a field $k$? In this post we will explore a few ideas for how one could try to define this. It will be a fraught journey, with some false starts and paths that get lost in rocky ground, but eventually we will arrive at a satisfying definition.

The obvious thing to try is to just define representability of infinite matroids the same way we define it for finite matroids: take a set $E$ of vectors in some vector space $V$ over $k$, and say that a subset of $E$ is independent if it is linearly independent in $V$. If $E$ is infinite then we have an infinite matroid, and such matroids should certainly count as representable over $k$.

Unfortunately this definition doesn’t cover all the examples of matroids which ought to be representable. For example, in this post we saw a bunch of examples that look like infinite graphic matroids, and graphic matroids should be representable over every field. But these examples are not covered by the definition above. Nor are the examples from this post. Why not? A set of vectors is linearly independent as soon as all of its finite subsets are, so all the circuits of these matroids will necessarily be finite. In other words, all these matroids are finitary.

This might remind of you of the issues which got this whole series of posts started, here and here. It is easy to find axioms for the collection of finitary infinite matroids, but that doesn’t include all the examples of things that look like infinite matroids, and in particular the collection of finitary matroids is not closed under duality. Finding natural axioms for a class of infinite matroids closed under duality was a much trickier problem. Now we are running into exactly the same problem with representability. Not only have we failed to cover the important examples, this definition of representability is not even closed under duality.

Still, we have made some progress. We have identified which finitary matroids should count as representable over $k$, and so whatever our definition turns out to be it should give this collection of matroids as the finitary representable matroids. Since cofinitary matroids are just the duals of finitary matroids, we have also identified which cofinitary matroids should count as representable over $k$, namely the duals of these finitary representable matroids. Taking the union of these two classes would give a class of matroids closed under duality, but this is pretty crude and still doesn’t cover some of the interesting examples.

We need a way to allow infinite linear combinations of our vectors. One natural idea, which quickly turns out to be a dead end, is to use the infinite sums defined in Hilbert spaces (the notion of independence given this way does not give rise to a matroid). A more fertile approach was found by Bruhn and Georgakopoulos [4]. You can understand the basic idea by considering the following list of vectors in $\mathbb{R}^{\mathbb{N}}$:

$$\begin{array}{rrrrrrrrr}(&1,&0,&0,&0,&0,&0,&\ldots&)\\(&-1,&1,&0,&0,&0,&0,&\ldots&)\\(&0,&-1,&1,&0,&0,&0,&\ldots&)\\(&0,&0,&-1,&1,&0,&0,&\ldots&)\\(&0,&0,&0,&-1,&1,&0,&\ldots&)\\&&&\vdots&&&&&\end{array}$$

Although this list is infinite, if we pick any particular column and take the sum of the entries in that column it evaluates to 0. So there is a sense in which this infinite list of vectors sums to 0. More precisely, given a set $I$, we can consider the vector space $k^I$ of functions from $I$ to $k$. Then we say that a set $U$ of vectors in $k^I$ is thinly dependent if we can find coefficients $\lambda_u \in k$ for each $u \in U$, not all zero, such that for any $i \in I$ we have $$\sum_{u \in U} \lambda_u u(i) = 0\,.$$ There is of course the problem that some of these sums might not be defined, in that they might have infinitely many nonzero summands. We say that $U$ is thin if such sums are necessarily well-defined, that is, if for each $i \in I$ there are only finitely many $u \in U$ with $u(i) \neq 0$.

This suggests a new idea for how to define representable matroids. We take the ground set $E$ to be a thin set of vectors in $k^I$, and as dependent sets we take the thinly dependent subsets of $E$. The matroids we get this way need not be finitary, but now we have some new problems. A typical set of vectors in $k^I$ will not be thin, so it isn’t clear that all of the finitary representable matroids we saw above can be presented in this way. And in fact they cannot! Together with Afzali, I showed in [1] that all such matroids are cofinitary, and in fact they are exactly the duals of the finitary representable matroids.

So now we understand representability for finitary and for cofinitary matroids. To make any more progress we need to find a way to squeeze more juice out of the idea of thin dependency. The reason we took $E$ to be a thin family above was to ensure that thin dependency would always be defined for subsets of $E$, but we could drop that requirement if we take more care in our notion of dependency. More precisely, we take as our ground set $E$ any set of vectors in $k^I$, and we say that a subset $X$ of $E$ is dependent if it has a subset $Y$ which is thinly dependent (here $Y$ must be thin, even if $X$ need not be). Matroids arising in this way are called thin sums matroids.

This now includes all the cofinitary representable matroids, and it also includes all the finitary representable matroids (that’s less obvious, but it was shown in [1]). What’s more, it includes all the examples of things we wanted to be representable matroids. But there are some new problems. The systems of dependent sets defined in this way are not always matroids [1]. Even if they are matroids, their duals are not always thin sums representable [2]. Closure under duality is one of the main things we should hope for from a definition of representability. It seems we have hit a dead end.

However, there is a way forward. All of the examples that we cared about, and wanted to cover with our definition of representable matroids, had the property that they were tame, meaning that any intersection of a circuit with a cocircuit is finite. On the other hand, the bad examples where duality breaks down are not tame, but wild. This distinction was already discussed in an earlier post of the series. So we should restrict our attention to tame matroids.

And there we have it: we say that a matroid is representable over $k$ if it is tame and is a thin sums matroid over $k$. Suddenly, magically, everything works. This class is closed under duality [1]. All of the motivating examples are covered. Even better, all the usual theory of representable matroids can be extended to infinite representable matroids. For example, the various standard characterisations of binary and ternary matroids still work in this setting, including the characterisations via excluded minors [3].

Indeed, there is a very general principle which allows the lifting of excluded minor characterisations from finite to infinite matroids. For any finite field $k$, a tame infinite matroid $M$ is representable over $k$ precisely when all of its finite minors are [3]. This principle allows us to lift all kinds of other statements easily from finite to infinite matroids. For example, an infinite matroid which is representable over both $GF(3)$ and $GF(5)$ is necessarily representable over $GF(p)$ for all primes $p$ (since all its finite minors are). 

For those readers who have come across partial fields and tracts, that last statement might have got you wondering whether we can define representations of infinite matroids over those objects, in the spirit of this post. For example, what might it mean for an infinite matroid to be orientable? This is a thorny problem, which will have to wait for a future post.

Although we now have a good definition of representability, there is one open problem in this area that has been nagging at me for years. Binary matroids can be defined as tame matroids with no $U_{2,4}$-minor. But do we really need to impose the condition of tameness here? To put it another way, must every wild matroid have a $U_{2,4}$-minor? All the examples we know of do.

[1] S. Hadi Afzali Borujeni and Nathan Bowler, Thin sums matroids and duality, Advances in Mathematics, Volume 271, 2015, Pages 1-29.
[2] Nathan Bowler and Johannes Carmesin, Matroids with an infinite circuit–cocircuit intersection, Journal of Combinatorial Theory, Series B, Volume 107, 2014, Pages 78-91.
[3] Nathan Bowler and Johannes Carmesin, An excluded minors method for infinite matroids, Journal of Combinatorial Theory, Series B, Volume 128, 2018, Pages 104-113
[4] Henning Bruhn and Agelos Georgakopoulos, Bases and closures under infinite sums, Linear Algebra and its Applications, Volume 435, Issue 8, 2011, Pages 2007-2018.

The IBS Discrete Mathematics Group (DIMAG, https://dimag.ibs.re.kr/) in Daejeon, Korea invites applications for three research fellowship positions:

URL: https://dimag.ibs.re.kr/hiring/

DIMAG is a research group that was established on December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.

Currently, DIMAG consists of researchers from various countries such as Korea, the USA, Germany, Canada, and Australia, and the work is done in English. DIMAG is co-located with the IBS Extremal Combinatorics and Probability Group (ECOPRO).

Successful candidates for research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, combinatorial optimization, matroid theory, and algorithms.

These appointments are for about two years, and the starting salary is no less than KRW 59,000,000. The appointment is one-time renewable up to 5 years in total contingent upon the outstanding performance of the researcher. The expected appointment date is September 1, 2024, but it is negotiable within the same calendar year.

These are purely research positions and will have no teaching duties.

A complete application packet should include:

1. AMS standard cover sheet (preferred) or cover letter (PDF format)
2. Curriculum vitae including a publication list (PDF format)
3. Research statement (PDF format)
4. Application for the IBS & Consent to Collection and Use of Personal Information (PDF file)
5. At least 3 recommendation letters

For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to dimag@ibs.re.kr by December 3, 2023, Sunday. (Anywhere on Earth)

Recommendation letters forwarded by an applicant will not be considered.

DIMAG encourages applications from individuals of diverse backgrounds.

For Korean citizens who have not yet completed their military duty: 전문연구요원 종사를 희망하는 경우에는 지원 의사와 병역 관계를 cover letter 및 이메일 등에 표시하여 제출 필요. 다만 현역입영대상자의 전문연구요원 신규 편입은 불가하며, 보충역 대상자 및 타 기관에서 전직해서 오는 경우에 한하여 지원 가능(반드시 타 기관에서 전직 요건이 충족되는 등 전직 요건이 충족 되어야만 함)