The ACO Seminar (2025–2026)

Consider a family of subsets $F =\{F_i \subseteq T\}$ over a finite ground set $T$. A (unweighted) packing problem is asking what is the largest number of pairwise disjoint sets in $F$. In cases where $F$ has a nice enough polyhedral description, one may use tools such as linear programming duality and the theory of blocking polyhedra to derive min-max type relations. Some examples of this include Menger’s theorem, max-flow min-cut, etc. By relaxing integrality conditions on the coefficients of the packing, one can look for fractional packings or packings where we allow subtraction. Both directions lead to lattice theory.

In this talk, we consider two packing conjectures and their lattice theoretical relaxations: one in the setting of perfect matchings in a graph and another in the setting of strongly connected orientations in a digraph. While the two theories share many similarities in terms of polyhedral descriptions and structural properties, there are still certain distinctions leading to different lattice theoretical results. Based on joint works with Ahmad Abdi, Gerard Cornuejols, and Siyue Liu.