arXiv:2605.23291 · v2

Maximum Probability of Independence in Transitive Matroids

首次提交 2026-05-22 15:03

版本更新 2026-11-10 18:58

雷达观测 2026-11-11 13:08

摘要

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$.

作者备注：15 pages