Submodular and strongly submodular functions and diversities

Abstract

Submodular functions and their close relatives play a key role in combinatorial optimization, decision theory and potential theory. Part of their importance and usefulness stems from the connections with convex functions and polytopes. Here we explore connections between these functions and metric theory, with the bridge provided by diversities, a recently developed generalization of metric spaces to (finite) sets rather than just pairs. Both submodular functions and strongly submodular functions correspond to natural classes of diversities. Submodular diversities, as we define them here, are essentially non-decreasing, intersecting submodular functions which vanish on singletons. We prove new geometric embedding results for these diversities. In particular we show that submodular, strongly submodular, and XOS functions can be represented by the generalized circumradius, a set function in convex analysis equal to the amount a given convex body needs to be stretched to cover a set of points.

Disclosure

“δ (1) ), . . . , (X ∪ {x}, δ (m) ) so that by Proposition 17, f = δx = max{δx } is XOS. Acknowledgements PT was supported by a Natural Sciences and Engineering Research Council (Canada) Discovery Grant (RGPIN-2025-04769). Claude and ChatGPT were used to help identify relevant literature, to test conjec- tures, to help check proofs, to suggest ideas for proofs (both fruitful and not) and to format the bibliography. All text and proofs were written by the authors. References”

PDF page 27

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:10:25.182893Z

Structural counts