Will's place for things

Home

Hello I’m Will and this is my site! I’m a mathematics PhD student with too many hobbies. Here you can find my maths blog, my academic research and research interests. I might also post some creative writing along with other side projects that I get up to.

About

Research

Writing

Hijinks

Generalising obstructions – Part 2 – Fracturings

This is the second blog post in a collaborative project between me and Ben Bumpus, whose blog can be found here. The first post is here. We devoted a week to messing around with the categorical machinery and now have a little collection of lemmas and a clearer direction. Lots of stuff didn’t work like we thought it might and there are a couple of things that seem like nice results but might not fit into the larger project anymore. This post is devoted to recording some of those things. It will be a little disjointed but I hope you’re able to get something out of these ideas. Ben has written a parallel post about one of our findings here. Watch out for more intallments (both here and on Ben’s blog) – we’ll be documenting our new ideas sometime soon.

In the previous post, we saw how we can express nestedness of separations in the language of category theory. In the following section, we generalise this.

First though, let’s recap the setting. We can think of a separation of a graph as a really simple tree decomposition, one with two bags and one adhesion. We can think of a tree decomposition of a graph $G$ as a diagram in the category of graphs; we have objects corresponding to bags, objects corresponding to adhesions and monic spans from these adhesions to their bags:

The diagram’s colimit (when we glue it all together) must be $G$ .

We write $\text{fract}(c)$ (fracturings of $c$ ) for the category of diagrams whose colimits are some object $c$ . Morphisms in this category are natural transformations that commute with the colimit cocones:

Interlacing

Recall that, in the category $\text{fract}(c)$ of fracturings of an object $c$ , two separations $S_1$ and $S_2$ are nested if there is a span $S_1\leftarrow P\rightarrow S_2$ where $P$ has shape $P_2$ . The intuition of this can be thought of as follows:

The span tells us that the $P_1$ -shape decompositions are actually just coarser versions of a $P_2$ -shape decomposition and they are somehow ‘lined-up’.

This definition seem to be a bit restrictive though. Shouldn’t we be able to say that $P$ can have any path shape? This doesn’t quite work. Indeed, given crossed separations $S_1$ and $S_2$ , it might be that a path of length three ( $P_3$ ) factors through $S_1\times S_2$ as follows:

Since it factors through the product, it spans $S_1$ and $S_2$ .

So what’s going wrong in this example? Well, the map from $P$ into $S_2$ somehow ‘folds in on itself’. In fact, this is precisely the problem. Let’s make the following definition.

Definition We say that a map $a\rightarrow b$ between fracturings is a contraction map if the map on the shapes of the decompositions is a contraction map. That is, if it just consists of contracting edges and identifying the end bags.

Now we can make the following generalisation:

Definition We say that two separations $S_1$ and $S_2$ are nested if there is a span of contraction maps $S_1\leftarrow P\rightarrow S_2$ where $P$ has path shape.

But why stop there? Why settle for boring-shaped decompositions?

Definition We say that a class $\mathcal{F}$ of graphs is closed under subdivision. If for any $G\in\mathcal{F}$ and $H$ a subdivision of $G$ , we have $H\in\mathcal{F}$ .

Definition Let $\mathcal{F}$ be a graph class closed under subdivision. We say that two fracturings $F_1$ and $F_2$ with shapes in $\mathcal{F}$ are $\mathcal{F}$ –interlaced if there is a span of contraction maps $F_1\leftarrow F\rightarrow F_2$ where $F\in\mathcal{F}$ .

In particular, nestedness of separators is interlacedness of fracturings with respect to the class of paths.

This machinery possibly has some nice applications to the mechanics of refining decompositions of a particular class of shapes. But we’re going to leave it here for now.

We found out more stuff about corners

Given a pair $S_1$ and $S_2$ of crossed (non-nested) separations, we can obtain four new separations, the “corner separations” from the intersections and unions of pairs of sides of the separations.

These corners are used in the theory of separations to refine systems of separations and have all sorts of nice properties.

Oberve that we can get corner separations via the following means:

Observation Let $Z$ be a separation such that $S_1\times S_2\rightarrow Z$ . Then either $Z=S_1,S_2$ or $Z$ is a corner separation.

That is, there are six unique ways to contract the product to a fracturing of shape $P_1$ .

One of the nice properties of corners is that any separation $S$ , that is nested with both of $S_1$ and $S_2$ , is nested with all four corner separations. This follows immediately from our above obersvation.

Let’s play around with limits some more. Suppose we are given crossing separations $S_1,S_2$ and a separation $S$ nested with both. Let $P$ and $Q$ be nestedness-witnessing paths of length two for the pairs $S_1,S$ and $S,S_2$ respectively. Let’s take the pullback over $P\rightarrow S\leftarrow Q$ .

Observe that $P\times_S Q$ factors uniquely into the product $S_1\times S_2$ since it maps into both $S_1$ and $S_2$ . To figure out the shape of $P\times_S Q$ , we split into two cases based on exactly how these witnessing spans are:

We can ommit the second case; indeed, this is telling us that $S_1$ and $S_2$ were nested in the first place. The first case is the interesting one. We obtain this “tadpole”-shaped diagram that contains both the information about the product and the separation $S$ . In fact, the shape of the diagram gives us a canonical choice for which corner is “closest” to the separation $S$ . This normally requires a lot of poset machinery. That’s pretty neat!

That’s all for now. Keep an eye open for more installments soon!

June 13, 2023

Playground
Generalising obstructions – Part 1 – Nestedness

This is the first blog post in a collaborative project between me and Ben Bumpus, whose blog can be found here. We’re looking to use category theory to generalise machinery from the theory of obstructions to tree decomposition. I plan to make a separate post introducing category theory (with a graph theory twist of course) sometime soon. If that doesn’t exist yet, I can recommend S. Awodey’s book (available for free online). For this post, you’ll need a basic understanding of categories, natural transformations, products and pullbacks.

Ben and his co-authors have already made significant inrows into the subject of generalising tree decompositions. At some point there’ll be an accessible introduction on Ben’s blog but, for now you can check out their first paper here.

Intro

Graph theory can be messy; there can be a lot of data and sometimes there’s no symmetry to work with. Luckily, there are lots of tools that can help us make sense of complicated graphs. Tree decomposition, for example, splits up a graph $G$ into lots of subgraphs that are glued back together to form $G$ in a “tree-like way”. Amongst other things, tree decompositions are closely tied to separators and separations of graphs, which we explore in the next section.

Separations and corners

In a graph $G$ , a separation is a cover of the vertex set $A\cup B=V(G)$ such that each edge of the graph lies completely in one of the sets $A$ or $B$ . We call a separation ‘trivial’ if one of its sides is contained in the other. We’ve got to be carfeul with this definition; sometimes separations are defined on the edge set (as in a previous post). For our purposes however, it will be more convenient to define separations on vertex sets. We say that a separation $A\cup B$ is of order $k$ if $|A\cap B|=k$ and in this case we call it a $k$ -separation.

Separations allow us to chop up our graph into simpler pieces; they’re everywhere in structural graph theory, but is it useful to consider all separations of a graph? Perhaps in a few cases, but in general we want to be more specific, so that we have information about how the separations interact. Consider a long cycle for instance; even if we just consider separations of order two, there is one of these for every pair of vertices. It’s worth taking some time to think about why this doesn’t lead to a nice decomposition; would it even make sense to split our graph up along all of these? If not, how do we make a canonical choice of separations out of all the possibilities?

To this end, we make the following definition: We say that a separation $A\cup B$ is nested with a separation $C\cup D$ if we have $A\subseteq C$ and $B\supseteq D$ or the same arrangement after swapping the order of either separation. If separations aren’t nested, then we call them crossed.

Crossed separations aren’t as nice as nested ones, but this is ok; a pair of crossed separations gives rise to four new ‘corner’ separations which may be nicer than the originals. Let $G$ be a graph and consider a pair of crossed separations $A\cup B$ and $C\cup D$ . The four corner separations are

$(A\cup C,B\cap D)$ , $(A\cup D,B\cap C)$ , $(A\cap D,B\cup C)$ and $(A\cap C,B\cup D)$ .

If the separations a set of separations $S$ are pairwise nested with eachother, we call $S$ totally nested.

Structured decompositions

You can find a full introduction to structured decompositions here. For now though, we can understand them as follows: Given a category $\mathcal{C}$ , a ( $\mathcal{C}$ -valued) structured decomposition $d$ is a diagram in $\mathcal{C}$ whose shape is governed by a some graph $G$ . That is, for each vertex $u$ of $G$ we have an object $du\in\mathcal{C}$ and for every edge $e$ in $G$ , that spans vertices $u$ and $v$ , we have an object $de\in\mathcal{C}$ along with monic (injective) arrows $du\leftarrow de\rightarrow dv$ (a ‘monic span’).

Morphisms between structured decompositions are natural transformations between the diagrams. In this way, we get a category $\mathcal{D}\mathcal{C}$ of $\mathcal{C}$ -valued structured decompositions.

Observe that structured decompositions with tree shape, valued in the category of reflexive graphs and homomorphisms, are exactly tree decompositions of graphs!
In fact, if we take the colimit of a graph-valued structured decomposition, it glues everything together into one object, which turns out to be the underlying graph!

We can easily represent separations in this language too: A separation of a graph $G$ is a structured decomposition $d$ of shape $P_1$ (two vertices with an edge spanning them), whose colimit is (isomorphic to) $G$ .

Now, before we get to the punchline, we need one more defintion.

The right universe

What if we want to investigate exactly the structured decompositions that have got something to do with a particular colimit $G$ ? We’ll need a category of such things if we want to do category theory on them. This brings us to the definition below. We’ll put this definition in more context in a future post.

Given a category $\mathcal{C}$ and an object $c\in\mathcal{C}$ , we define the category $\text{fract}(c)$ as follows: The objects of $\text{fract}(c)$ are colimit cocones $x\rightarrow c$ from some diagram $x$ to its colimit $c$ . We call these the fracturings of our object $c$ . Morphisms between $a:x\rightarrow c$ and $b:y\rightarrow c$ are given by natural transformations $f:x\rightarrow y$ such that $b\circ f=a$ .

Structured decompositions live in this category, but so do diagrams of other shapes. Sometimes we’ll restrict ourselves further so that we are only dealing with diagrams of particular shapes.

Back to nestedness!

Right away, we can make a fun observation: Given a graph $g$ in the category $\underline{\text{Gr}}$ of reflexive graphs and graph homomorphisms, let’s work in the category $\text{fract}(g)$ . Given separations (in our new context), $s_1$ and $s_2$ , there is a span $s_1\leftarrow p\rightarrow s_2$ where $p$ is a decomposition of shape $P_2$ . Since this is concise, lets turn it into a definition for structured decompositions in general.

Definition: In the category $\text{fract}(g)$ , we say two structured decompositions $s_1$ and $s_2$ of shape $P_1$ are nested if there is a structured decomposition $p$ of shape $P_2$ that spans $s_1$ and $s_2$ .

Why don’t we try messing around with limits in this category to see what happens? For now, we’ll see what happens to structured decompositions of shape $P_1$ .
Observe that products in $\text{fract}(g)$ are just pullbacks in the original category with respect to the base object $c$ and the morphisms into it.

Let $d_1,d_2$ be two objects in $\text{fract}(g)$ , that have shape $P_1$ :

$d_1x\leftarrow d_1e\rightarrow d_1y$ and $d_1x\leftarrow d_1e\rightarrow d_1y$

Let’s try and calculate the product of these. We’ll need the following category theory fact:

Fact: Limits of diagrams have the shape of the limit of their underlying graphs (in the category of reflexive graphs and homomorphisms).

Using this, all we need to do is know how to take the pullback of a graph, right? Not quite! It’s actually much simpler. Since the diagram $g^\ast$ containing just the graph $G$ has one vertex, namely $G$ , it is the shape of the terminal graph, and so the pullback is simply a product.

This product will have nine objects, four corresponding to the combinations of the different images of $x$ and $y$ , which we will denote by $dxx,dxy,dyx$ and $dyy$ , and five corresponding to the other object combinations. We’ll get the following diagram and we’ll use the fact that it commutes to determine what the objects actually are:

For each $w,z\in{x,y}$ we’ll get that $dwz$ is the pullback of $d_1w$ and $d_2z$ with respect to their inclusion into $G$ . Thus $dwz$ will be the intersection of these graphs. The other objects will represent intersections between the objects of $d$ that the maps that leave them span.

If you pause for a moment to look at the diagram above, you might begin to see something familiar. It seems like we’ve run into corners! Indeed, the objects $dxx, dxy, dyx, dyy$ are exactly the corners of the crossing separations (if they cross).

What happens if they don’t cross? Well, if the separations we started out with were nested, we’d get one of the corners is empty.

This is exactly what we’d expect. Why? Because if separations are nested, then there is a span with top of shape $P_2$ . By the universal property of the product, this needs to factor through the product. The only way that it can do this is if one of the corners is empty.

This is neat, and maybe it lends itself to further generalisation. Stay tuned while we iron out the details…

May 2, 2023

Playground
What on Earth is a matroid – Part 2 – Not-so squiggly lines
This is the second post in a thread introducing matroids. In the last post, we looked at how matroids arise as a natural object in topological graph theory. Now we’re going to attack matroids from the angle of linear algebra. All the while, we’ll push the concepts back into the world of graphs to see what kind of insight this new angle can give us.

Cryptomorphism

That’s a fun word but what does it mean? Essentially it means two systems of axioms are equivalent in the following sense: The objects that satisfy one set of axioms are in one-to-one correspondence with the objects satisfying the other set of axioms, in some kind of ‘natural’ way.

Before we jump back into matroids, one example you might be familiar with is that of topological spaces. Normally, we define a topological space in terms of open sets:

Let $X$ be a set and $\tau$ be a collection of subsets of $X$ that we call ‘open sets’. Then we call $(X,\tau)$ a topoligical space if it satisfies the following axioms:
- Both $X$ and $\varnothing$ are open.
- The arbitrary union $\bigcup_{i\in I}U_i$ of open sets $\{U_i\}_{i\in I}$ is open.
- The intersection $\bigcap_{i\in [n]}U_i$ of finitely many open sets $\{U_i\}_{i\in [n]}$ is open.
But we could equally-well define a topological space as follows: A topological space is a pair $(X,\sigma)$ where $X$ is a set and $\sigma$ is a collection of subsets of $X$ that we call ‘closed sets’ satisfying the following axioms:
- Both $X$ and $\varnothing$ are closed.
- The arbitrary intersection $\bigcap_{i\in I}U_i$ of closed sets $\{U_i\}_{i\in I}$ is closed.
- The union $\bigcap_{i\in [n]}U_i$ of finitely many closed sets $\{U_i\}_{i\in [n]}$ is closed.
These two defintions don’t formally define the same object, but they define equivelent (spiritually the same?) objects in some sense. There is a one-to-one correspondence between spaces defined both ways; we can move easily between them. In particular, a set is closed if and only if its complement is open. This is a cryptomorphism.

Matroids exhibit a multitude of cryptomorphic defintions. In fact, one of the reasons matroids were first studied was as a means of studying equivalence of axiomatic systems.

In the previous post, we saw the following definition for matroids in terms of their ‘circuits’:

A matroid $M=(E,\mathcal{C})$ is a set $E$ called the ground set, along with a set $\mathcal{C}$ of subsets of $E$ called circuits satisfying the following axioms:
- (C0) No $O\in\mathcal{C}$ is empty;
- (C1) $\mathcal{C}$ is an antichain w.r.t. inclusion. That is, no circuit is a subset of another;
- (C2) For distinct $O_1,O_2\in\mathcal{C}$ and $e\in O_1 \cap O_2$ , there is a circuit $O_3\in\mathcal{C}$ s.t. $e\notin O_3$ but $O_3\subseteq O_1\cup O_2$ .
The last condition is called circuit elimination. Subsets of $E$ which contain circuits are called dependent and those which do not contain circuits are called independent.

But we could have just as well stated the definition in terms of ‘bases’. This next definition will help us understand why matroids are a kind of generalisation of linear algebra.

Bases

A matroid $M=(E,\mathcal{B})$ is a set $E$ called the ground set, along with a set $\mathcal{B}$ of subsets of $E$ called bases satisfying the following axioms:
- (B1) There is at least one base. That is, $\mathcal{B}\neq \varnothing$ ;
- (B2) For distinct $B_1,B_2\in\mathcal{B}$ and $e\in B_2\setminus B_1$ , there is an element $f\in B_1\setminus B_2$ s.t. $B_2-e+f$ is a base.
The last condition is called basis exchange and is inspired by the properties of bases from linear algebra. We can get between the cryptomorphic defintions in the following way:

Given a matroid axiomatised in terms of circuits (minimally dependent sets), we obtain bases as the maximally independent (circuit-free) sets. Given a matroid axiomatised in terms of bases, we obtain circuits as the minimally dependent sets.

Like in a vector space, we can prove that all bases in a (finite) matroid have the same size.

Recall that, from a matroid $M$ , we obtain the dual matroid $M^*$ by taking its bases to be the complements of all of the bases of $M$ .

It sounds like “matrix”

As you might expect, the independent and dependent collections of vectors in a vector space satisfy the axioms of a matroid. In fact, we can be a little bit broader with this. If we take a matrix $A$ , with entries in some field $\mathbb{F}$ , then we can consider the columns as ground set elements, with the independence/dependence relations of the column space (treating the columns as vectors). Note that this is a little more general than the vector space defintion, since we might have columns that have the same entries but, by virtue of being differet columns, give multiple ‘parallel’ ground set elements.

Now we have a way to express elements of non-graphic matroids. Remember that a graphic matroid is a matroid on the edge set of a graph, whose circuits are the cycles of the graph. In particular, recall the forbidden minors from Tutte’s characterisation of graphic matroids:

$M^*(K_5)\quad M^*(K_{3,3})\quad U^2_4\quad F_7\quad F_7^*$

None of these matroids are graphic, but the matroid $F_7$ can be expressed as a matrix over $\mathbb{F}_2=\{0,1\}$ as follows:

$\begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{bmatrix}$

Graphic matroids are representable as matrices over any field. Given a graph $G=(V,E)$ , assign an arbitrary orientation to all of the edges (decide for each edge a ‘source’ and ‘target’ vertex). Now define a matrix as follows: Each row corresponds to a vertex $u\in V$ . Add a column for each edge $e\in E$ , with entries all $0$ except for a $1$ at the target of $e$ and a $-1$ at the source of $e$ . Remember that in the field $\mathbb{F}=\mathbb{F}_2=\{0,1\}$ , we get $-1=1$ . The matroid that this matrix defines is (isomorphic to) the cycle matroid $M(G)$ of the graph.

How about $U^2_4$ , the ‘uniform matroid of rank 2 on 4 elements’? We’ve been keeping awefully quiet about the representations of this one. In general, the uniform matroid $U^r_n$ is the matroid on the ground set $\{1,\ldots,n\}$ with bases exactly the subsets of size $r$ .

It turns out that $U^2_4$ is has no matrix that represents it with entries in $\mathbb{F}_2$ (or any field of characteristic 2). We can, however represent $U^2_4$ over $\mathbb{F}_3=\{-1,0,+1\}$ .

This is a strange phenomenon and it brings us to our next section.

Representability

We say that a matroid $M$ is representable over a field $\mathbb{F}$ if it is generated as the ‘column matroid’ of some matrix with entries in $\mathbb{F}$ .

It turns out that the matroids representable over $\mathbb{F}_2$ , the so-called binary matroids, are exactly those which do not contain $U^2_4$ as a minor.

Similarly, the ternary matroids, those representable over $\mathbb{F}_3$ , are characterised by the following set of four forbidden minors:

$U^2_5\quad U^3_5=(U^2_5)^*\quad F_7\quad F_7^*$

The matroids representable over every field are called regular matroids and it turns out that regular matroids are exactly those which are both binary and ternary. Therefore, the regular matroids are characterised by the forbidden minors:

$U^2_4\quad F_7\quad F_7^*$

These kind of representability results are tied together into Rota’s Conjecture below. It is sometimes seen as the matroid-theoretic counterpart to graph theory’s Robertson-Seymour Theorem.

Rota’s Conjecture – For any finite field $\mathbb{F}$ , the set of forbidden minors that characterise the matroids representable over $\mathbb{F}$ is finite.

In 2013, Geoff Whittle announced that he, along with Jim Geelen and Bert Gerards, had solved Rota’s conjecture. The result has yet to be published.

While I’d like to dive further into the representability of matroids, I’ll leave this here and maybe come back to it in a future post.

Rank

What other ideas from linear algebra can we import into matroid theory? Well, since for a finite matroid, all of its bases have the same size, we automatically get a notion of ‘dimension’. We call this size value the rank of a matroid $M$ and denote it by $r(M)$ .

We can extend this notion of rank to a function on all subsets of the ground set. Indeed, for a matroid $M$ on a ground set $E$ , the rank of a subset $F\subseteq E$ is the size of the largest independent set contained within $F$ and is denoted $r(F)$ .

For matroids that come from vector spaces, the rank of a subset is the dimension of the subspace generated by that set.

We even get a cryptomorphic definition of matroids via the rank function:

A matroid $M=(E,r:\mathcal{P}(E)\rightarrow\mathbb{Z}_{\geq0})$ is a set $E$ called the ground set, along with a function $r:\mathcal{P}(E)\rightarrow\mathbb{Z}_{\geq0}$ that assigns to subsets of $E$ an integer rank, satisfying the following axioms:
- (R1) For all subsets $F\subseteq E$ , we have $r(F)\leq |F|$ ;
- (R2) Rank is submodular. That is, for any subsets $A,B\subseteq E$ , we have $r(A\cup B)\leq r(A)+r(B)-r(A\cap B)$ ;
- (R3) Rank is monotonic. That is, for any subset $F\subseteq E$ and any $e\in E$ , we have $r(F)\leq r(F\cup\{e\})\leq r(F)+1$ .
The rank of a matroid $M=(E,r)$ is then $r(E)$ . The bases of $M$ are the subsets of maximum rank.

Rank allows us to define another familiar structure! We get the analogues of linear subspaces, hyperplanes. In matroid-land, these are called flats and are the subsets of the ground set $E$ that are maximal with their current rank. That is, we can’t add any more elements without increasing their rank. These flats form an ordered set (a lattice in fact!), which leads to another way to cryptomorphically define a matroid. Sadly, we don’t have time to go into that now.

Let’s bring it back to graphs

What role does rank play in the cycle matroids of graphs? It seems like a strange property to try and query graphs about, but it turns out to make some graph definitions more elegant.

Recall that the bases of a cycle matroid of a connected graph $G=(V,E)$ correspond to the edge sets of the spanning trees (the maximally acyclic subgraphs in $G$ ). In this way, we get $M(G)$ has rank $|V|-1$ .

From this, the flats of a graph $G$ are the ‘induced subgraphs’ of $G$ . That is, the subgraphs defined on a specific set of vertices with as many edges from the parent graph included as possible.

This is cool but not particularly enlightening. What is more interesting, is when we look at graph connectivity in terms of matroids…

Let $G=(V,E)$ be a graph. For some number k, we say that a collection of k vertices $S\subseteq V$ is a k-separator of $G$ , if removing the vertices $S$ leaves $G$ disconnected. A graph is called k-connected if it has no k-separator.

In the spirit of matroids, let’s try and rewrite this in terms of edges. How about:

Let $G=(V,E)$ be a graph. A nontrivial bipartition of the edge set $E=A\cup B$ is called a separation of $G$ . We say that it is a k-separation if the total vertices incident with $A$ and the total vertices incident with $B$ have k vertices in common. A graph is k-connected if it has no k-separation.

Now, these definitions aren’t one-to-one (a separation gives a unique (minimal) separator but not always vice versa) but they’re close enough for our purposes. Indeed, the definitions of k-connected coincide (at least when there are sufficient vertices involved).

We can lift the separation defintion straight to matroids using rank. Indeed, for a set of edges in a cycle matroid, rank counts one less than the number of vertices incident with those edges.

Let $M$ be a matroid on a ground set $E$ . A separation of $M$ is a bipartition of the ground set $E=A\cup B$ . We say that it is a k-separation if $r(A)+r(B)+1=r(M)+k$ . We say that a matroid is k-connected if it has no k-separation.

As you would expect, k-separations of cycle matroids correspond to k-separations of the graphs that generated them (except when the original graph is not connected). As such, lots of graph-connectivity results generalise to matroids. We can even define tree-decompositions (and thus treewidth) of matroids using this machinery!

That’s the end of this post for now, but I hope to explore this all again in detail soon.
April 13, 2023

Introductions
What on Earth is a matroid – Part 1 – Squiggly lines
Matroids are a weird new (ish) object that seems to be constantly gaining steam in the world of combinatorics. But what on Earth is a matroid? And why should you care about them? (And why do I keep going on about them at lunch?)

In this post, we’ll first take a détour through some topological graph theory, finding that matroids jump out as the natural object to describe embeddability of graphs. Then we’ll dive into their axiomatisation and see where else they crop up (in graph theory and beyond). This will be the first in a series of undetermined length…

Embedding graphs

In combinatorics, a graph $G=(V,E)$ is a set $V$ of vertices along with a set $E$ of edges. To each edge $e\in E$ is associated two endvertices from $V$ . A graph is data which encodes the abstract connections between a set of objects. In this post, we’ll assume all graphs are connected. That is, between every two vertices, there is a walk in the graph (a sequence of vertices, consequtively joined by edges).

In this post, we allow graphs to have multiple edges between the same pair of vertices and even loops, edges with both endvertices the same. For now, we wont consider edges to have an intrinsic direction.

We often draw out a graph on paper as a set of dots for its vertices and lines between them, representing the presence of edges. Sometimes, for really dense graphs, this can get a bit difficult. Sometimes it’s impossible to do without the lines crossing. When exactly is this possible though? Is there a nice way to tell whether this is possible or not? Formally, does the graph have a ‘planar embedding’?

For formality, we have to interpret our graph as a topological space. This is easy; we just take the vertices to be single points and the edges are (internally disjoint) line segments. For simplicity, we’l use the same letter $G$ to denote this ‘geometric realisation’ of our graph $G$ .

A planar embedding of a graph $G=(V,E)$ is an continous map

$\iota:G\rightarrow\mathbb{R}^2$

that is injective. That is, no point in $\mathbb{R}^2$ is mapped to more than once.

If a graph $G$ has a planar embedding we say that $G$ is a planar graph.

In this post, we consider two embeddings to be ‘the same’ if we can smoothly deform one into the other, without having the edges cross eachother on the way. I like to think that the graphs are made pebbles (vertices) tied together with string (edges) and we’re allowed to smoosh the embedding around with our palms flat against the floor.

As it turns out, there is a particularly beautiful way to characterise whether a graph is planar or not. For us to fully understand it, we need one more set of definitions.

Graph minors and Kuratowski

Given a graph $G$ , we can obtain a subgraph $H$ from $G$ by deleting some edges (in this post, to keep our graphs connected, we also delete any isolated vertices). Similarly, we obtain a minor of $G$ by deleting some edges and contracting some other edges. We contract an edge by deleting it from our edge set and identifying (gluing together) its two endvertices into a new vertex. Note that it doesn’t really matter in what order we perform these operations; as long as the edges we choose to contract/delete stay the same, we’ll always end up with the same thing (the operations ‘commute’).

Now we can state the characterisation. This was first proved (albeit in a slightly different form) by Kuratowski in 1930.

Kuratowski’s Theorem – Let $G$ be a graph. Then $G$ is planar if and only if $G$ has no $K_5$ or $K_{3,3}$ as a minor.

What this says is that there are two kinds of forbidden shapes that a graph can’t have if it wants to be planar. These are the fundamental ways that the graph could be ‘too tangly to be untangled’. What’s especially neat about this, is that it works two ways: if we can gaurantee these shapes aren’t present in the graph, then there must exist a way to embed it!

This kind of characterisation is known as a ‘forbidden minors’ characterisation. If this is exciting to you, go and google Robertson and Seymour’s ‘Graph Minors Theorem’ – you won’t be dissapointed.

Whilst possibly the most well-known characterisation of planarity, Kuratowski’s Theorem is by far not the only one. Soon, we’ll take a look at a different approach to characterising planarity. For now though, we’ll introduce a few more concepts.

Dual graphs

A face in an embedding of a graph is what you intuitively think it should be, a maximally connected region of the plane enclosed by bits of the graph. These include the ‘outer face’, the infinite bit around the graph.

Given a graph $G$ and a particular embedding $\iota:G\rightarrow\mathbb{R}^2$ , we construct the dual graph $G^*=(V^*,E^*)$ of $G$ (with respect to $\iota$ ) as follows:

Take the vertex set $V^*$ to be the set of faces of the embedding of $G$ and add and an edge between every pair of these $f_1$ and $f_2$ for every edge shared between their boundaries. Since the edges of $G$ and $G^*$ are in bijection (one-to-one correspondence), we often just use the same set $E$ for both edge sets.

Specifying our embedding is a necessary part of the above definition. Indeed, we might get different dual graphs from different embeddings.

Notice that, from an embedding of $G$ , we get an embedding of $G^*$ for free. Using this, we can define the dual of the dual, which turns out to be equal to the original graph.

$(G^*)^*=G$

Although we won’t see the proof in full, the following fact is used in the proof of the matroidal characterisation later:

Fact – Given a (2-connected) graph $G$ and a graph $H$ that is known to be the dual graph $G^*$ with respect to some planar embedding of $G$ , the data in $H$ is sufficient to completely reconstruct this embedding.

The proof of the above is a bit fiddly but it relies on the idea that, given a planar graph, if you know in what rotational order the edges appear around each vertex, this determines an embedding completely. In a graph $G$ , each vertex $v$ becomes a face in the dual $G^*$ , which is bounded by a collection of edges, the same edges that share the endvertex $v$ . The dual contains the information about the rotational order they should be in, so that the embedding generates that dual.

So to find out if something is embeddable, all we need to do is look for a candidate to be its dual.

All we need now is one more very important property…

A cycle in a graph is a set of edges which form a closed non-self-intersecting walk in the graph. A bond in a graph is a minimal edge cut. That is, a set of edges which disconnects the graph, but removing one fewer edge from that set does not disconnect the graph.

Now we can state a very important property of dual graphs:

Very important property – Let $G=(V,E)$ be a graph, $\iota:G\rightarrow\mathbb{R}^2$ be a particular embedding of $G$ and $S\subseteq E$ be a subset of the edges. Then $S$ is a cycle in $G$ if and only if $S$ is a bond in $G^*$ , the dual with respect to $\iota$ .

So, if we’re looking for a candidate for a dual graph, we have some information about what it must be like. In fact, this is all the information we need!

This brings us to Whiteny’s Criterion, proved in 1932. For a graph $G$ , denote by $C(G)$ the set of cycles in $G$ and by $B(G)$ the set of bonds in $G$ .

Whiteney’s Criterion – Let $G$ be a graph. Then $G$ is planar if and only if there exists a graph $H$ , sharing the same edge as $G$ , such that $C(H)=B(G)$ (or equiv. $B(G)=C(H)$ ).

In this case, there is an embedding giving $H=G^*$ and so $C(G)=B(G^*)$ and $B(G)=C(G^*)$ .

Matroids

It turns out that the set systems $C(G)$ and $B(G)$ both form an object known as a matroid over the edge set $E$ . The axioms of a matroid are often written in terms of ‘dependence’ and ‘independence’, evocative of the linear independence in vector space. In fact, matroids were first introduced by Whitney in 1935 to study linear dependence properties. Can we interpret the following dependence relations on graphs as actual linear dependence relations in some space? Maybe, but we’ll have to leave that for a future post.

One of the formal definitions of a matroid is as follows (we will see in the next post that this is one of many ‘crypomorphic’ definitions):

A matroid $M=(E,\mathcal{C})$ is a set $E$ called the ground set, along with a set $\mathcal{C}$ of subsets of $E$ called circuits satisfying the following axioms:
- (C0) No $O\in\mathcal{C}$ is empty;
- (C1) $\mathcal{C}$ is an antichain w.r.t. inclusion. That is, no circuit is a subset of another;
- (C2) For distinct $O_1,O_2\in\mathcal{C}$ and and $e\in O_1 \cap O_2$ , there is a circuit $O_3\in\mathcal{C}$ s.t. $e\notin O_3$ but $O_3\subseteq O_1\cup O_2$ .
The last condition is called circuit elimination. Subsets of $E$ which contain circuits are called dependent and those which do not contain circuits are called independent.

Given a graph $G=(V,E)$ , the pair $(E,C(G))$ is a matroid called the cycle matroid and is denoted by $M(G)$ . Similarly, the pair $(E,B(G))$ is a matroid called the bond matroid which is denoted by $M^*(G)$ .

We can thus restate Whitney’s Criterion:

Whiteney’s Criterion – Let $G$ be a graph. Then $G$ is planar if and only if there exists a graph $H$ , such that $M(H)=M^*(G)$ .

If $G$ is a graph and $G^*$ is its dual w.r.t. some planar embedding, we get $M^*(G)=M(G^*)$ .

There are a few natural questions about the above. Firstly, how easy is it to determine whether there is a graph which generates a particular matroid? In the section below, we’ll introduce a few more concepts and see a result that brings us back, full-circle, to Kuratowski’s Theorem.

Secondly, What about the relationship between $M(G)$ and $M^*(G)$ ? It turns out that the relationship between these two things is even stronger than first implied.

Let $M=(E,\mathcal{C})$ be a matroid. We say that a subset $B\subseteq E$ is a base if it is maximally independent (as large as possible whilst being circuit-free).

In the next post, we’ll see that we can axiomatise matroids in terms of their bases. For now though we note that the bases of $M(G)$ are exactly the complements of the bases of $M^*(G)$ . In general, given a matrix $M=(E,\mathcal{C})$ , we can define a new matroid $M^*=(E,\mathcal{C})$ by defining its bases to be the complements of all the bases of $M$ . We call $M^*$ the dual matroid of $M$ .

Matroid operations!

Let’s introduce some notation to help us write things down explicitly. For a graph $G=(V,E)$ , write $G\setminus e$ for the graph obtained from $G$ by deleting the edge $e\in E$ . Write $G/e$ for the graph obtained from $G$ by contracting the edge $e\in E$ .

We can define analogous operations on matroids!

Let $M=(E,\mathcal{C})$ be a matroid and $e\in E$ . We define the following deletion and contraction operations, giving matroids on $E\setminus\{e\}$ :
- $M\setminus e$ is the matroid on $E\setminus\{e\}$ with circuits $\mathcal{C}'=\{O\in\mathcal{C}:e\notin O\}$ . That is, all the circuits from $M$ that don’t contain $e$ .
- $M/e$ is the matroid on $E\setminus\{e\}$ with circuits $\mathcal{C}'$ where $\mathcal{C}'$ consists of the minimal nonempty members of the set $\{O\setminus\{e\}:O\in\mathcal{C}\}$ . Essentially, it is all circuits from $M$ , where we remove $e$ and then ensure that the set of circuits is still an antichain.
As you might expect, this definition works exactly like you’d hope it would in the context of cycle matroids. That is, given a graph $G$ ,

$M(G\setminus e)=M(G)\setminus e\quad\text{and}\quad M(G/e)=M(G)/e$

Similarly to graphs, if a matroid $N$ can be obtained from a matroid $M$ by a sequence of deletions and contractions, we call $N$ a minor of the matroid $M$ .

That’s nice. Let’s jump back to dual graphs and dual matroids for a bit.

Now, for planar $G$ , fix some embedding $\iota:G\rightarrow\mathbb{R}^2$ . We get ‘induced’ embeddings for $G\setminus e$ and $G/e$ for all $e\in E$ by performing the deletion or contraction “in real life”. That is, for deletion we ignore the image of our deleted edge in the embedding and for contraction we contract (quotient by) the image of our contracted edge (unless it’s a loop, in which case we delete it) to obtain embeddings of the minors.

We get some fun properties of graph operations on the dual graphs generated by these embeddings:

$(G\setminus e)^*=G^*/e\quad\text{and}\quad (G/e)^*=G^*\setminus e$

Similarly, we get the following for matroids:

$(M\setminus e)^*=M^*/e\quad\text{and}\quad (M/e)^*=M^*\setminus e$

Graphicness

Now we’ve developed all the necessary machinery, we’re ready for the punchline!

We say that a matroid $M$ is graphic if there is a graph $G$ such that $M=M(G)$ . So Whitney’s Criterion boils down to a question of whether a the bond matroid (or equivalently the dual matroid of the cycle matroid) is graphic or not.

But is there a nice way to characterise when a matroid is graphic? Yes! And the result looks suspiciously similar to something we’ve seen before. The following was proven by Tutte in 1959:

Tutte’s Characterisation – A matroid $M$ is graphic if and only if it does not have one of the following forbidden minors:

$M^*(K_5)\quad M^*(K_{3,3})\quad U^2_4\quad F_7\quad F_7^*$

Those first two seem awfully familiar (in fact, we can derive Kuratowski’s Theorem from this). As for the others, they’re a little more complicated.

The matroid $U^2_4$ (the 2,4-uniform matroid) has four elements and its circuits are exactly the 3-element subsets of these four. As for $F_7$ and $F_7^*$ , you’ll need to wait until next time to see the construction of those…
April 7, 2023

Introductions