About Nathan Bowler

I'm working at the university of Hamburg on infinite matroid theory.

Building matroids from infinite graphs

Today we’ll be looking at infinite matroids again. We started this series by examining the question of how infinite matroids could be defined. With a suitable definition in hand, we took a quick tour through the zoo of known examples. Then we took a closer look at one very flexible way to build infinite matroids: by sticking together infinite trees of matroids.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, preprint here.
[BC16] N. Bowler and J. Carmesin, The ubiquity of Psi-matroids, preprint here.
[D10] R. Diestel, Locally finite graphs with ends: a topological approach I–III, Discrete Math 311–312 (2010–11).
[G07] A. Georgakopoulos. Connected but not path-connected subspaces of infinite graphs, Combinatorica, 27(6) 683–698 (2007).

Infinite trees of matroids

Welcome back to this series of posts about infinite matroids. Up to this point we’ve seen what infinite matroids are, and we’ve started to understand the notion a little by looking at a variety of examples. Next we will look at how to stick together infinite matroids to build bigger ones. We’ll see that it is possible to stick infinitely many matroids together at once, and this will give us a flexible way to build new infinite matroids by sticking together infinitely many finite matroids.

Let’s start with a familiar way to stick matroids together: via 2-sums. Suppose that we have matroids $M_1$ and $M_2$ with ground sets $E_1$ and $E_2$, and suppose that these ground sets meet in only a single edge $e$. For the sake of simplicity, we’ll assume that $e$ isn’t a loop or a coloop in either matroid. Now we can build a new matroid $M_1 \oplus_2 M_2$ on the ground set $E_1 \triangle E_2$, by taking the circuits to be sets of the following 3 kinds:

  • circuits of $M_1$ not containing $e$
  • circuits of $M_2$ not containing $e$
  • sets of the form $C_1 \cup C_2 -e$, where $C_1$ and $C_2$ are circuits of $M_1$ and $M_2$ respectively, both containing $e$.

These three kinds of circuit are illustrated below:


This operation is associative, in the sense we might expect: suppose we have 3 matroids $M_1$, $M_2$ and $M_3$ on ground sets $E_1$, $E_2$ and $E_3$. Suppose that $E_1 \cap E_2$ and $E_2 \cap E_3$ each contain just a single edge, and that $E_1 \cap E_3$ is empty. Then the two matroids $M_1 \oplus_2 (M_2 \oplus_2 M_3)$ and $(M_1 \oplus_2 M_2) \oplus_2 M_3$ are equal. This is easy to see by considering the six kinds of circuits which can arise in the sum, as shown here:


Usually associativity means that it doesn’t matter how we bracket a list of things that we want to add together, but in the case of 2-sums the geometry is a little different. The kind of configuration we might want to stick together with 2-sums in general is not a list of matroids, but rather a tree of matroids. More precisely, suppose we have a finite tree $T$, and that for each node $t$ of $T$ we have a matroid $M_t$ with ground set $E_t$. Suppose further that for distinct nodes $t$ and $t’$ of $T$ the intersection $E_t \cap E_{t’}$ either consists of a single edge $e_{tt’}$, if $t$ and $t’$ are neighbours in $T$, or else is empty. Let’s call a structure like this a finite tree of matroids. Then there is an unambiguously defined 2-sum of our tree of matroids, whose ground set is the union of all the sets $E_t$ but without the `gluing edges’ $e_{tt’}$. A typical circuit in such a 2-sum of a tree is shown here:


More precisely, each circuit of the 2-sum is supported on some subtree $S$ of $T$. It is determined by a choice, for each node $t$ of $S$, of a circuit $C_t$ of $M_t$. This circuit $C_t$ should contain precisely those gluing edges $e_{tt’}$ of $M_t$ such that $t’$ is also in $S$. Given such a subtree $S$ and such a family of circuits $C_t$, we get a circuit of the 2-sum whose edges are the non-gluing edges of the circuits $C_t$.

All of this works just as well for sticking together infinite matroids as for finite ones. But the real power of this technique for building new infinite matroids comes when we consider 2-sums of infinitely many matroids at once.

So what happens if we try to stick together an infinite tree of matroids in the way outlined above? To understand the kinds of difficulty which can arise, let’s first of all consider the simplest possible infinite tree: an infinite ray. We certainly want to allow circuits of the following kind:



But what about ones which go all the way to the end of the ray:


Should we allow them?

It turns out that if we allow them, then we get an infinite matroid. But we also get a different infinite matroid by banning them: by only allowing those circuits whose underlying tree $S$ is finite. So we have two different options for how to build a matroid by sticking together an infinite ray of matroids. We say that the circuits are allowed to use the end of the ray in the first of these matroids, but not in the second.

We could just decide to fix one of these two as the `correct’ 2-sum of the ray of matroids, but it turns out that that would be a bad idea. To see why, we should consider the interaction of 2-sums with duality. If we take the dual of the 2-sum of 2 matroids, then it turns out to be the same as the 2-sum of their duals. It follows that the same is true for finite trees of matroids: the dual of the 2-sum of a tree of matroids is the 2-sum of the duals of those matroids. This is certainly a property which we would like to keep for infinite 2-sums.

Now suppose that we have a ray of matroids, and we take the variant of the 2-sum where the circuits are not allowed to use the end, then take the dual of that 2-sum. What we get is the 2-sum of the duals of the matroids, but this time in the version where the circuits are allowed to use the end. So these two different constructions of the 2-sum of a ray are dual to each other, and we shouldn’t privilege either of them.

Formally, we take the decision about whether the circuits should be allowed to use the end of the ray to be part of the data used to specify the sum, in addition to the choices of the matroids lying along the ray. More generally, suppose that we have an infinite tree of matroids. Then in order to specify a 2-sum for this tree of matroids, we must decide, for each end of the tree, whether the circuits are allowed to use that end. Here the ends of the tree can be identified with the rays from a fixed root.

More precisely, suppose that we have a (possibly infinite) tree $T$, and that for each node $t$ of $T$ we have a matroid $M_t$ with ground set $E_t$. Suppose further that for distinct nodes $t$ and $t’$ of $T$ the intersection $E_t \cap E_t’$ either consists of a single edge $e_{tt’}$, if $t$ and $t’$ are neighbours in $T$, or else is empty. Suppose further that we have a subset $\Psi$ of the set of ends of $T$, which we intend to be the set of ends which we will allow circuits to use. Then we might hope to define the 2-sum of this tree of matroids as follows:

Each circuit of the 2-sum will be supported on some subtree $S$ of $T$, such that all rays in $S$ go to ends in $\Psi$. The circuit is determined by a choice, for each node $t$ of $S$, of a circuit $C_t$ of $M_t$. This circuit $C_t$ should contain precisely those gluing edges $e_tt’$ of $M_t$ such that $t’$ is also in $S$. Given such a subtree $S$ and such a family of circuits $C_t$, we get a circuit of the 2-sum whose edges are the non-gluing edges of the circuits $C_t$.

So the circuits would look something like this:


Unfortunately, this construction does not always give a matroid. The reason why not is related to some tricky set-theoretical issues, so we will not discuss it here. But due to a very deep and beautiful set-theoretic result called Borel Determinacy, we know that this construction will give a matroid if the set $\Psi$ is topologically nice enough (if it is a Borel set) [BC15].

There are also certain infinite trees of matroids such that the above construction will give a matroid for any set $\Psi$ of ends. This has the immediate consequence that there are a lot of infinite matroids – as many as there could possibly be. A matroid is determined by a set of subsets of its ground set, so there could be no more than $2^{2^{\aleph_0}}$ matroids on a countable set. And in fact, there are that many non-isomorphic matroids on a countable set, because there are that many possibilities for the set $\Psi$.

This means that when an infinite matroid is constructed from a tree of matroids together with a set $\Psi$ of ends, most of the information is encoded in the set $\Psi$ – if the matroids in the tree are finite, then there are only $2^{\aleph_0}$ possibilities for the tree of matroids, but there are $2^{2^{\aleph_0}}$ possibilities for $\Psi$. This huge reservoir of extra information hidden at the ends means that countable matroids behave in many ways like uncountable graphs. For example, the constructions which show that infinite graphs in general are not well-quasi-ordered under the minor relation already work for countable matroids, even though they do not work for countable graphs [BC15].

The construction we are considering also plays a key role for the reconstruction of infinite matroids from their decompositions into 3-connected parts. It is known that any finite matroid is canonically expressible as a 2-sum of a finite tree of matroids, each of which is either 3-connected or else consists of a single circuit or cocircuit [CE80, S80]. This result extends directly to infinite matroids: any matroid can be canonically expressed as a 2-sum (in the above sense) of a tree of matroids, each of which is either 3-connected or else consists of a single circuit or cocircuit [ADP15, BC16]. As with the finite result, this implies that it often suffices to prove a result only for 3-connected matroids in order to be able to deduce it for all matroids.

The construction we have considered was based on the 2-sum, one of the simplest possible ways to stick matroids together. Next time, we shall see that similar ideas work to give infinitary versions of other more complicated ways of sticking matroids together, and the surprisingly close connections between these infinitary sums and the matroids naturally arising in infinite graphs.

[ADP15] E. Aigner-Horev, R. Diestel, L. Postle. The structure of 2-separations of infinite matroids, to appear in JCTB, available here.
[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, submitted to LMS, available here.
[BC16] N. Bowler and J. Carmesin, The ubiquity of Psi-matroids, preprint, available here.
[CE80] W. H. Cunningham and J. Edmonds, A combinatorial decomposition theory, Canad. J. Math. 32 (1980), no. 3, 734–765.
[S80] P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359.

A menagerie of infinite matroids

So far in this series we have focused on the search for a good way to axiomatise infinite matroids. Now that we have the axioms, our next aim is to get a better sense of what sort of ground they stake out by taking a whirlwind tour of the known examples of infinite matroids.

Let’s start off with some very familiar examples: The set of subsets of a given set which have size at most $n$,  the set of (edge sets of) forests in a given graph and the set of linearly independent subsets of a given family of vectors in a vector space each give the set of independent sets of a matroid. This is true even if we allow the set, graph or family of vectors in question to be infinite. Of course, all of these examples are finitary (that is, a set is independent as soon as all of its finite subsets are). We saw earlier that it would be a bad idea to only consider finitary matroids, because we would lose the power of duality. But we certainly want our notion of infinite matroid to include all of these examples. Since we now have a concept of infinite matroid which is closed under duality, we get all their duals for free, too.

What about matroids which are neither finitary nor cofinitary? At first it looks like a simple way to construct such examples would be by building infinite uniform matroids. But the usual definition of uniformity, namely that the bases should be all sets of a given size, becomes silly when we replace `size’ by `cardinality’, since infinite sets can have proper subsets of the same cardinality. It doesn’t help to define things in terms of independent sets. For example, we might hope to have a matroid whose independent sets are just the countable subsets of some uncountable set $E$. But since there are no maximal countable sets, this object wouldn’t even have any bases.

The right notion of uniformity for infinite matroids is as follows: if $B$ is a base and $x$ and $y$ are elements of the ground set $E$ with $x$ in $B$ but $y$ not in $B$ then $B – x + y$ is also a base. It isn’t hard to check that this is equivalent to uniformity when applied to finite matroids. Now we might try to build infinite uniform matroids by just recursively choosing the set of bases, paying attention to the fact that (because of the definition above) whenever we choose a set $B$ we also have to choose all sets $B’$ for which $B \setminus B’$ and $B’ \setminus B$ are finite and of equal size. This simpleminded strategy works, given some weak assumptions [BG15]. Because this recursive construction gives us so much freedom, infinite uniform matroids are much more varied than finite ones.

The flexibility of this construction lets us resolve a very basic question: must it be true that any two bases of an infinite matroid have the same cardinality? Higgs showed that this is true if we assume the continuum hypothesis [H69a]. But using the freedom mentioned above we can also show that it is consistent that the following naive plan for building a matroid with bases of different sizes actually works: run the above recursive construction to build a uniform matroid on an uncountable set, and begin by nominating some countable subset and some uncountable subset as bases [BG15]. So the answer to the question above is actually independent of the usual axioms of set theory.

The other examples we’ll look at today will all be associated to graphs. The finitary matroid mentioned above, whose circuits are (edge sets of) cycles in a given graph $G$, is called the finite-cycle matroid of $G$. There is another finitary matroid whose circuits are the finite bonds of $G$. But these two are no longer dual to each other. The circuits of the dual of the finite-bond matroid correspond to topological circles in a topological space, called the end-compactification of $G$. This space is obtained from $G$ by adding some points at infinity, called ends. These `topological cycles’ were actually first invented for a very different reason and helped to motivate the current axiomatisations of infinite matroids. This was the starting point of our story.

So although there is one canonical matroid associated to a finite graph, for an infinite graph we already have two. In fact there are many more. For example, Higgs showed that there very often is a matroid whose circuits are the (edge sets of) finite cycles or double rays in the graph $G$. This doesn’t always work. For example, in the Bean Graph, shown below, the set of bold edges and the set of dashed edges are both bases but there is no way to replace the edge $e$ with a bold edge in the dashed basis and still have a base. So the base axioms don’t hold.


This is essentially all that can go wrong: Higgs showed [H69b] that if $G$ includes no subdivision of the Bean Graph then there is a matroid, called the algebraic-cycle matroid of $G$, whose circuits are given as above by the finite cycles and double rays.

Another fertile way to build more matroids from graphs is to ignore some of the ends. More precisely, we consider topological circles in a space obtained from the end-compactification of $G$ by deleting some of the ends. For example, the double ladder has two ends and we might wish to keep only one of them, giving rise to the following space:


Once more it is true that the (edge sets of) topological circles give the circuits of a matroid, as long as the set of ends we remove is Borel [BC15].

Is there any unifying theme to this profusion of examples, except that they can all be built somehow from graphs? Yes! Each of these matroids can represented by a topological space. The finite-cycle matroid of $G$ is represented by the geometric realisation of $G$ and the topological-cycle matroid by the end-compactification. The rich collection of matroids we just discussed are represented by subspaces of the end-compactification. The algebraic-cycle matroid is represented by the space obtained from the end-compactification by identifying all the ends.

More generally, there is a precisely specified class of graph-like topological spaces and a  notion of representation of a matroid by such a space, such that a matroid is representable in this way if and only if, firstly, every intersection of a circuit with a cocircuit is finite (this corresponds to the fact that topological circles are compact), and secondly, it satisfies the usual excluded-minor characterisation of graphic matroids.

Thus the wide range of ways of building infinite matroids from graphs corresponds to the variety of ways of building such graph-like spaces out of graphs. We have seen that this construction doesn’t always give a matroid, as with the Bean Graph above, but it does so often enough to give a rich variety of matroids. For example, we always get a matroid when the space is compact. Hence the (edge sets of) topological circles in the following picture give the circuits of a matroid, the Sierpinski Matroid:


Before we conclude, lets just glance at a couple of the other kinds of infinite matroid which have been discovered. There are frame matroids: Matthews and Oxley showed that in any graph $G$ the edge sets of subdivisions of the following graphs gives the set of circuits of a matroid [MO77], and a more general construction works in in infinite biased graphs.



There are infinite gammoids, defined either in terms of bipartite graphs or of directed graphs. The question of when these constructions give rise to matroids is a delicate one and has been investigated by Afzali, Law and Müller [ALM15].

Finally, we can define the truncation of a non-free matroid $M$ to have as independent sets the proper subsets of independent sets of $M$, and all truncations and co-truncations of infinite matroids are again infinite matroids. This gives lots of new examples, such as the matroids whose circuits are edge sets of topological copies of the following spaces in a graph-like space:


This is not so much a class of examples as a way to build new infinite matroids from old. We’ll consider some other fertile ways to combine infinite matroids next time.

[ALM15] H. Afzali, Hiu-Fai Law and M. Müller, Infinite gammoids. Electronic J. Comb. 22 (2015), #P1.53
[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, submitted to LMS, available here.
[BG15] N. Bowler and S. Geschke,  Self-Dual Uniform Matroids on Infinite Sets, to appear in the Bulletin of the American Mathematical Society, available here.
[H69a] D. Higgs, Equicardinality of bases in B-matroids, Canadian Math. Bul. 12 (1969), 861–862.
[H69b] D. Higgs. Infinite graphs and matroids. Recent Progress in Combinatorics, Proceedings Third Waterloo Conference on Combinatorics, Academic Press (1969),  245-53.
[MO77] L. Matthews, J. Oxley, Infinite graphs and bicircular matroids. Discrete Mathematics, Volume 19, Issue 1 (1977), 61-65.

Announcement: Summer School in Infinite Matroid Theory, 19-25 July 2015

There will be a Summer School in Infinite Matroid Theory from the 19th to 25th of July at the youth hostel in Bosau, near Hamburg, Germany. More details are available at http://www.math.uni-hamburg.de/home/bowler/im15

It is aimed at doctoral students and other young researchers, especially graph theorists, who are already familiar with the basic theory of finite matroids. The aim is to give the participants a sufficient grounding in the theory of infinite matroids that they can start to work independently in the field. The organisers are Nathan Bowler and Johannes Carmesin.

There are no accommodation costs, and we have a little money to help pay for travel in exceptional cases. If you have any questions, feel free to email us at im15@math.uni-hamburg.de