Skip to main content

On the volume of the Birkhoff polytope

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Mishna, Marni
Member of collection
Download file Size
input_data\21354\etd21368.pdf 1.27 MB

Views & downloads - as of June 2023

Views: 42
Downloads: 2