Vertices The Birkhoff polytope has n! vertices, one for each permutation on n items. but equivalent results in the languages of
projective configurations and of
regular bipartite graph matchings, respectively, were shown much earlier in 1894 in
Ernst Steinitz's thesis and in 1916 by
Dénes Kőnig. Because all of the vertex coordinates are zero or one, the Birkhoff polytope is an
integral polytope.
Edges The edges of the Birkhoff polytope correspond to pairs of permutations differing by a cycle: {{bi|left=1.6|(\sigma,\omega) such that \sigma^{-1}\omega is a cycle. }} This implies that the
graph of B_n is a
Cayley graph of the
symmetric group S_n. This also implies that the graph of B_3 is a
complete graph K_6, and thus B_3 is a
neighborly polytope.
Facets The Birkhoff polytope lies within an
affine subspace of the space of all n\times n matrices. This subspace is determined by the linear equality constraints that the sum of each row and of each column must equal one. Within this subspace, it is defined by n^2
linear inequalities, one for each coordinate of the matrix, specifying that the coordinate must be non-negative. Therefore, for n\ge 3, it has exactly n^2
facets. A combinatorial formula for all n was given in 2007. The following
asymptotic formula was found by
Rodney Canfield and
Brendan McKay: :\mathop{\mathrm{vol}}(B_n) \, = \, \exp\left( - (n-1)^2\ln n + n^2 - \left(n - \frac{1}{2}\right)\ln(2\pi) + \frac{1}{3} + o(1) \right) . For small values n\le 15 the volume was estimated in 2014 while similar estimations follow.
Ehrhart polynomial Determining the
Ehrhart polynomial of a polytope is harder than determining its volume, since the volume can easily be computed from the leading coefficient of the Ehrhart polynomial. The Ehrhart polynomial associated with the Birkhoff polytope is only known for small values. It is conjectured that all the coefficients of the Ehrhart polynomials are non-negative. == Generalizations ==