Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices | Sciact - Система учета научной деятельности ИМ СО РАН

Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices Научная публикация

Журнал

Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X

Вых. Данные

Год: 2026, Том: 349, Номер: 1, Страницы: 114653 Страниц : 7 DOI: 10.1016/j.disc.2025.114653

Ключевые слова

Polystochastic matrix, Birkhoff polytope, Vertices of a polytope, Asymptotic bound, Multidimensional permutation

Авторы

Potapov Vladimir N. ¹ , Taranenko Anna A. ¹

Организации

1	Sobolev Institute of Mathematics

Информация о финансировании (2)

1	Институт математики им. С.Л. Соболева СО РАН	FWNF-2022-0017
2	Российский научный фонд	22-21-00202

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.

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

Поступила в редакцию:	21 июн. 2024 г.
Принята к публикации:	18 июн. 2025 г.
Опубликована online:	7 июл. 2025 г.
Опубликована в печати:	1 янв. 2026 г.

Web of science:	WOS:001530761200001
Scopus:	2-s2.0-105009281683
OpenAlex:	W4412060237

Пока нет цитирований