- Асимптотические оценки количества таблиц непредвиденных обстоятельств, целочисленных потоков и объемов транспортных многогранников (arXiv)
Автор : Александр Барвинок
Аннотация: Мы доказываем асимптотическую оценку числа mxn неотрицательных целочисленных матриц (таблиц сопряженности) с заданными суммами строк и столбцов и, в более общем случае, числа целочисленных допустимых потоков в сети. Аналогично оценивается объем многогранника mxn неотрицательных вещественных матриц с заданными суммами по строкам и столбцам. Наши оценки являются решениями задач выпуклой оптимизации и, следовательно, могут быть вычислены эффективно. Как следствие, мы показываем, что если суммы строк R=(r_1, …, r_m) и суммы столбцов C=(c_1, …, c_n) с r_1 + … + r_m =c_1 + … +c_n =N достаточно далеки от постоянных векторов, то асимптотически в равномерном вероятностном пространстве mxn целочисленных неотрицательных матриц с общей суммой элементов N событие, состоящее из матриц с суммами по строкам R, и событие, состоящее из матриц с суммами по столбцам C, положительно коррелированный.
2. Графы транспортных многогранников (arXiv)
Автор: Хесус А. Де Лоэра, Эдвард Д. Ким, Шмуэль Онн, Франсиско Сантос.
Аннотация: В статье обсуждаются свойства графов двусторонних и трехсторонних транспортных многогранников, в частности их возможное число вершин и их диаметры. Наши основные результаты включают квадратичную оценку диаметра аксиальных трехсторонних транспортных многогранников и каталог невырожденных транспортных многогранников малых размеров. Каталог опровергает пять гипотез об этих многогранниках, высказанных в монографии Емеличева и др. (1984). Это также позволило нам обнаружить некоторые новые результаты. Например, мы доказываем, что количество вершин транспортного многогранника m × n кратно наибольшему общему делителю m и n.