Many different areas of combinatorics and optimization are interested in objects that admit a rough duality between packing and covering. A classic example is that every bipartite graph either has a matching of size $k$, or has a set of at most $k-1$ vertices which “hit” every edge (i.e. a vertex cover of size $k$; this is Kőnig’s theorem).

Another example where only a rough duality is possible was proven by Erdős and Pósa. They showed that every graph either has $k$ cycles that are pairwise vertex-disjoint, or has a set of $\mathcal{O}(k \log{k})$ many vertices which hit every cycle (i.e. a set of vertices whose deletion yields a forest). Note that this is not an exclusive “or”; some graphs have both. But any graph with a hitting set of size $r$ has at most $r$ pairwise vertex-disjoint cycles.

In general, for any problem which is suitable to study within this framework, the maximum size of a packing should be at most the minimum size of a covering (or at least roughly so). This is typically the easy direction (I would love to hear in the comments about any natural examples where it is not the easy direction!). If the other direction is also (roughly) satisfied, then the set of objects is said to have the Erdős-Pósa property, meaning that if there is no packing of size $k$, then there is a covering of size at most $f(k)$, for some function $f$.

Related Topics

I have discussed examples of exact combinatorial min-max theorems before, and how these problems often have an underlying matroid. One of the most general theorems about which hypergraphs admit a rough duality between packing and covering is due to Ding, Seymour, and Winkler and generalizes well-known results on VC-dimension. Other key terms are LP-rounding, total unimodularity, clutters, … . Erdős-Pósa problems are very actively researched; see for instance the recent workshop in Poland. Geelen and Kabell also proved a different matroidal Erdős-Pósa property.

Binary Matroids

For binary matroids there is a somewhat different notion of covering. It is convenient to think of a graph with a “small vertex cover” as being “close to” a graph whose largest packing has size zero. So instead of deleting a small set of vertices, we add a low-rank matrix. Formally, consider a binary matroid $M$ which is represented by the columns of an $n \times m$ binary matrix $A$. A rank-$k$ perturbation of $M$ is then any matroid $M’$ which can be represented by the columns of $A+B$, where $B$ is an $n \times m$ binary matrix of rank at most $k$. We perform addition over the binary field.

Campbell, Gollin, Hatzel, Kwon, Oum, Wiederrecht, and I proved the following theorem. Given a graph $H$, we write $M(H)$ for its cycle matroid.

Theorem
For any planar graph $H$, there is a function $f_H$ so that for every integer $k$, every binary matroid either has the cycle matroid of $k$ vertex-disjoint copies of $H$ as a minor, or has a rank-$f_H(k)$ perturbation which does not have $M(H)$ as a minor.

This really is an Erdős-Pósa property in the sense that it gives a rough min-max theorem for packing $M(H)$ minors. When $H$ is a cycle and the matroid is graphic, one should roughly think of the theorem as saying the following. Note that this is a conjecture; it does NOT just follow from our theorem. This is because, informally, our perturbations are allowed to leave the graphic world, and the ones below are not.

Conjecture
There exists a function $f$ so that for any integer $k$, every multigraph either 1) has a minor with $k$ different blocks, each of which is a cycle, or 2) can be turned into a forest by performing the following operations at most $f(k)$ times:

• identify two vertices $u$ and $v$ into a single vertex. This operation does not change the number of edges. So for instance if $u$ and $v$ were adjacent originally, there will be a loop at the new vertex after identification.
• split a vertex $v$ into two vertices $v_1$ and $v_2$. This operation is the opposite of identification.

Thank you to Mathieu Rundström for correcting the previous wrong version of the conjecture!