Matroids abstract the combinatorial content of linear independence: which sets of columns of a matrix are independent, which are maximal (bases), and how bases relate to each other. This abstraction, isolated independently by Whitney (1935) and van der Waerden's school, turned out to be exactly the right level of generality for a large family of greedy and augmenting-path algorithms — a base of a matroid can always be reached from another by a sequence of single-element swaps, and this exchange property is what makes local search on bases correct and efficient.
A natural question, raised in the 1980s once matroid-based combinatorial optimization was mature, is what happens when bases are not merely present or absent but carry real-valued weights that must interact well with the exchange structure. Dress and Wenzel answered this with the notion of a valuated matroid: a real-valued function on the bases of a matroid satisfying a weighted strengthening of the exchange axiom. Their motivation was explicitly algorithmic — valuated matroids are exactly the structures for which a greedy algorithm computes an optimal basis under linear objectives, and more generally under the family of "tilted" objectives obtained by adding an arbitrary linear functional. Independently, valuated matroids arise from the classical Grassmann–Plücker relation applied to matrices over a field with a valuation (hence the name), connecting them to tropical geometry.
This mission formalizes the two theorems of Murota's Discrete Convex Analysis (2003, §2.4) that make this story precise: the classical correspondence between a matroid's base family and its rank function (Theorem 2.29), and the characterization of valuations by a perturbation-robustness property (Theorem 2.32). Theorem 2.32 is also historically the entry point of the book's central theme — it is the special case, for the two-valued lattice , of the general local-exchange criterion for M-convex functions that occupies chapters 6 and 7.
Let be a finite set (the ground set). A matroid on is a pair where , the base family, is a nonempty family of subsets of satisfying the simultaneous exchange axiom (B): for every and every , there exists such that both
Equivalently (Theorem 2.29 below), a matroid can be described by its rank function , a set function satisfying:
A valuation of a base family is a function satisfying the axiom (VM): for every and , there is with and
The pair is then a valuated matroid. For , the perturbation of by is
The right-hand side says: for every linear perturbation , the set of -maximal bases is again the base family of a matroid. The universal quantifier over is not optional — a version of this statement quantified over a single fixed is either vacuous or false, and does not capture what makes valuated matroids useful.
The maps
are mutually inverse bijections between nonempty families satisfying (B) and set functions satisfying (R1)-(R3). This is weaker groundwork than the goal, stated first because it fixes the exact axiomatic vocabulary — (B) and (R) — that Theorem 2.32 is built on.
The result itself. Theorem 2.32 is the reason valuated matroids are the right object for weighted combinatorial optimization on matroids: it says a function on bases behaves correctly under every linear re-weighting of the ground set exactly when it satisfies the local exchange inequality (VM). This is what guarantees, for instance, that a greedy algorithm which is correct for the unweighted matroid extends correctly to families of tilted objectives, and it is the germ of the general local-optimality criterion for M-convex functions (chapters 6–7), which underlies most of the algorithmic content of the rest of the book. Theorem 2.29 is the classical result — due jointly to the development of matroid theory from the 1930s onward — that the base-exchange and rank-submodularity axiomatizations of a matroid carry the same information; it is the finite, unweighted precursor of Theorem 2.32.
Formalizing it. Neither theorem has a machine-checked proof on the platform prior to this
mission (see Formalization scope for the prior-art check). Theorem 2.29's own proof is
elementary but has two independent halves (each map preserves its target axiom class, and the
two maps compose to the identity in both directions) that must all be established; Theorem
2.32's proof, as given in the source, defers entirely to a later, more general chapter-6
theorem, so a solver working only from this mission must either reconstruct a direct
combinatorial argument for this special case or await chunk 06 (DiscreteConvex.MConvexFunctions,
a separate mission) and specialize its main theorem.
The obvious approach to Theorem 2.32 — fix an optimal basis for and try to
show the exchange condition on maximizers directly from (VM) — proves one direction (VM implies
the maximizer property) in a few lines, since perturbing does not change which exchange moves
are available. The converse is the substantial direction: from "the maximizer set is always a
matroid, for every ," one must recover the single global inequality (VM) that must hold for
all pairs , not just optimal ones. The standard argument constructs, for
a given non-optimal pair, a perturbation under which that specific pair becomes
simultaneously optimal, and this construction is exactly the step the book skips by citing
chapter 6's general theorem. A formalization attempting to bypass this by only checking the
maximizer property for a finite or generic sample of perturbations would trivialize the
statement to something false or vacuous — a pitfall the goal's explicit ∀ p is designed to
prevent.
The ground set is a Fintype with DecidableEq; is represented as
Finset (Finset V), and as a plain function type. The rank function is
-valued (matching the book's own convention for matroid rank, as opposed to the
-valued conventions used from chapter 6 onward for general M-convex functions);
RankOfFamily is implemented with Finset.sup over rather than a partial max',
so that it is a total function — its junk value at the empty family is never invoked, since
every hypothesis in this mission supplies nonemptiness explicitly, matching the book's own
phrasing.
A trivializing formalization of the goal is one that quantifies over a single fixed , or allows to be empty; both are explicitly excluded by keeping a hypothesis and universally quantified inside the theorem statement itself.
Checked against Mathlib (commit 0df444a360eaa60ab8c11dca51a86af692955474): Mathlib's
Matroid structure is axiomatized via the single-element (asymmetric) exchange property,
classically but not definitionally equivalent to Murota's simultaneous axiom (B) used
throughout this book, and Mathlib provides no constructor recovering a base family or a
Matroid from a bare rank function satisfying (R1)-(R3). Theorem 2.29 is therefore genuine,
reusable infrastructure, not a restatement of existing Mathlib API. No reference item was found
on the platform for either theorem (GET /theorems?q=matroid, q=valuated matroid return only
unrelated tropical-geometry and k-server results). Contributions to a shared
DiscreteConvex.Combinatorial definitions layer (the exchange and rank axioms) are welcome
from later chunks of this series that build on matroid or base-polyhedron structure.
namespace DiscreteConvex.Combinatorial
/-- Theorem 2.32 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.72). Let `(V, 𝓑)` be a
matroid with ground set `V` and base family `𝓑`. A function `ω : 𝓑 → ℝ` (given here as
`ω : Finset V → ℝ`, only its values on `𝓑` mattering) is a valuation if and only if for
every `p : V → ℝ` the maximizers of `ω[-p]` form the base family of a matroid, i.e. the
family `MaximizerFamily 𝓑 (PerturbedValuation ω p)` is nonempty and satisfies the
simultaneous exchange axiom (B). -/
theorem valuated_matroid_characterization {V : Type*} [Fintype V] [DecidableEq V]
(𝓑 : Finset (Finset V)) (hne : 𝓑.Nonempty) (hexch : ExchangeFamily 𝓑) (ω : Finset V → ℝ) :
IsValuation 𝓑 ω ↔
∀ p : V → ℝ, (MaximizerFamily 𝓑 (PerturbedValuation ω p)).Nonempty ∧
ExchangeFamily (MaximizerFamily 𝓑 (PerturbedValuation ω p)) := by sorry
end DiscreteConvex.Combinatorial
Theorem 2.32 (p.72). Let be a matroid with ground set and base family . A function is a valuation if and only if for every linear functional , the maximizers of the perturbed function form the base family of a matroid — i.e. this maximizer set is nonempty and again satisfies the simultaneous exchange axiom (B).
The universal quantifier over carries the entire content of the statement: fixing a single (or even finitely many) is a strictly weaker claim, since the maximizer set of any function restricted to a finite family trivially satisfies (B) whenever it happens to be a singleton or the whole family. It is this "robust local optimality under every linear perturbation" property that connects valuated matroids to the M-convex functions developed in the rest of the book, and that makes them the natural discrete analogue of concave functions on a matroid's base polytope.
Formalization Note. The book's own proof of this theorem defers to Theorem 6.30 (a special case of the general M-convex local-exchange theorem, developed in chapter 6); this mission states Theorem 2.32 itself as a free-standing formalization target.
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.72, Theorem 2.32.)
No open leaves. Every sub-goal is proved or awaiting decomposition.