An elementary obstruction to same-ground-set matroid-rank approximation
Read the paper (PDF) · Download PDF · Supporting ZIP · Zenodo record
Plain-English explanation · Read on this page · Collaboration
Abstract
We give a self-contained elementary obstruction to the displayed formulation of Végh’s matroid-rank approximation question. A constant is interpreted conventionally as independent of the finite ground-set size; the source does not separately print that quantifier. For normalized nonnegative monotone submodular functions, approximation is by one ordinary unscaled matroid rank on the same ground set, with both comparisons r/α ≤ f ≤ αr. The classical function f(S) = √|S| forces α ≥ n^(1/6), and its exact optimum over all matroids is min over integers 1 ≤ R ≤ n of max{√R, √n/R}. A rational cardinality family on m² elements forces α² + α ≥ m. The functions and their uniform-rank decompositions are classical. Historical attribution of the exact one-rank argument remains unresolved in the bounded source review; no novelty or priority claim is made.
The idea in plain English
A submodular function describes diminishing returns: adding an item gives less extra value when more items are already present. A matroid rank counts the largest independent selection inside a set of items. This note asks how closely one such rank can track a submodular function.
For the two-sided formulation printed in Végh’s question, no fixed approximation factor works as the number of items grows. The note makes the conventional size-independent meaning of “constant” explicit; the source does not separately print that quantifier.
The precise result
Let f be nonnegative, monotone and submodular on a finite ground set V, with f(∅) = 0 and f({i}) = 1. The approximant is one ordinary, unscaled matroid rank r on that same V. Both inequalities r(S)/α ≤ f(S) ≤ αr(S) must hold for every subset S.
For f(S) = √|S| on n elements, every such rank requires α ≥ n^(1/6). The exact best factor for this family is min over integers 1 ≤ R ≤ n of max{√R, √n/R}. A uniform matroid attains the bound at each total rank R. When n = m³, the optimum is √m.
A rational family gives a stronger lower bound on a different collection of inputs. On m² elements, put g(∅) = 0 and g(S) = 1 + (|S| − 1)/m for nonempty S. Every admissible factor obeys α² + α ≥ m, and hence α ≥ (√(1 + 4m) − 1)/2.
Why the result holds
Positive singleton values rule out matroid loops. If the matroid has total rank R, choose a basis of size R. For the square-root function, the lower comparison at that basis forces α ≥ √R. The upper comparison at the full ground set forces α ≥ √n/R. These two requirements cannot stay bounded as n grows.
The rational family uses the same basis and full-set tests. Its values are a nonnegative combination of rank-one and free uniform ranks. The obstruction concerns compressing those values into one ordinary rank on the original ground set.
Scope and limitations
The exact optimization formula concerns the square-root family. The note does not determine the best worst-case exponent over all normalized submodular functions.
The conclusion depends on using one ordinary unscaled rank on the same ground set. Scaled or weighted ranks, sums of ranks, and matroids on an expanded set are different approximation classes. No query-complexity lower bound is claimed.
The note addresses Végh’s literal displayed two-sided formulation under the stated conventional quantifier. It does not establish a different intended formulation, historical firstness, or current worldwide open status.
Background and prior work
- The contribution in Oberwolfach Report 53/2021, printed p. 2946, supplies the same-ground-set rank question and its two-sided display. Végh, Approximating submodular functions by matroid rank functions
- Proposition 1 presents classical concave-cardinality submodularity and credits Lovász. The note proves the needed property directly; it makes no new-function claim. Balcan–Harvey, Submodular Functions: Learnability, Structure, and Optimization
- Appendix D gives the prior uniform-rank decomposition. The note supplies the direct finite-difference coefficients, correcting the displayed coefficient and index slips in Lemma D.1. Devanur–Dughmi–Schwartz–Sharma–Singh, On the Approximation of Submodular Functions
- Their polynomial-query problem and root-linear approximants differ from the existential approximation by one ordinary rank considered here. Goemans–Harvey–Iwata–Mirrokni, Approximating Submodular Functions Everywhere
- The classical copied-element construction is credited there to Helgason. It uses an expanded ground set. Original Lovász and Helgason source bodies were not independently inspected for this note. Schrijver, Combinatorial Optimization, §44.6b
Status and AI use
Unrefereed preprint. AI tools assisted in preparing and checking this paper. Independent human review is welcome.
Read the paper
Open the published PDF · Download PDF · Original PDF on Zenodo
Supporting materials
Download pr1047_supportkit_v1.0.zip · Original supporting ZIP on Zenodo
Collaborate on this result
I would welcome an independent review of the optimum for square-root cardinality and of the formulation printed in Végh’s workshop report. Authorship would reflect substantive contributions to the research or manuscript.
Cite this paper
Kriebel, Alec (2026). An elementary obstruction to same-ground-set matroid-rank approximation. Version 1.0. Zenodo. 10.5281/zenodo.23430660.
Licensing
The deposited work is available under Creative Commons Attribution 4.0.