Discrete modulus in graphs and matroids: theory and algorithms

Abstract

This dissertation develops and extends the theory of discrete modulus for families of combinatorial objects in graphs, matroids, and hypergraphs. Discrete modulus is an optimization framework for studying a finite family of objects through their usage vectors on a common finite ground set. It assigns densities to the elements of the ground set and minimizes a convex energy subject to the requirement that every object in the family has total density at least one. A central theme of this dissertation is that the resulting optimizer often encodes much more than the solution to an optimization problem: it also determines structural invariants of the underlying combinatorial model. The first part of the dissertation studies modulus for the family of bases of a matroid. We prove that the optimal density of the base modulus problem, called the universal density, determines the strength, fractional arboricity, and principal partition of the matroid. We also recover Edmonds’s base packing and covering theorems from this perspective, characterize the Fulkerson blocker of the base family, obtain a minimal inequality description of the base dominant, and establish a duality between the base modulus of a matroid and that of its dual. The second part extends the theory to weighted matroids. In this setting, we introduce matroid reinforcement and matroid sparsification problems, which ask for minimum-cost ways to increase or decrease element weights so that the resulting weighted matroid becomes homogeneous. Here, homogeneous matroids are those that are balanced, in the sense that strength and fractional arboricity coincide. We express the relevant weighted invariants through the geometry of the base dominant and anti-dominant, reduce the optimization problems to polymatroid greedy instances, and obtain explicit algorithms in the graphic case. The third part studies matroid truncation and dual truncation. We derive explicit formulas expressing the universal density of each truncation in terms of the universal density of the original matroid. These formulas describe how strength, fractional arboricity, and the principal partition evolve across the truncation family. We also characterize the universal density of a weighted matroid as the unique minimizer of a Kullback–Leibler divergence over the convex hull of the base family. The final part carries the modulus framework to hypergraphs. Hypergraphic matroids generalize spanning trees to hypertrees, but a connected hypergraph need not contain a hypertree. To address this, we introduce the multi-tree family, whose members are multisets of hyperedges that span the vertex set as a hypertree. We show that the modulus of this family reveals the strength, fractional arboricity, and hierarchical decomposition of any connected hypergraph. We also prove a Fulkerson duality between the multi-tree family and a system of partition inequalities. Across these settings, the same phenomenon recurs: the optimal density arising from discrete modulus is not merely an optimizer of a convex program. It is a structural object that organizes packing, covering, density, duality, and decomposition phenomena in graphs, matroids, and hypergraphs.