I spent last week in Waterloo (Ontario) attending a conference celebrating the work of Chris Godsil (and his 65th birthday). It was a week packed with excellent talks, mostly by current or former students and collaborators of Chris.

The conference title is a clear indication of the breadth of Chris’ work: “Algebraic combinatorics: spectral graph theory, Erdös-Ko-Rado theorems and quantum information theory”. The number of talks shows the impact of Chris Godsil’s research. There were way too many speakers for me to even mention all of them, so I’ll just talk about a few of the talks.

The conference opened with Brendan McKay, who talked about counting edge-coloured regular graphs. In the 1980s, together with Chris Godsil, the speaker had determined an asymptotic formula for counting edge-coloured regular bipartite graphs (which correspond to latin rectangles). This result suggested investigating the analogous problem for general edge-coloured regular graphs, which was the subject of the talk.

On the same day the only talk to mention matroids was delivered by Gordon Royle. He talked about roots of the chromatic polynomial of graphs and matroids. The chromatic polynomial of a graph is a polynomial that counts the number of proper colouring of the vertices of the graph with a certain number of colours. I won’t get into any details, you can find a small introduction to the chromatic polynomial on wikipedia . Despite being studied by mathematicians and physicists for a long time, there are many open questions about the chromatic polynomial of graphs, in particular about the location of its real and complex roots. Being an evaluation of the Tutte polynomial, the chromatic polynomial can easily be defined for matroids (although in this case it’s usually called characteristic polynomial). Almost nothing is known about the location of the roots of the chromatic polynomial of matroids, except for results on graphic matroids and cographic matroids (the chromatic polynomial of a cographic matroid is the flow polynomial of the associated graph). I will soon start a project with Gordon on this intriguing subject; hopefully this will lead to some posts about this.

Cheryl Praeger was also part of the small delegation from the University of Western Australia; she gave a history of the classification of finite 2-transitive permutation groups and its applications.

Peter Cameron talked about endomorphisms and synchronisation; every graph has a semigroup of endomorphisms, but one can also start from a transformation semigroup and construct a graph with nice properties.

Chris Godsil’s talk concerned the last part of the conference title, quantum information theory. He talked about a range of tools to obtain graph which have uniform mixing in quantum walks. Coding theory, association schemes and number theory all figured in his talk. Chris lived to his reputation of being an avid photographer by taking pictures of all the speakers at the conference. An email front he organisers, on the day before his talk, suggested that we all took pictures of him during his talk (more precisely, during the 5th slide). I didn’t do a very good job with my picture, but here it is anyway.

The conference closed with a talk by Karen Meagher, who was a post-doc at the University of Waterloo working with Chris Godsil. She talked about an algebraic perspective on Erdös-Ko-Rado theorems. The EKR-theorem gives the exact structure of the largest collection of k-subsets of n elements with the property that every two sets share at least one element. This type of question can be extended to many combinatorial objects. This is the topic of a book that Karen is writing with Chris. Quoting her abstract, the book is “$\epsilon$ away from completion”; I look forward to see it published.

Peter Nelson has been discussing Growth Rates of matroids (in aptly named posts Growth Rates I, II, III and IV). Following his notation, I will denote by $\epsilon(M)$ the number of points of a matroid $M$ (i.e. the number of elements in the simplification of $M$). Deviating just slightly from Peter’s notation, I’ll denote by $h(\mathcal{M},r)$ the growth rate (also called size function) of a class of matroids $\mathcal{M}$. This is the maximum number of points in a matroid in $\mathcal{M}$ of rank at most $r$. In symbols:

$h(\mathcal{M},r)=\textrm{max}\{\epsilon(M)\ |\ M \in \mathcal{M}\ \textrm{and } r(M)\leq r\}$.

In his first post Peter stated the Growth Rate Theorem, a beautiful and very general result on growth rates of minor-closed classes of matroids. For binary matroids, this specialises to saying that, if $\mathcal{M}$ is a minor-closed class of binary matroids, then either:

1. $h(\mathcal{M},r)$ is linear, or
2. $h(\mathcal{M},r)$ is quadratic, and $\mathcal{M}$ contains all graphic matroids, or
3. $\mathcal{M}$ is the class of all binary matroids.

I will discuss results and conjectures about the exact value of the growth rate for specific classes of binary matroids. The conjectures stated here were made possible by Gordon Royle’s database of binary matroids. I’ve been working on some of these conjectures with Joseph Kung, Dillon Mayhew and Gordon Royle.  I’ll denote by $EX(M)$ the class of binary matroid with no $M$-minor.

Let’s first look at binary matroids that fall into outcome (1) of the Growth Rate Theorem for binary matroids, i.e. classes of binary matroids that do not contain all graphic matroids. For these classes we know that the growth rate is linear. The first class I’ll consider is that of cographic matroids. A simple cographic matroid arises from a graph where every vertex has degree at least 3. The rank of the matroid (if the graph in question is $G$), is $|E(G)|-|V(G)|+1$. Now suppose that $G$ has a vertex of degree at least 4. Split that vertex into two vertices of degree at least 2 and add an edge between these two vertices (this corresponds to an extension in the matroid). This new graph gives rise to a cographic matroid with the same rank as the initial one, but with one more element. Thus the largest simple cographic matroids arise from cubic (i.e. 3-regular) graphs. With this simple argument we proved that

1) $h(\textrm{cographic matroids}, r)=3(r-1)$.

This was first noted by Joseph Kung in [Ku86].

In the next results I’ll be a bit sloppy and write $EX(G)$ for $EX(M(G))$. I will also be a bit sloppy with small rank cases that can easily be worked out. It is well-known that the class $EX(K_4)$ is exactly the class of series-parallel graphs. Thus:

2) $h(EX(K_4),r)=2r-1$.

Let $W_n$ denote the wheel with $n$ spokes. By giving a decomposition theorem for $EX(W_4)$, Oxley [Ox87] proved that

3) $h(EX(W_4))=3r-2$ if $r$ is odd, and $h(EX(W_4))=3r-3$ if $r$ is even.

The extremal examples are parallel connections of copies of $F_7$ and at most one copy of the rank-4 binary spike (called $Z_4$ in [Ox11]). Having extremal examples of large rank built from small extremal examples seem to be “common” in these types of classes (in fact, that’s also the case for 2) if we see series-parallel graphs as parallel connections of copies of $K_3$). This is also the case for the class $EX(K_{3,3})$, as was shown by Mayhew, Royle and Whittle in [MRW10]. This result follows again from a decomposition theorem for the class $EX(K_{3,3})$.

4) $h(EX(K_{3,3}))=14r/3-a$, where $a=7$ if $r=0$ (mod 3), $a=11/3$ if $r=1$ (mod 3) and $a=19/3$ if $r=2$ (mod 3).

The extremal examples are parallel connections of copies of $PG(1,2)$, $PG(2,2)$ and $PG(3,2)$.

Unfortunately, when looking at the next obvious class what I can state is only a conjecture.

Conjecture 1: $h(EX(K_5),r)=9r/2-a$, where $a=13/2$ if $r$ is odd and $a=6$ if $r$ is even. Moreover, the extremal examples are generalised parallel connections along a line of copies of $C_{12}$ and at most one copy of $F_7$.

The matroid $C_{12}$ is one of the sporadic examples appearing in [MRW10] (where you can also find a definition). While I think that Conjecture 1 may be attacked directly, I wish  the best of luck to anyone who would try to prove it via a decomposition theorem for $EX(K_5)$ (which appears to be a much harder problem than the already very difficult decomposition theorem for $EX(K_{3,3}$).

Let’s now move on to classes of binary matroids with quadratic growth rate. A classical result by Heller [He57] gives the growth rate for binary matroids with no $F_7$-minor.

5) $h(EX(F_7),r)=\binom{r+1}{2}$

and it’s not hard to see that the extremal examples are given by graphic matroids. Since $F_7$ is a splitter for the class of binary matroids with no $F_7^*$-minor, we deduce that, for $r\geq 4$,

6) $h(EX(F_7^*),r)=\binom{r+1}{2}$.

In [KDPR13] we showed that the same growth rate is maintained (for $r \geq 5$) by the larger class $EX(AG(3,2))$, and the extremal examples are still graphic matroids.

7) $h(EX(AG(3,2)),r)=\binom{r+1}{2}$.

We also showed that, for rank at least 6, the extremal non-regular example at rank $r$ is the generalised parallel connection along a line of $M(K_r)$ and $F_7$.

What about other classes of binary matroids with quadratic growth? Unfortunately not much is known… However, I do have some interesting conjectures to propose. These are easier to state in terms of even cycle matroids. I mentioned these matroids in my post on biased graphs, but I’ll quickly redefine them here. If $G$ is a graph and $S$ a subset of its edges, we call the pair $(G,S)$ a signed graph. The even cycle matroid arising from $(G,S)$ is the binary matroid represented by the following matrix. Take any binary matrix $A$ representing $M(G)$ (such a matrix has columns indexed by $E(G)$). Now add to $A$ the row incidence vector of $S$ (i.e. a row where entry $e$ is 1 if $e \in S$ and 0 otherwise).

How large can a simple even cycle matroid be? One can see fairly easily that if the even cycle matroid of $(G,S)$ is simple, then $G$ cannot have pairs of parallel edges that are both in $S$ or both not in $S$, and every loop of $G$ has to be in $S$. Moreover we can have at most one such loop. So the largest simple even cycle matroid (for rank $r$) is obtained when we choose $G$ to be $K_r$ with all edges doubled plus a loop, and we choose $S$ to contain exactly one edge per parallel class, plus the loop. The corresponding even cycle matroid is the geometric cone of $M(G)$. So the growth rate for the class of even cycle matroids is $2\binom{r}{2}+1$. The next conjecture states that this is also the growth rate for $EX(PG(3,2))$.

Conjecture 2: For $r \geq 6$, $h(EX(PG(3,2)),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.

A binary matroid $M$ is an even cycle matroid if and only if it has a binary single element extension $M’$ (by an element $e$) such that $M’/e$ is graphic. Since any single element contraction of $PG(3,2)$ is not graphic, $PG(3,2)$ is not an even cycle matroid and the whole class of even cycle matroids is contained in $EX(PG(3,2))$.

Let $PG(3,2)^-$ denote the matroid obtained from $PG(3,2)$ by deleting an element. Then $PG(3,2)^-$ is also not an even cycle matroid. The next conjecture is weaker (and possibly easier to prove) than Conjecture 2.

Conjecture 3: For $r \geq 6$, $h(EX(PG(3,2)^-),r)=2\binom{r}{2}+1$, and the extremal examples for $r\geq 7$ are even cycle matroids.

What if we delete two elements from $PG(3,2)$? (I’ll call the corresponding matroid $PG(3,2)^{- -}$). I conclude the post with this conjecture.

Conjecture 4: For $r \geq 6$, $h(EX(PG(3,2)^{- -}),r)=\binom{r}{2}+2r-2$.

The extremal examples are again even cycle matroids, but not the same as for Conjecture 2. This is because $PG(3,2)^{- -}$ is an even cycle matroid itself, so $EX(PG(3,2)^{- -})$ cannot contain the whole class of even cycle matroids. The (conjectured) extremal examples in this class arise from signed graphs $(G_r,S_r)$ described as follows. Pick two vertices $u$ and $v$ in $K_r$. Double all the edges incident with $u$ or $v$ (or both) and add a loop. Call the resulting graph $G_r$. Now put in $S_r$ exactly one edge per parallel class of size 2, plus the loop (and no other edges). It can be shown by induction on $r$ (if you know the signed graph representation of $PG(3,2)^{- -}$) that these even cycle matroids do not, indeed, contain $PG(3,2)^{- -}$ as a minor.

References

[Ox87] J. Oxley,  The binary matroids with no 4-wheel minor, Trans. Amer. Math. Soc. 301, 1 (1987), 63-75.

[Ox11] J. Oxley, Matroid theory, second ed., vol. 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, 2011.

This post is mainly about results that I proved together with Matt DeVos and Daryl Funk, partly while they were visiting the University of Western Australia after the 37ACCMCC (Dillon talked about this conference in his blog post on December 16, 2013).

First, let me remind you of what a biased graph is (more details can be found in my introductory post). A biased graph is a pair $(G,\mathcal{B})$, where $G$ is a graph and $\mathcal{B}$ is a set of cycles of $G$ satisfying the theta-property: there is no theta subgraph of $G$ that contains exactly two cycles in $\mathcal{B}$. Cycles in $\mathcal{B}$ are called balanced, while the other cycles of $G$ are unbalanced.

A quite general way of constructing biased graphs is via group-labelled graphs. Pick your favourite (say multiplicative) group $\Gamma$ and graph $G$, and assign to each edge $e$ of $G$ an orientation and a value $\phi(e)$ from $\Gamma$: then what you have is a group-labelled graph. Now consider any walk $W$ in $G$, with edge sequence $e_1,e_2,\ldots,e_k$ and extend $\phi$ as

$\phi(W)=\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}$,

where $\textrm{dir}(e_i)$ is 1 if $e_i$ is forward in $W$, and -1 otherwise. Then we define a cycle $C$ of $G$ to be balanced if a simple closed walk $W$ around $C$ has $\phi(W)=1$. It’s easy to see that this definition is independent of the choice for $W$, and in this way we get, indeed, a biased graph. In this case we identify the group-labelled graph with the associated biased graph. If a biased graph can be constructed in this way from a group $\Gamma$, then we say that such a biased graph is $\Gamma$-labellable. If a biased graph is $\Gamma$-labellable for some group $\Gamma$, then we say that the biased graph is group-labellable. Not all biased graphs are group-labellable, hence the question that is the title of this post. As it turned out, there is a nice topological answer to this question.

Theorem 1: Let $(G,\mathcal{B})$ be a biased graph; construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for every $C \in \mathcal{B}$. Then the following are equivalent:

1. $(G,\mathcal{B})$ is group-labellable.
2. $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
3. Every unbalanced cycle of $G$ is noncontractible in $K$.

Before I explain a bit how the proof works, let me discuss some nice constructions that we derived using this theorem. For any group $\Gamma$, the class of $\Gamma$-labellable graphs is closed under minors, for both definition of minors given in my second post on biased graphs. Using Theorem 1, we proved that if $\Gamma$ is an infinite group then there are infinitely many excluded minors to the class of $\Gamma$-labellable biased graphs. In fact, we proved something stronger, namely that there is an infinite list of excluded minors on $n$ vertices for every $n \geq 3$.

Theorem 2: For every $n \geq 3$ and $\ell$ there exists a biased graph $(G,\mathcal{B})$ with the following properties:

• $G$ is a graph on $n$ vertices and every pair of vertices is joined by at least $\ell$ edges.
• $(G,\mathcal{B})$ is not group-labellable.
• For every infinite group $\Gamma$, every proper minor of $(G,\mathcal{B})$ is $\Gamma$-labellable.

For a group $\Gamma$, let $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ denote the class of frame and lift matroids respectively that arise from $\Gamma$-labelled graphs. From Theorem 2 (and a one-page argument) we also show that

Theorem 3: For every infinite group $\Gamma$ and every $n \geq 3$ the classes $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ have infinitely many excluded minors of rank $n$.

Theorem 3 implies in particular that frame and lift matroids are not well-quasi ordered. This was already known, since swirls and spikes form infinite antichains of, respectively, frame and lift matroids (see [GGW02] and [M05]). As far as I know, however, it wasn’t known that there are infinite antichains of frame and lift matroids all of the same rank.

I’ll conclude the post by mentioning the two main ingredients for the proof of Theorem 1. The first main part of the proof consists of expressing $\pi_1(K)$ in the appropriate way. Let $\gamma_e$ be a variable associated with every edge in $G$. We use an application of Van Kampen’s Theorem (see Hatcher’s book on algebraic topology), to express $\pi_1(K)$ as the group presented by the generating set $\{\gamma_e | e \in E(G)\}$, with the relations given by setting

$\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}=1$,

for each balanced cycle $C$ and any closed walk $W$ around $C$ with edge sequence $e_1,\ldots,e_k$. This allows us to show that (3) implies (2).

The second ingredient of the proof involves reroutings. Consider a closed walk $W$ containing a path $P$, and a balanced cycle $C$ containing $P$. Let $P’$ be the complement of $P$ in $C$; then the walk $W’$ obtained by from $W$ by replacing $P$ with $P’$ is obtained by rerouting along the balanced cycle $C$. If in the previous definition $W$ and $W’$ are both simple walks around a cycle, then the theta property implies that $W$ is balanced if and only if $W’$ is balanced. However, if we start with a simple closed walk $W_1$ around a cycle, we do a series of reroutings and we end with a simple closed walk $W_k$ around a cycle, then knowing the bias of $W_1$ doesn’t tell us anything about the bias of $W_k$, since the intermediate closed walks in the sequence of reroutings may not be simple closed walks around a cycle. However, things are different for group-labelled graphs.

Suppose that $(G,\mathcal{B})$ is a group-labelled graph (so every edge $e$ of $G$ has an orientation and a value $\phi(e)$ from some group $\Gamma$). Consider the extension of $\phi$ to closed walks of $G$, as above. If a closed walk $W’$ is obtained from a closed walk $W$ by rerouting along a balanced cycle, then $\phi(W)=\phi(W’)$ (because $C$ is balanced, so $\phi(P)=\phi(P’)$ in the definition of rerouting). So if $(G,\mathcal{B})$  is group-labelled, then we can never start from a simple closed walk around a balanced cycle and obtain (via reroutings) a simple closed walk around an unbalanced cycle. That is, any biased graph $(G,\mathcal{B})$ that is group-labellable satisfies the following:

4. There does not exist a sequence $W_1,W_2,\ldots,W_k$ of closed walks such that each $W_{i+1}$ is obtained from $W_i$ by rerouting along a balanced cycle and $W_1$ is a simple walk around a balanced cycle and $W_k$ is a simple walk around an unbalanced cycle.

By the argument above, (1) in Theorem 1 implies (4). Using the fundamental group of $K$ we can show that if (3) fail then (4) fails (so (4) implies (3)).

References

[GGW02] J. Geelen, A.M.H. Gerards, and G. Whittle, Branch-Width and Well-Quasi-Ordering in Matroids and Graphs, J. Combin. Theory Ser. B 84 (2002), 270-290.

[M05] D. Mayhew, Inequivalent Representations of Bias Matroids, Combinatorics, Probability and Computing 14 (2005) 567-583.

In this post I’ll discuss a way of constructing matroids from other matroids. A simpler form of this construction was first introduced by Rado. I will follow partly Matt DeVos’ notes on Rado matroids and partly [Oxley11, Sections 11.1-11.3].

Let $G$ be a bipartite graph, with bipartition $(X,Y)$. Denote by $N(S)$ the set of neighbours of vertices in $S$ that are in $V(G)-S$. Suppose that $M$ is a matroid on ground set $Y$ with rank function $r$. Let $t$ be any integer and define $\mathcal{C}$ to be the set of minimal non-empty subsets of $X$ satisfying $|S|>r(N(S))+t$. With this definition we have the following proposition. The proof is short, so I’ll include it.

Proposition 1: $\mathcal{C}$ is the set of circuits of a matroid on $X$.

proof: From the definition we immediately have that the first two circuit axioms are satisfied. Now consider distinct $C_1, C_2 \in \mathcal{C}$ and an element $e \in C_1 \cap C_2$. Using (in the last inequality) the fact that $C_1\cap C_2$ does not contain any member of $\mathcal{C}$, we have that $\\|C_1 \cup C_2| + |C_1 \cap C_2| = |C_1| + |C_2|\\ \geq r(N(C_1))+r(N(C_2))+2t+2\\ \geq r(N(C_1)\cup N(C_2)) + r(N(C_1) \cap N(C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+r(N(C_1 \cap C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+|C_1 \cap C_2|-t +2t +2$.

Therefore $r(N(C_1 \cup C_2)) \leq |C_1 \cup C_2|-t-2$. Let $C’=(C_1 \cup C_2)-e$.

Then $r(N(C))\leq kr(N(C_1 \cup C_2))\leq |C_1 \cup C_2|-t-2=|C|-t-1$. Hence $r(N(C))< |C|-t$, so $C$ contains an element of $\mathcal{C}$. $\hspace{2 cm} \Box$

I’ll call a matroid defined this way a Rado matroid. Rado defined these matroids for $t=0$, so in this case I will call the matroid a standard Rado matroid. We may make the definition above more general by adding a parameter $k \geq 1$ and defining $\mathcal{C}$ to be the minimal non-empty sets satisfying $|S|>kr(N(S))+t$. Then the proposition above still holds (with the same proof). However, all the examples I’m going to introduce here have $k=1$, so I will stick to the simpler definition.

Note that, strictly speaking, every matroid is a Rado matroid: if $N$ is any matroid on ground set $E$, then we can obtain it as a standard Rado matroid on $G$ with bipartition $(E,E)$, where every vertex is adjacent to its copy (and the matroid on $Y=E$ is $N$). However, seeing a matroid as a Rado matroid is sometimes useful, for example in the case of the hypergraphic matroids (which I will define later).

Lots of matroids may be constructed as Rado matroids (in a non-trivial way). Since there are many objects involved in the definition of a Rado matroid and I’m a bit lazy, in the following examples I will always assume that $G, X, Y, M$ and $t$ are as above and I’ll denote just by $R$ the Rado matroid.

• If $t \leq -r(M)$, then $R=U_{0,n}$.
• If $t \geq |Y|$, then $R=U_{n,n}$.
• If $M$ is a free matroid, then the standard Rado matroid is a transversal matroid (with respect to the sets $N(v)$ for $v \in X$).
• If $H$ is a graph and $G$ has bipartition $(E(H),V(H))$, where $e \in E(H)$ is adjacent to $v \in V(H)$ if $v \in e$, and $M$ is a free matroid, then the standard Rado matroid is the bicircular matroid of $H$. Thus we see that bicircular matroids are transversal matroids [Mat77].
• Define $G$ from $H$ as above and let $M$ be a free matroid again. If now we choose $t=-1$ we obtain as a Rado matroid the graphic matroid of $H$.

We can generalise the construction above to hypergraphs. Suppose that $H=(V,F)$ is a hypergraph and define $G$ as the graph with bipartition $(F,V)$, where $f \in F$ is adjacent to $v \in V$ if $v \in f$. Let $M$ be a free matroid and set $t=-1$. Then $R$ is the hypergraphic matroid, defined by Lorea [Lor75]. We can also see hypergraphic matroids as standard Rado matroids, with this alternative definition. Our starting hypergraph is still $H=(V,F)$. We define the bipartition of $G$ to be $(F,E)$, where $E$ is the edge set of $K_V$, the complete graph on $V$. For $f \in F$ and $e=uv \in E$, we set $e$ to be adjacent to $f$ if $u,v \in f$. Now if we choose $M$ to be the graphic matroid on $K_V$ then the standard Rado matroid is again the hypergraphic matroid of $H$. The advantage of this alternative definition is that Rado [Rado42] proved the following result for standard Rado matroids (where again $G, X, Y$ and $M$ are as in definition above). Call a matching independent if the set of vertices it covers in $Y$ is independent in $M$.

Theorem 2: If $R$ is a standard Rado matroid then a set $S \subseteq X$ is independent in $R$ if and only if there is an independent matching in $G$ covering $S$ (i.e. $S$ may be matched to an independent set of $M$).

From the definition of standard Rado matroids, we immediately have that a set $S \subseteq X$ is independent in $R$ exactly when $|S’|\leq r(N(S’))$ for every $S’$ contained in $S$. Thus Rado’s theorem is saying that this condition is satisfied exactly when $S$ may be matched to an independent set of $M$. This result looks suspiciously similar to P. Hall’s marriage theorem [Hall35]: in fact we obtain Hall’s marriage theorem from Theorem 2 when $M$ is a free matroid. A proof of Theorem 2 may be found, for example, in Matt DeVos’ notes on Rado matroids. In the same notes you may also find a proof of the following generalisation of König’s Theorem for bipartite graphs.

Theorem 3: There exists $A$ contained in $X$ such that the size of the largest independent matching is equal to $|X-A|+r(N(A))$.

Corollary 4: In a standard Rado matroid, the rank of $S\subseteq X$ is equal to $$min_{A \subseteq S} \{|S-A|+r(N(A))\}.$$

Going back to our definition of a hypergraphic matroid as a standard Rado matroid, Theorem 2 tells us that a set of hyperedges $I$ is independent in this matroid if and only if we may replace every $f \in I$ with an edge $uv$, for $u,v \in f$, so that the resulting graph is a forest. This result was proved in [FKK03] (using the first definition of hypergraphic matroids).

Another interesting application of Rado’s construction is that we may obtain the Matroid Union Theorem (so relevant to our blog) as a consequence.  In fact, let $N_1,\ldots,N_k$ be matroids on a common ground set $E$, and let $M$ be the direct sum of $N_1,\ldots,N_k$. Define a bipartite graph $G$ with bipartitions $E$ and $E_1\cup \cdots\cup E_k$, where each $E_i$ is a copy of $E$ (seen as the ground set of $N_i$). Any element $e \in E$ is adjacent to each of its copies in $E_1,\ldots,E_k$. Then the standard Rado matroid is just the union matroid $N_1 \vee \cdots \vee N_k$, first introduced by Nash-Williams [N-W66]. As expected, Corollary 4 implies that the rank of a set $S$ in $N_1 \vee \cdots \vee N_k$ is $$min_{A \subseteq S} \{|S-A|+r_1(A)+\cdots +r_k(A)\},$$ where $r_i(A)$ is the rank of $A$ in $N_i$.

I was first introduced to Rado matroids while working on a paper [DMP13] with Matt DeVos and Jessica McDonald. Another nice theorem that we used in that paper is a result by Király, Lau and Singh [KLS08]. Basically this theorem says that, if $M$ has a fractional basis satisfying some constraints, then it has an actual basis almost satisfying those constraints. This theorem has nothing to do with Rado matroids, but I think it’s a nice result so I’m going to go ahead and end my post on it. First let me define what I mean by a fractional basis.

Let $M$ be a matroid on $E$ with rank function $r$ and let $x \in \mathbb{R}^E$ be a vector satisfying the following three constraints:

1. $0 \leq x(e) \leq 1$, for every $e \in E$.
2. $x(S) \leq r(S)$, for every $S \subseteq E$.
3. $x(E)=r(E)$.

Then we say that $x$ is a fractional basis of $M$. The name is justified by the following result of Edmonds’ [Edm69].

Theorem 5: If a vector $x$ satisfies 1. and 2. above, then $x$ is a convex combination of incidence vectors of independent sets of $M$.

Thus a fractional basis is a convex combination of incidence vectors of bases of $M$. The last result of this post (from [KLS08]) may be used, for example, to prove the existence of a bounded degree spanning tree in a graph if a bounded degree fractional spanning tree exists.

Theorem 6: Let $M$ be a matroid on $E$, let $x$ be a fractional basis of $M$, and let $\mathcal{F}$ be a collection of subsets of $E$ so that every $e \in E$ is contained in at most $d$ members of $\mathcal{F}$. Then $M$ has a basis $B$ such that every $F \in \mathcal{F}$ satisfies $|B \cap F| \leq \lceil x(F) \rceil +d -1$.

References

[DMP13] M. DeVos, J. McDonald, I. Pivotto, Packing Steiner trees, submitted. (available on the ArXiv)

[Edm69] J. Edmonds, Submodular functions, matroids and certain polyhedra, Com- binatorial structures and their applications (Proc. Calgary Internat. Conf. 1969), 69-87. Gordon and Breach, New York.

[FKK03] A. Frank, T. Király, and M. Kriesell, On decomposing a hypergraph into $k$ connected sub-hypergraphs, Discrete Appl. Math. 131 (2003), 373-383.

[Hall35] P. Hall, On representatives of subsets, Quart. J. London Math. Soc. 10 (1935), 26-30.

[KLS08] T. Király, L. C. Lau, and M. Singh, Degree bounded matroids and submodular flows, Proceedings of 13th International Conference IPCO 2008, LNCS 5035 (2008), 259-272.

[Lor75] M. Lorea, Hypergraphes et matroides, Cahiers Centre Etud. Rech. Oper. 17 (1975), 289-291.

[Mat77] L.R. Matthews, Bicircular Matroids, Quart. J. Math. Oxford (2), 28 (1977), 213-228.

[N-W66] C. St. J. A, Nash-Williams, An application of matroids to graph theory, In Theory of Graphs (Internat. Sympos. Rome) (1966), 263-265. Dunod, Paris

[Oxley11] J. Oxley, Matroid Theory, Oxford University Press, New York (2011).

[Rado42] R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89.