← Back to arXiv
arXivCombinatoricsarXiv:2608.17130

Caged Retractions of Polymatroids

The paper develops a systematic theory for a mathematical operation called "caged retraction" applied to objects known as polymatroids. A polymatroid is a generalization of a matroid, which is itself an abstract structure that captures the notion of independence, like linear independence of vectors or acyclicity in graphs. A polymatroid allows elements to be "used multiple times" up to a capacity limit, rather than just once. A "cage" is essentially a set of upper bounds on how much each element can be used. The caged retraction takes a polymatroid and squeezes it into a smaller, bounded version by projecting its building blocks (called bases) into the allowed region and keeping only the largest ones that fit. The authors show this geometric projection process is equivalent to a clean algebraic formula involving rank functions, which are the standard way to describe these structures.

The heart of the paper is showing that caged retractions and the natural inclusion of bounded polymatroids into all polymatroids form a "Galois connection." This is a precise mathematical relationship saying that the two operations are inverses of each other in a specific structural sense, similar to how closing and opening operations work in topology or logic. This Galois connection is organized around something called the weak-map order, a natural way to compare polymatroids by saying one is "smaller" than another if its rank function is pointwise smaller. Having this Galois connection is powerful because it means the retraction behaves very predictably and respects the structure of the whole collection of polymatroids.

Building on this foundation, the authors derive bounded or caged versions of several classical results in matroid and polymatroid theory, including theorems about combining polymatroids (union), decomposing them into disjoint pieces, and constructing new ones from bipartite graphs. When the cage is set to its simplest possible value, the results collapse back to the classical matroid theorems, confirming consistency with the existing literature. The paper also investigates how caged retractions interact with two more advanced topics: Lorentzian polynomials, which are polynomials with special positivity and log-concavity properties important in combinatorics, and algebraic representations over certain generalized number systems called near-idempotent tracts. In both cases, the retraction is shown to preserve the relevant properties, meaning the bounded version inherits the good behavior of the original.

Read original →