On the volume of the Birkhoff polytope

Date created: 
2021-04-15
Identifier: 
etd21368
Keywords: 
Birkhoff polytope
Doubly stochastic matrices
Semi-magic squares
Asympototics
Polytopes
Abstract: 

The Birkhoff polytope was introduced in 1946 to facilitate the study of doubly stochastic matrices. The volume of the n-th Birkhoff polytope is an essential characteristic but methods to compute this are computationally complex and the volume is only known up to n = 10. In this thesis, we apply a novel automated method to calculate the relative volume using analytic combinatorics in several variables. An implementation using Maple and Sage computes this volume up to n = 6 and we compare to existing methods including interpolation, Euler’s generating function, complex analytic techniques, and Barvinok’s Algorithm (LattE). The key advantage of this method is its robustness and adaptability to variants of the initial problem.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Supervisor(s): 
Marni Mishna
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.
Statistics: