Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices Full article
| Journal |
Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X |
||
|---|---|---|---|
| Output data | Year: 2026, Volume: 349, Number: 1, Pages: 114653 Pages count : 7 DOI: 10.1016/j.disc.2025.114653 | ||
| Tags | Polystochastic matrix, Birkhoff polytope, Vertices of a polytope, Asymptotic bound, Multidimensional permutation | ||
| Authors |
|
||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
| 2 | Russian Science Foundation | 22-21-00202 |
Abstract:
Amultidimensional nonnegative matrix is called polystochastic if the sum of the entries in each line is equal to 1. The set of all polystochastic matrices of order n and dimension d forms a convex polytope Ωd n. In the present paper, we compare known bounds on the number of vertices of the polytope Ωd n and prove that the number of vertices of Ωd 3 is doubly exponential in d.
Cite:
Potapov V.N.
, Taranenko A.A.
Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices
Discrete Mathematics. 2026. V.349. N1. P.114653. DOI: 10.1016/j.disc.2025.114653 WOS Scopus OpenAlex
Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices
Discrete Mathematics. 2026. V.349. N1. P.114653. DOI: 10.1016/j.disc.2025.114653 WOS Scopus OpenAlex
Dates:
| Submitted: | Jun 21, 2024 |
| Accepted: | Jun 18, 2025 |
| Published online: | Jul 7, 2025 |
| Published print: | Jan 1, 2026 |
Identifiers:
| Web of science: | WOS:001530761200001 |
| Scopus: | 2-s2.0-105009281683 |
| OpenAlex: | W4412060237 |
Citing:
Пока нет цитирований