Sharp proximity for group-labeled matroid bases

\(\)

Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We prove that, for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. This resolves the unweighted proximity conjecture for representable matroids over arbitrary fields, with no compatibility condition on the label group. The bound is sharp even for spanning trees. The proof combines column operations within label classes, induction through a hyperplane, and the classical unique-representation sumset inequality. For weighted proximity, we prove that a polynomial nonvanishing constraint of degree \(d\) admits an optimal feasible basis within \(d\) exchanges of every unconstrained optimum. For elementary abelian \(p\)-group labels and a representation in characteristic \(p\), this gives the exact worst-case weighted radius; for binary labels it is \(\lfloor\log_2(|F|+1)\rfloor\). We also give a sharp group-dependent bound for abelian \(p\)-groups, simultaneous-constraint consequences, and an extension to realizable valuated costs.

Article

Download

View PDF