In the last post, we had just reached the definition of a 1-flowing matroid. To recap, let $M$ be a matroid on the groundset $E$, and let $e$ be an element of $E$. We choose a function that assigns a positive integral capacity, $c_{x}$, to each element $x\in E-e$. A flow is a function that assigns a non-negative real number, $f_{C}$, to each circuit, $C$, containing $e$. We insist that, for every $x\in E-e$, the inequality $\sum f_{C}\leq c_{x}$ holds (here the sum is taken over all circuits that contains $e$ and $x$). The value of a flow is $\sum f_{C}$, where the sum is taken over all circuits that contain $e$. In the last post, the following inequality was an exercise.

$\text{maximum value of a flow} \leq \min\{\sum_{x\in C^{*}-e}c_{x}\}$

(the minimum is taken over all cocircuits $C^{*}$ such that $e\in C^{*}$).

Proof. Let $C^{*}$ be an arbitrary cocircuit that contains $e$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $\mathcal{D}$ be the collection of all ordered pairs $(x,C)$ where $x$ is an element in $C^{*}-e$, and $C$ is a circuit that contains $\{e,x\}$. Since a circuit and a cocircuit cannot intersect in $\{e\}$, it follows that every circuit in $\mathcal{C}$ appears in an ordered pair in $\mathcal{D}$. Therefore

\[
\qquad\sum_{C\in\mathcal{C}}f_{C}\leq\sum_{(x,C)\in\mathcal{D}}f_{C}
=\sum_{x\in C^{*}-e}\sum_{C\in\mathcal{C}\colon x\in C}f_{C}
\leq \sum_{x\in C^{*}-e}c_{x}\qquad\square
\]

We have shown that the value of a flow is bounded above by the capacity of a cut, for every matroid, every element $e$, and every choice of capacities. In some matroids, the inequality is actually an equality for every choice of capacities. In this case, we say that $M$ is $e$-flowing. If $M$ is $e$-flowing for every element $e$, then we say $M$ is $1$-flowing. This definition is motivated by min-max theorems in graph theory, such as the max-flow min-cut theorem. As detailed in the last post, these theorems show that graphic and cographic matroids are $1$-flowing. Seymour’s $1$-flowing conjecture concerns a characterisation of the $1$-flowing matroids.

Bertrand Guenin [Gue02] restates Seymour’s conjecture in a way that I initially did not understand. This method of talking about $1$-flowing matroids involves using ideas from linear programming. Say that $M$ is a matroid on the groundset $E$, and $e$ is an element of $E$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $A$ be the $0$-$1$ matrix whose columns are labelled by elements of $E-e$, and whose rows are labelled by the members of $\mathcal{C}$, where an entry $A_{C,x}$ is equal to one if and only if $x\in C$. Let $\mathcal{P}$ be the set of vectors, $\mathbf{x}$, in $\mathbb{R}^{E-e}$ such that every entry of $\mathbf{x}$ is non-negative, and every entry of $A\mathbf{x}$ is at least $1$. This is the intersection of several half-spaces in $\mathbb{R}^{E-e}$, so $\mathcal{P}$ is a polytope. Guenin’s statement of Seymour’s conjecture rests on the following fact:

Lemma 1. If $M$ is $e$-flowing, then the vertices of $\mathcal{P}$ have $0$-$1$ coordinates.

This wasn’t obvious to me, so I spent some time thinking about why it should be true. My relatively naive proof follows. A more sophisticated argument can be found in Cornuejols [Cor01].

If $\mathbf{a}$ and $\mathbf{b}$ are real vectors with the same number of entries, we write $\mathbf{a}\geq\mathbf{b}$ to mean that every entry of $\mathbf{a}$ is at least as large as the corresponding entry in $\mathbf{b}$. We write $\mathbf{0}$ and $\mathbf{1}$ for the vectors of all zeroes and the vector of all ones, and we use $\mathbb{R}_{\geq 0}$ to denote the set of non-negative reals. Let $\mathbf{c}$ be the vector in $\mathbb{Z}_{+}^{E-e}$ that contains the capacity of each element in $E-e$.

Proposition 1. The value of a maximum flow is equal to
\[
\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}.
\]

Proof. The vector $\mathbf{y}$ assigns a non-negative real value to each circuit containing $e$. The linear program maximises the sum of these values, while respecting the constraint that the sum of the values on circuits passing through an element of $E-e$ must be no greater than the capacity of that element. Thus the solution to the linear program is exactly the maximum value of a flow. $\square$

Proposition 2. The minimum of $\sum_{x\in C^{*}-e}c_{x}$ taken over all cocircuits, $C^{*}$, that contain $e$, is equal to
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}.
\]

Proof. A circuit and a cocircuit cannot meet in a single element. Therefore, if $C^{*}$ is a cocircuit containing $e$, and $C$ is a member of $\mathcal{C}$, then $C^{*}-e$ and $C-e$ have a non-empty intersection. In other words, if $\mathbf{a},\mathbf{b}\in \{0,1\}^{E-e}$ are the characteristic vectors of $C-e$ and $C^{*}-e$ respectively, then $\mathbf{a}^{T}\cdot \mathbf{b} \geq 1$. Thus the dot product of $\mathbf{b}$ with any row of $A$ is at least one. This means that $A\mathbf{b} \geq \mathbf{1}$, so $\mathbf{b}$ is contained in $\{A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. Thus
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}
\leq\\
\min\{\sum_{x\in C^{*}-e}c_{x}\colon C^{*}\ \text{is a cocircuit of}\ M,\ e\in C^{*}\}.
\end{multline*}

For the converse, assume $\mathbf{x}_{0}\in \{0,1\}^{E-e}$ is a solution to the program $\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. As the entries of $\mathbf{c}$ are non-negative, we can assume that there is no vector in $\{\mathbf{x}\in\{0,1\}^{E-e}\colon A\mathbf{x} \geq \mathbf{1}\}$ with support properly contained in the support of $\mathbf{x}_{0}$. Therefore $\mathbf{x}_{0}$ is the characteristic vector of a set $D\subseteq E-e$, where $D$ is minimal with respect to meeting every $C\in \mathcal{C}$. We will show that $D\cup e$ is a cocircuit of $M$. Suppose that $D\cup e$ is coindependent. Then there is a basis $B$ of $M$ that has an empty intersection with $D\cup e$. Now $B\cup e$ contains a circuit that contains $e$, and this circuit has an empty intersection with $D$. This is a contradiction, so $D\cup e$ contains a cocircuit $C^{*}$. Suppose that $e\notin C^{*}$, and let $c$ be an arbitrary element of $C^{*}$. By the minimality of $D$, there is a circuit $C \in\mathcal{C}$ such that $C$ has a non-empty intersection with $D$, but not with $D-c$. Then $C$ meets the cocircuit $C^{*}$ in a single element, $c$. This contradiction means that $e\in C^{*}$. As a circuit and a cocircuit cannot meet in a single element, every circuit in $\mathcal{C}$ meets $C^{*}-e\subseteq D$ in at least one element. The minimality of $D$ implies that $C^{*}-e=D$, so $D\cup e$ is a cocircuit, as desired. Now $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to $\sum_{x\in C^{*}-e}c_{x}$, and the proposition follows. $\square$

It follows from Propositions 1 and 2 that $M$ is $e$-flowing if and only if the two programs
\[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\]
and
\[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}\]
have the same optimal value for every choice of the vector $\mathbf{c}\in \mathbb{Z}_{+}^{E-e}$.

Let $A’$ be the matrix obtained by stacking a copy of $A$ on top of a copy of the identity matrix $I_{E-e}$. This means that the vector $\mathbf{x}\in\mathbb{R}^{E-e}$ is contained in the polytope $\mathcal{P}$ if and only if it satisfies the following system of inequalities:
\[A’\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}.\]
If $\mathbf{x}$ is a vector in $\mathcal{P}$, then $A’_{\mathbf{x}}$ is the submatrix of $A’$ consisting of all rows $\mathbf{a}^{T}$ satisfying
\[
\mathbf{a}^{T}\mathbf{x}=
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
In other words, $A’_{\mathbf{x}}$ consists of all rows of $A’$ for which the corresponding inequality in the system
\[A’\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
is actually an equality for the vector $\mathbf{x}$. The vertices of $\mathcal{P}$ can be characterised by saying that they are the vectors $\mathbf{x}\in\mathcal{P}$ such that $A’_{\mathbf{x}}$ contains an $|E-e|\times |E-e|$ non-singular matrix.

Now assume that $\mathcal{P}$ has a vertex that does not have $0$-$1$ coordinates. We will show that $M$ is not $e$-flowing, and this will establish Lemma 1. To this end, assume that $\mathbf{x}_{0}$ is a vertex of $\mathcal{P}$ with at least one coordinate that is not $0$ or $1$. Let $A_{0}$ be an $|E-e|\times |E-e|$ non-singular submatrix of $A_{\mathbf{x}_{0}}$. Let $\mathbf{b}_{0}$ be the submatrix of the vector on the righthand side of
\[A’\mathbf{x}_{0}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
consisting of rows that correspond to rows of $A_{0}$. This means that $\mathbf{x}_{0}$ is the unique solution to the equation $A_{0}\mathbf{x}=\mathbf{b}_{0}$. Define $\mathbf{c}^{T}$ to be the sum of the rows of $A_{0}$. Then $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to the weight of $\mathbf{b}_{\mathbf{x}}$. Let $\mathbf{x}’$ be any point in $\mathcal{P}$ other than $\mathbf{x}_{0}$. Since $\mathbf{x}’$ is not the unique solution to $A_{0}\mathbf{x}=\mathbf{b}_{\mathbf{x}}$, there is some row $\mathbf{a}^{T}$ in $A_{0}$ such that
\[
\mathbf{a}^{T}\mathbf{x}’ >
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
This means that $\mathbf{c}^{T}\mathbf{x}’$ is greater than the weight of $\mathbf{b}_{\mathbf{x}}$. It follows that $\mathbf{x}_{0}$ is the unique solution to the linear program
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}
\]
so
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}<\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}, \end{multline*} since $\mathbf{x}_{0}$ is not a $0$-$1$ vector. Now if $\mathbf{y}$ and $\mathbf{x}$ are feasible points in, respectively, the programs \[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\] and \[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\},\] then $A\mathbf{x}\geq \mathbf{1}$, so $\mathbf{1}^{T} \leq \mathbf{x}^{T}A^{T}$. This means that \[ \mathbf{1}^{T}\mathbf{y} \leq (\mathbf{x}^{T}A^{T})\mathbf{y}= \mathbf{x}^{T}(A^{T}\mathbf{y}) \leq \mathbf{x}^{T}\mathbf{c} = \mathbf{c}^{T}\mathbf{x} \] so \begin{multline*} \max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\leq\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}. \end{multline*} (We can also deduce this using linear programming duality.) Combining this with the fact in the last paragraph, we see that \begin{multline*} \max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}<\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}. \end{multline*} Hence the maximum value of a flow is strictly less than the minimum capacity of a cut, for this choice of the capacity function $\mathbf{c}$. This demonstrates that $M$ is not $e$-flowing, exactly as we wanted. In fact, with a bit more work we can show that the converse also holds. That is, $M$ is $e$-flowing if and only if the vertices of $\mathcal{P}$ all have $0$-$1$ coordinates. [Gue02] B. Guenin, Integral polyhedra related to even-cycle and even-cut matroids. Math. Oper. Res. 27 (2002), no. 4, 693–710. [Cor01] G. Cornuéjols, Combinatorial optimisation: Packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, 74. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.

Let $G$ be a graph with distinct vertices $s$ and $t$, and let $\mathcal{C}$ be the family of paths from $s$ to $t$. Let us say that a subfamily of $\mathcal{C}$ is a matching if its members are pairwise edge-disjoint. An $s$-$t$ cut is a subset of edges in $G$ with the property that removing that set of edges destroys every path from $s$ to $t$. From this definition, we can clearly see that an $s$-$t$ cut contains an edge from each path in any matching. Thus we conclude:

maximum size of a matching $\leq$ minimum size of an $s$-$t$ cut.

It is a very well-known result, but no less lovely for it, that this inequality is actually an equality. That is, the minimum size of an $s$-$t$ cut is exactly equal to the maximum size of a matching. This classic result, known as the max-flow min-cut theorem was proved by Ford and Fulkerson [FF1956], and independently by Elias, Feinstein, and Shannon [EFS1956].

Let us consider this phenomenon in a more general context. Let $E$ be a finite set, and let $\mathcal{C}$ be a family of subsets. A matching will be a subfamily of $\mathcal{C}$ consisting of pairwise disjoint subsets of $E$. A transversal will be a subset of $E$ that has non-empty intersection with each member of $\mathcal{C}$. Then clearly

maximum size of a matching $\leq$ minimum size of a transversal

and we will say that the system $(E,\mathcal{C})$ packs if the two quantities are equal. This terminology was introduced by Seymour [Sey1977]. Thus, if $E$ is the edge set of $G$, and $\mathcal{C}$ is the family of edge-sets of $s$-$t$ paths, then $(E,\mathcal{C})$ packs.

Let’s look at another, dual, example. Again, $G$ is a graph, and $s$ and $t$ are distinct vertices. Let $\mathcal{C}^{*}$ be the family of $s$-$t$ cuts. If we consider an arbitrary matching in $\mathcal{C}^{*}$, that is, a collection of pairwise disjoint $s$-$t$ cuts, then we can clearly see that an $s$-$t$ path must intersect each cut in the matching, so

maximum size of a matching $\leq$ minimum length of an $s$-$t$ path.

Fulkerson observed that this inequality is also an equality, so $(E,\mathcal{C}^{*})$ packs [Ful1968]. This is sometimes called the min-potential max-work theorem (or at least a special case thereof).

Both of these examples can be seen in a matroidal light. We add the edge $e=st$ to $G$. Call the resulting graph $G^{+}$, and consider $M(G^{+})$. Then $C$ is the edge-set of an $s$-$t$ path if and only if $C\cup e$ is a circuit of $M(G^{+})$, and $C^{*}$ is the edge-set of an $s$-$t$ cut if and only if $C^{*}\cup e$ is a cocircuit of $M(G^{+})$. From this we can deduce that if $M$ is a graphic or cographic matroid, with ground set $E$, and $e\in E$, then the set systems $(E-e,\{C-e\mid C\ \text{is a circuit of}\ M\ \text{and}\ e\in C\})$ and $(E-e,\{C^{*}-e\mid C^{*}\ \text{is a cocircuit of}\ M\ \text{and}\ e\in C^{*}\})$ both pack.

We can do more, and consider weighted versions of these problems. Let us illustrate by assuming that every edge, $x$, in $G$ is assigned a positive integer, $c_{x}$, the capacity of $x$. An $s$-$t$ flow is an assignment that gives, to each $s$-$t$ path, $P$, a value, $f_{P}$, from $\mathbb{R}^{+}\cup\{0\}$. We insist that, for every edge, $x$, the total $\sum f_{P}$ does not exceed $c_{x}$ (here the sum is taken over all $s$-$t$ paths that contain $x$). We can think of a flow as a movement of liquid through the network, from $s$ to $t$, in such a way that the total amount of liquid flowing through any edge does not exceed the capacity of that edge. The value of the flow is the total $\sum f_{P}$, summed over all $s$-$t$ paths. Clearly, if we cut a swath through the network, disconnecting $s$ and $t$, the volume of liquid that flows onto the floor will be no greater than the total capacity of the edges we have just cut. Put less floridly,

maximum value of an $s$-$t$ flow $\leq$ minimum total capacity of an $s$-$t$ cut.

The max-flow min-cut theorem says that this inequality is an equality for any choice of capacities. What is more, there is a flow meeting this bound that assigns an integer value to every $s$-$t$ path, so we can recover our earlier version of the theorem by assigning a capacity of $1$ to every edge.

This idea of weighting can also be translated into matroidal language. Let us say that $M$ is a matroid with ground set $E$, and $e$ is in $E$. Every element $x\in E-e$ is assigned a capacity, $c_{x}$, from $\mathbb{Z}^{+}$. A flow is an assignment that gives a non-negative real value, $f_{C}$, to each circuit, $C$, of $M$ that contains $e$. We insist that, for every element, $x\in E-e$, the total $\sum f_{C}$ does not exceed $c_{x}$ (the sum is taken over all circuits of $M$ that contain $e$ and $x$). The value of a flow is the sum $\sum f_{C}$ over all circuits that contain $e$. Exercise: prove that the following inequality holds.

maximum value of a flow $\leq$ min $\left\{\sum_{x\in C^{*}-e}c_{x}\right\}$

where the minimum is taken over all cocircuits, $C^{*}$, that contain $e$. What can we say about $M$ if this inequality is an equality for all choices of capacities? The least we can do is give it a name, so we follow Seymour, and say $M$ is $e$-flowing [Sey1981]. If $M$ is $e$-flowing for every choice of $e$, then $M$ is $1$-flowing. The max-flow min-cut and min-potential max-work theorems imply that graphic and cographic matroids are $1$-flowing, but are there other $1$-flowing matroids, and if so, can we characterise them? This characterisation is the subject of a beautiful open problem, due to Seymour, but that will have to wait for my next post.

[EFS1956] P. Elias, A. Feinstein, and C. Shannon, A note on the maximum flow through a network. IEEE Transactions on Information Theory, 2 (1956) 117-119.

[FF1956] L. R. Ford and D. R. Fulkerson, Maximal flow through a network. Canad. J. Math. 8 (1956) 399-404.

[Ful1968] D. R. Fulkerson, Networks, frames, blocking systems. 1968 Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) 303-334.

[Sey1977] P. D. Seymour, The matroids with the max-flow min-cut property. J. Combinatorial Theory Ser. B 23 (1977) 189-222.

[Sey1981] P. D. Seymour, Matroids and multicommodity flows. European J. Combin. 2 (1981) 257-290.

A few days ago I was talking about 37ACCMCC in Perth. It was a great conference, and we all had a good time. If my vivid and evocative prose made you feel bad about missing out, never fear. You can always go next year! 38ACCMCC will be held at my own university, Victoria University of Wellington. The dates are Monday 1 December 2014 to Friday 5 December 2014. Matroids will be represented by Stefan van Zwam, who will be familiar to readers of this blog, and also by James Oxley, senior matroid statesman, and author of a book you may have come across.

The website for the conference is only basic at the moment, but functionality will be added when registration and accommodation become available. Keep on checking back. Hope to see you in NZ!

I’ve been on the road: three Canadian provinces and six states (five American, one Australian) in the last two months. My body-clock has no idea what it should be set to, and this morning I found myself utterly befuddled when I woke up in my own bedroom for the first time in months — but the upside is that I’ve been to a couple of really enjoyable meetings.

Combinatorial Potlatch

The Combinatorial Potlatch is a British Columbian/Pacific North-West institution. The word Potlatch refers to a gift-giving festival practised by the indigenous inhabitants of the area, and it was chosen to reflect the informal and hospitable nature of the workshop. I really like the way the meeting is run: it lasts only one day, there are only two or three speakers, and the day ends in the pub. Nobody speaks more than once in the series, ensuring that new people to the area are given a chance to participate. Judging by this year’s meeting, there is also an emphasis on inviting early-career mathematicians. In fact I had the slightly unsettling experience of being the oldest of the speakers: the first time this has happened to me, but probably not the last (if I can be presumptuous enough to expect further invitations).

In its recent incarnation, the Potlatch is organised by Nancy Neudauer and Rob Beezer, both of whom I know from a short course on matroid theory that Nancy ran during the 2011 joint meeting of the AMS and MAA. Every year a university from the region is tapped to host the meeting, and in 2013 it was the turn of Victoria University, the namesake of my own institution. The name of this Victoria is slightly more obvious, as it resides in the town of Victoria, provincial capital of British Columbia, and largest urban area on Vancouver Island. I had been in Vancouver immediately before the meeting, so I caught the ferry, which dodges islands in the Juan De Fuca Strait.

The island is also beautiful. While I was there I got to see some spawning salmon:

Of course, you don’t get to spawn without breaking some fish:

All part of life’s cycle, but it does make for a fairly pungent atmosphere.

I enjoyed the two talks that I got to see at the Potlatch. Richard Hoshino gave an interesting and personal talk about some of his career choices; in particular, his decision to emphasise education and real-world optimisation over pure research that is unlikely to be appreciated or noticed by more than a handful. Speaking for myself, it doesn’t bother me too much that my research will only ever be read by specialists. I think it’s legitimate for artists and pure mathematicians alike to gain satisfaction from doing the best work they can, while letting the audience take care of itself — the number of people who appreciate a piece of work isn’t necessarily the best indication of its quality anyway. But I certainly understand that not everyone feels as I do.

Jérémie Lumbroso gave an attractive talk on an idea that I hadn’t encountered before: if we have a generating function that enumerates a class of combinatorial objects, then we can use that generating function to construct a parameterised random algorithm that will select one of those objects. The choice of parameter will influence the size of the object chosen by the algorithm. Therefore, if we want to randomly select a rooted binary tree embedded in the plane with 20 vertices (say), then we adjust our parameter so that the algorithm will deliver a tree of the right size with reasonable probability, and we let it run until it produces an output with 20 vertices. This process chooses trees of 20 vertices with uniform probability. Jérémie showed us the code that he used to implement the algorithm, and it was remarkably simple: just a couple of lines of Mathematica code.

37ACCMCC

Soon after the Potlatch, it was time for me to head to Perth for the 37th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. Matroidunion.org’s own Irene Pivotto was a member of the organising committee, and Gordon Royle from SymOmega lead the committee. It was an extremely well-run meeting; so much so, in fact, that you can only feel sorry for the organiser of the 38th conference, given the high standards that he or she will have to live up to. (Expect to see more posts about 38ACCMCC sometime soon.)

I enjoyed many talks at the ACCMCC, so I will mention only the ones with significant amounts of matroid content. Nick Brettell spoke about an algorithm for constructing a $k$-tree of a matroid; Ben Clark talked about a project that myself and Stefan are involved in: the attempt to find excluded minors for the matroids representable over the partial field $\mathbb{H}_{5}$; Rong Chen talked about an inductive connectivity theorem for $k$-coherent matroids; Darryl Funk described work on the excluded minors for the class of frame matroids; Songbao Mo talked about a polymatroidal characterisation of abstract connectivity functions; Peter Nelson’s presentation covered some of the same material as his most recent post; Irene Pivotto spoke about some work she has done with Rong on a class of matroids arising from bias graphs; Michael Welsh described work on a conjecture of Steven Archer on maximum-sized golden-mean matroids. I think that covers everyone, so apologies if I have missed anyone.

The talks I gave at the two conferences were basically isomorphic (so apologies to the two people who were in the audience for both). In the first half I introduced matroids, and talked about excluded-minor characterizations, both exisiting and those still in progress. The second half was dedicated to work I have been doing with Mike Newman and Geoff Whittle on the impossibility of using matroid axioms to capture representability. Here are my slides.

Postscript

Attending these conferences made me think again about a small peeve of mine. I can’t understand the practice of abbreviating one’s own name to an initial when listing the authors of a theorem. You will no doubt know what I mean:

Theorem (M., Newman, Whittle — 2013)

instead of

Theorem (Mayhew, Newman, Whittle — 2013).

Can anyone tell me why we do this? It makes no sense to me. Slides usually have enough room to list names in full, so it can’t be a space constraint. Perhaps it comes from some sense of humility, as if we don’t want to lay too much of a claim to our own work lest we appear immodest? If that’s the case, then we seem to be saying that writing one’s own name above a theorem that we helped prove is an unbearable act of self-aggrandisement, and I can’t agree with that. I think it’s probably more likely that the custom just started years ago, and now people do it because it is what everyone does. But that’s not a good enough reason to continue a tradition. Unless somebody gives a masterful argument in favour of the practice in the comments, then I am going to write my own name in full on my slides, and I think others should do the same.