There is a wonderful matroidal proof of the Tutte-Berge formula for the maximum size of a matching [1]. Today we discuss another min-max theorem [2] which has a similar matroidal proof. Tantalizingly, the two theorems do not (yet?!) have a common generalization. This theorem was just posted to arXiv by yours truly – it arose from joint work with Jim Geelen and Paul Wollan on vertex-minors, which I’ll have to discuss later!
Matchings and the proof strategy
First we outline the proof in the case of matchings. It’s more convenient to work in the “dual setting”. So, given a graph $G$, we write $\textrm{defect}(G)$ for the minimum number of vertices left uncovered by a matching. So, where $\nu(G)$ denotes the size of a maximum matching of $G$, we have $\textrm{defect}(G) = |V(G)|-2\nu(G)$.
We write $\textrm{odd}(G)$ for the number of components of a graph $G$ with an odd number of vertices. Note that for any $X \subseteq V(G)$, we have $\textrm{defect}(G) \ge \textrm{odd}(G-X)-|X|$, since all but $|X|$ of the odd components must contribute towards the defect. The min-max theorem says that in fact equality can be achieved.
Theorem (Tutte-Berge Formula): For any graph $G$,
$$\textrm{defect}(G) = \max_{X \subseteq V(G)} \left(\textrm{odd}(G-X)-|X|\right).$$
Here is a rough roadmap on using matroids to prove min-max theorems like this one. This strategy is due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour [1], who use it to prove a theorem which does generalize the Tutte-Berge Formula.
- Find a matroid whose rank equals the defect. In this case, sets which are of the form $V(G)\setminus V(M)$ for some maximum matching $M$ form the bases of a matroid. This is the dual of the well-known matching matroid.
- Reduce to the case that the matroid is loopless. In this case, no vertex-minimum counterexample can contain a loop vertex $v$. Otherwise, we would have $\textrm{defect}(G)<\textrm{defect}(G-v)$, and so we could add $v$ to the set $X$ obtained for $G-v$ to get a “good set” for $G$ and thus a contradiction.
- Use transitivity of parallel pairs to complete the proof. In this case, each component of $G$ has rank $1$ by transitivity of parallel pairs and the fact that for each edge $uv \in E(G)$, the vertices $u$ and $v$ are parallel (that is, there is no maximum matching which leaves both $u$ and $v$ uncovered). So we can take $X = \emptyset$ since each component is odd and contributes $1$ towards the defect.
The new min-max theorem
The new min-max theorem is for “rooted Eulerian signed graphs”, which is a bit of a mouthful. The point is that we have a (multi-)graph $G$ which is Eulerian (connected and with every vertex of even degree), a specified vertex $b \in V(G)$ called the root, and a specified set of edges $S \subseteq E(G)$ called the signature. It is helpful to think of the edges in $S$ as being “odd” and the other edges as being “even”.
Since $G$ is Eulerian, it is possible to partition its edge-set into exactly $\textrm{degree}(b)/2$ many parts, each of which is the edge-set of a trail that begins and ends at $b$. We call such a trail a $b$-trail, and we say that it is odd if it contains an odd number of edges from $S$. We are interested in the following maximization problem.
Problem: What is the maximum number of odd trails in a collection of $\textrm{degree}(b)/2$ many $b$-trails which partitions $E(G)$?
We call this the flooding number and denote it by $\widetilde{\nu}$. The min-max theorem for $\widetilde{\nu}$ is somewhat technical to state, so we refer the reader to [2]. However, here is an example of our version of an “odd component”. The thick red edges denote the edges in $S$. Look at the parity of $|S|$ and notice that $\widetilde{\nu}$ is $3$ rather than $\textrm{degree}(b)/2$, which is $4$.
The general outline of the proof is exactly the same as before. We define a matroid of rank $\textrm{degree}(b)/2-\widetilde{\nu}$; this quantity is our analog of the “defect”. We then reduce to the case that this matroid is loopless and use transitivity of parallel pairs to get “odd components”. These two proofs are too similar for coincidence! So, the question is:
Question: Is there a construction which reduces the matching number $\nu$ to the flooding number $\widetilde{\nu}$, or vice-versa?
[1] Section 3 of “Packing Non-Zero A-Paths In Group-Labelled Graphs” by Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour, Combinatorica, 2006.
[2] “Decomposing a signed graph into rooted circuits” by McCarty, arXiv:2308.01456, 2023.
