Alec Kriebel

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

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.

Contact Alec

Cite this paper

Kriebel, Alec (2026). An elementary obstruction to same-ground-set matroid-rank approximation. Version 1.0. Zenodo. 10.5281/zenodo.23430660.

Download BibTeX

Licensing

The deposited work is available under Creative Commons Attribution 4.0.