no. 13 · Wednesday 11 November 2026
Maximum Probability of Independence in Transitive Matroids
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. For $2\le K\le\rank(M)$, we characterize all maximizers by uniform total mass on the parallel classes and, in particular, show that the maximizer is unique and has global quadratic stability when $M$ is simple. As a corollary, for a random $K\times N$ matrix over a finite field with i.i.d.\ rows, uniform sampling from the nonzero vectors maximizes the probability of full row rank. Finally, we show that uniform sampling maximizes $\Prob\big(\rank_M(X_1,\ldots,X_L)\ge r\big)$, and hence also $\E\rank_M(X_1,\ldots,X_L)$, for every $L, r$.
- comments
- 15 pages
- fields
- Combinatorics, Probability