Volumes and Integer Points of Multi-Index Transportation Polytopes.

combinatorics;integer points;transportation polytope;Fourier analysis;Asymptotic counting;Mathematics;Science;Mathematics

Benson-Putnins, David T.Vershynin, Roman ;

University of Michigan

关键词: combinatorics;    integer points;    transportation polytope;    Fourier analysis;    Asymptotic counting;    Mathematics;    Science;    Mathematics;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/111456/dputnins_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Counting the integer points of transportation polytopes has important applications in statistics for tests of statistical significance, as well as in several applications in combinatorics.In this dissertation, we derive asymptotic formulas for the number of integer and binary integer points in a wide class of multi-index transportation polytopes.A simple closed form approximation is given as the size of the corresponding arrays goes to infinity.A formula for the volume of $4$-index transportation polytopes is also given.We follow the approach of Barvinok and Hartigan to estimate the quantities through a type of local Central Limit Theorem.By carefully estimating eigenvalues and eigenvectors of certain quadratic forms, we are able to prove strong concentration results for the corresponding multivariate Gaussian random variables.We also estimate correlations between linear functions of Gaussian random variables to produce concentration results for the distribution of certain exponential functions.Combined, these techniques allow us to give a complete accounting of the integrals of several functions that are key to estimating the number of integer or binary integer points in multi-index transportation polytopes.As an additional result, we transform a standard concentration of measure on the sphere argument to a concentration result for Gaussian measures whose quadratic forms contain several small eigenvalues, allowing a similar calculation for the volume of multi-index transportation polytopes.