Maximum Probability of Independence in Transitive Matroids
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913155058237440 |
|---|---|
| author | Kovačević, Mladen |
| author_facet | Kovačević, Mladen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23291 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximum Probability of Independence in Transitive Matroids Kovačević, Mladen Combinatorics Discrete Mathematics Probability 05B35, 05B25, 15B52, 60C05 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. |
| title | Maximum Probability of Independence in Transitive Matroids |
| topic | Combinatorics Discrete Mathematics Probability 05B35, 05B25, 15B52, 60C05 |
| url | https://arxiv.org/abs/2605.23291 |