Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2207.08116 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913649836163072 |
|---|---|
| author | Etkind, Mark Mordechai Lev, Nir |
| author_facet | Etkind, Mark Mordechai Lev, Nir |
| contents | An $n \times m$ array with nonnegative entries is called doubly stochastic if the sum of its entries at each row is $m$ and at each column is $n$. The set of all $n \times m$ doubly stochastic arrays is a convex polytope with finitely many extremal points. The main result of this paper characterizes the possible sizes of the supports of all extremal $n \times m$ doubly stochastic arrays. In particular we prove that the minimal size of the support of an $n \times m$ doubly stochastic array is $n + m - \gcd(n,m)$. Moreover, for $m=kn+1$ we also characterize the structure of the support of the extremal arrays. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_08116 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Support of extremal doubly stochastic arrays Etkind, Mark Mordechai Lev, Nir Combinatorics 05B20, 05C05, 15B51 An $n \times m$ array with nonnegative entries is called doubly stochastic if the sum of its entries at each row is $m$ and at each column is $n$. The set of all $n \times m$ doubly stochastic arrays is a convex polytope with finitely many extremal points. The main result of this paper characterizes the possible sizes of the supports of all extremal $n \times m$ doubly stochastic arrays. In particular we prove that the minimal size of the support of an $n \times m$ doubly stochastic array is $n + m - \gcd(n,m)$. Moreover, for $m=kn+1$ we also characterize the structure of the support of the extremal arrays. |
| title | Support of extremal doubly stochastic arrays |
| topic | Combinatorics 05B20, 05C05, 15B51 |
| url | https://arxiv.org/abs/2207.08116 |