Maximum Probability of Independence in Transitive Matroids

Mladen Kova\v{c}evi\'c

arxiv: 2605.23291 · v1 · pith:O2UXKD4Rnew · submitted 2026-05-22 · 🧮 math.CO · cs.DM· math.PR

Maximum Probability of Independence in Transitive Matroids

Mladen Kova\v{c}evi\'c This is my paper

Pith reviewed 2026-05-25 04:18 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.PR MSC 05B35

keywords matroidsindependence probabilityquasi-concave functionsuniform distributiontransitive automorphism groupfinite fieldsfull row rankprojective space

0 comments

The pith

In matroids whose automorphisms treat every element the same, the probability of sampling a distinct independent set is maximized exactly when the sampling distribution is uniform.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that if a matroid's symmetries map any element to any other, then the function that assigns to each probability vector p the chance of drawing K distinct elements forming an independent set is quasi-concave and reaches its global maximum at the uniform vector. The same conclusion applies to the probability that K random rows drawn from projective space over a finite field are linearly independent. The transitivity assumption is used to show that any deviation from uniformity cannot increase the probability.

Core claim

Let M be a matroid on finite ground set E whose automorphism group acts transitively on E. If X1,...,XK are drawn independently according to a distribution p on E, then the probability that the Xi are distinct and that {X1,...,XK} is independent in M is a quasi-concave function of p that attains its maximum when p is the uniform distribution on E. The same statement holds for the probability that K independently chosen nonzero projective row vectors over a finite field yield a matrix of full row rank; in that special case the maximizer is moreover unique and the objective is globally quadratically stable.

What carries the argument

Quasi-concavity of the map p to the probability that K independent samples are distinct and independent, established via the transitive action of the automorphism group.

If this is right

Uniform sampling is optimal for maximizing the chance of obtaining an independent set of prescribed size under any transitive matroid.
For random matrices over a finite field the uniform distribution on projective space maximizes the probability of full row rank.
Uniqueness of the maximizer and global quadratic stability hold for the matrix case but can fail for general transitive matroids.
Any local maximum of the probability function must occur at the uniform distribution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result supplies a symmetry-based reason that uniform distributions are preferred in randomized constructions involving matroids.
The same quasi-concavity argument may apply to other combinatorial structures whose automorphism groups act transitively.
The matrix corollary gives a concrete criterion for choosing row distributions when designing random linear codes or matrices with prescribed rank properties.

Load-bearing premise

The automorphism group of the matroid must act transitively on the ground set.

What would settle it

An explicit non-uniform distribution p on the ground set of any transitive matroid together with a direct computation showing that the independence probability at p exceeds the value at the uniform distribution.

read the original abstract

Let $M$ be a matroid on a finite ground set $E$, and suppose that the automorphism group of $M$ acts transitively on $E$. We show the following: if $X_1,\ldots,X_K$ are sampled independently from a distribution $p$ on $E$, then the probability that the samples are distinct and that $\{X_1,\ldots,X_K\}$ is an independent set in $M$ is quasi-concave in $p$ and maximized when $p$ is uniform. As a corollary, for a random $K\times N$ matrix over a finite field whose rows are sampled independently from an arbitrary distribution on nonzero projective row classes, the uniform distribution on projective space maximizes the probability of full row rank. In this particular case we also establish the uniqueness of the maximizer and global quadratic stability, while a simple example illustrates that uniqueness and stability need not hold for arbitrary transitive matroids.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows that for transitive matroids the independence probability is quasi-concave in the sampling distribution and therefore maximized at uniform, via a symmetry argument that also yields a clean corollary for random matrices over finite fields.

read the letter

The main takeaway is that when Aut(M) acts transitively on the ground set, the function f(p) giving the probability that K independent draws are distinct and independent in M is quasi-concave on the simplex and attains its maximum at the uniform distribution. The argument rests on group invariance of f together with transitivity forcing any orbit average to uniform; quasi-concavity then pins down the maximizer without further work. The paper separates this from the stronger claims of uniqueness and quadratic stability, which it proves only for the linear matroid case and disproves in general with an explicit counter-example. That separation is useful and keeps the claims proportionate. The corollary on K by N matrices over finite fields follows directly and supplies a concrete optimization statement for row-rank probability. The logic is self-contained, uses no free parameters or fitted quantities, and the citation pattern is light and appropriate for a focused result in matroid theory. The limitation to transitive matroids is stated up front and not overstated. Outside that class the claim does not apply, but the paper does not pretend otherwise. A reader working on extremal problems in matroids or on random matrices over finite fields will find the explicit maximizer and the counter-example directly usable. The result is narrow in scope but the reasoning is tight and the distinction between the general and linear cases is handled cleanly. It deserves a serious referee.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that if the automorphism group of a matroid M acts transitively on its ground set E, then the probability that K i.i.d. samples from a distribution p on E are distinct and form an independent set is quasi-concave in p and therefore maximized at the uniform distribution. A corollary states that the uniform distribution on projective space maximizes the probability of full row rank for a random K×N matrix over a finite field whose rows are drawn independently from an arbitrary distribution on nonzero projective classes. The paper further establishes uniqueness of the maximizer and global quadratic stability in the linear-matroid case, while supplying an explicit counter-example showing that uniqueness and stability fail for arbitrary transitive matroids.

Significance. If the central claim holds, the result supplies a symmetry-based argument that identifies the uniform distribution as optimal for a natural independence probability on any transitive matroid. The clean separation between the quasi-concavity-plus-maximization statement (which follows from invariance and transitivity) and the stronger uniqueness/stability properties (which hold only for linear matroids) is a positive feature, as is the explicit counter-example that delineates the scope. The corollary for finite-field matrices is of direct interest in probabilistic combinatorics and random linear algebra.

minor comments (2)

[Abstract] Abstract, first sentence: the phrase 'the probability that the samples are distinct and that {X1,…,XK} is an independent set' should be given an explicit functional notation f(p) at the first appearance so that later references to quasi-concavity are immediately anchored.
[Abstract] The counter-example illustrating failure of uniqueness is mentioned only in the abstract; a brief pointer to its location in the body would help readers locate the concrete illustration of the distinction between linear and general transitive matroids.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper states a self-contained theorem: under the assumption that Aut(M) acts transitively on E, the function f(p) measuring the probability that K independent samples from p are distinct and form an independent set is quasi-concave on the simplex and attains its maximum at the uniform distribution. This follows directly from the group-invariance of f (which holds because automorphisms preserve independence) combined with transitivity (forcing the barycenter of orbits to be uniform) and the definition of quasi-concavity; no parameter fitting, self-referential definitions, or load-bearing self-citations appear in the derivation. The corollary for linear matroids and the counter-example for general transitive matroids are presented as separate, explicitly distinguished results. The derivation chain is therefore independent of its inputs and does not reduce by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of a matroid and the additional assumption of transitivity of the automorphism group; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)

standard math Standard axioms of matroid theory (independent-set axioms or equivalent)
Invoked implicitly by the use of the term 'matroid' and 'independent set'.

pith-pipeline@v0.9.0 · 5689 in / 1315 out tokens · 34532 ms · 2026-05-25T04:18:51.726754+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · 1 internal anchor

[1]

Anari, S

N. Anari, S. Oveis Gharan, and C. Vinzant, Log-concave polynomials I: entropy and a deter- ministic approximation algorithm for counting bases of matroids,Duke Math. J.170(2021), no. 16, 3459–3504

work page 2021
[2]

Bl¨ omer, R

J. Bl¨ omer, R. Karp, and E. Welzl, The rank of sparse random matrices over finite fields, Random Struct. Alg.10(1997), no. 4, 407–419

work page 1997
[3]

Br¨ and´ en and J

P. Br¨ and´ en and J. Huh, Lorentzian polynomials,Ann. of Math. (2)192(2020), no. 3, 821–891

work page 2020
[4]

Cooper, On the rank of random matrices,Random Struct

C. Cooper, On the rank of random matrices,Random Struct. Alg.16(2000), no. 2, 209–232

work page 2000
[5]

Cooper, On the distribution of rank of a random matrix over a finite field,Random Struct

C. Cooper, On the distribution of rank of a random matrix over a finite field,Random Struct. Alg.17(2000), no. 3–4, 197–212

work page 2000
[6]

Deli´ c and J

M. Deli´ c and J. Iveti´ c, On the maximum probability of full rank of random matrices over finite fields,Mathematics13(2025), no. 3, Article 540

work page 2025
[7]

Fulman, Random matrix theory over finite fields,Bull

J. Fulman, Random matrix theory over finite fields,Bull. Amer. Math. Soc. (N.S.)39(2002), no. 1, 51–85

work page 2002
[8]

Oxley,Matroid Theory, 2nd ed., Oxford University Press, 2011

J. Oxley,Matroid Theory, 2nd ed., Oxford University Press, 2011

work page 2011
[9]

On the rank of random matrices over finite fields

D. Salmond, A. Grant, I. Grivell, and T. Chan, On the rank of random matrices over finite fields, arXiv:1404.3250, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014

[1] [1]

Anari, S

N. Anari, S. Oveis Gharan, and C. Vinzant, Log-concave polynomials I: entropy and a deter- ministic approximation algorithm for counting bases of matroids,Duke Math. J.170(2021), no. 16, 3459–3504

work page 2021

[2] [2]

Bl¨ omer, R

J. Bl¨ omer, R. Karp, and E. Welzl, The rank of sparse random matrices over finite fields, Random Struct. Alg.10(1997), no. 4, 407–419

work page 1997

[3] [3]

Br¨ and´ en and J

P. Br¨ and´ en and J. Huh, Lorentzian polynomials,Ann. of Math. (2)192(2020), no. 3, 821–891

work page 2020

[4] [4]

Cooper, On the rank of random matrices,Random Struct

C. Cooper, On the rank of random matrices,Random Struct. Alg.16(2000), no. 2, 209–232

work page 2000

[5] [5]

Cooper, On the distribution of rank of a random matrix over a finite field,Random Struct

C. Cooper, On the distribution of rank of a random matrix over a finite field,Random Struct. Alg.17(2000), no. 3–4, 197–212

work page 2000

[6] [6]

Deli´ c and J

M. Deli´ c and J. Iveti´ c, On the maximum probability of full rank of random matrices over finite fields,Mathematics13(2025), no. 3, Article 540

work page 2025

[7] [7]

Fulman, Random matrix theory over finite fields,Bull

J. Fulman, Random matrix theory over finite fields,Bull. Amer. Math. Soc. (N.S.)39(2002), no. 1, 51–85

work page 2002

[8] [8]

Oxley,Matroid Theory, 2nd ed., Oxford University Press, 2011

J. Oxley,Matroid Theory, 2nd ed., Oxford University Press, 2011

work page 2011

[9] [9]

On the rank of random matrices over finite fields

D. Salmond, A. Grant, I. Grivell, and T. Chan, On the rank of random matrices over finite fields, arXiv:1404.3250, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014