Ehrhart $h^*$-polynomials of the Birkhoff polytopes

edit · history · discussion · files · short url · combinatorics discrete geometry polynomial

Polynomials

$n$

$h^*_{B_n}(z)$

z^2 + z + 1

z^6 + 14*z^5 + 87*z^4 + 148*z^3 + 87*z^2 + 14*z + 1

z^12 + 103*z^11 + 4306*z^10 + 63110*z^9 + 388615*z^8 + 1115068*z^7 + 1575669*z^6 + 1115068*z^5 + 388615*z^4 + 63110*z^3 + 4306*z^2 + 103*z + 1

z^20 + 694*z^19 + 184015*z^18 + 15902580*z^17 + 567296265*z^16 + 9816969306*z^15 + 91422589980*z^14 + 490333468494*z^13 + 1583419977390*z^12 + 3166404385990*z^11 + 3982599815746*z^10 + 3166404385990*z^9 + 1583419977390*z^8 + 490333468494*z^7 + 91422589980*z^6 + 9816969306*z^5 + 567296265*z^4 + 15902580*z^3 + 184015*z^2 + 694*z + 1

Definition

The Birkhoff polytope $B_n\subset\mathbb{R}^{n\times n}$ is the lattice polytope of $n\times n$ doubly stochastic matrices [2]. The table stores its Ehrhart $h^*$-polynomial $h^*_{B_n}(z)$, the numerator of the Ehrhart series of $B_n$ [3].

Parameters

$n$

— matrix size ($n$ is a positive integer)

Formulas

(1)

If $d=(n-1)^2$, then $\sum_{t\geq0}H_n(t)z^t=h^*_{B_n}(z)/(1-z)^{d+1}$.

(2)

With $h^*_{B_n}(z)=\sum_i h_i^*z^i$ and $d=(n-1)^2$, $H_n(t)=\sum_{i=0}^{d}h_i^*\binom{t+d-i}{d}$.

(3)

$h^*_{B_n}(1)$ is the normalized volume of $B_n$ [6].

(4)

$h^*_{B_n}(z)$ has degree $(n-1)(n-2)$ and palindromic coefficients [1].

Comments

(5)

If $d=(n-1)^2$, then $\sum_{t\geq0}H_n(t)z^t=h^*_{B_n}(z)/(1-z)^{d+1}$.

(6)

For $n=1$ and $n=2$ the polytope is respectively a point and a line segment, and $h^*_{B_1}(z)=h^*_{B_2}(z)=1$.

(7)

The rows here match the range of the companion Ehrhart polynomial table. Beck and Pixton list the Ehrhart polynomials through $n=9$ [4].

Programs

(P1)

Sage

from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

Z = PolynomialRing(QQ, "z")
z = Z.gen()
coefficients = [1, 14, 87, 148, 87, 14, 1]
sum(QQ(c) * z**i for i, c in enumerate(coefficients))  # h^*_{B_4}(z)

References

[1]

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete & Computational Geometry 30 (2003), no. 4, 623-637. (arXiv) (doi)

Links

[2]

Wikipedia: Birkhoff polytope

[3]

Wikipedia: Ehrhart polynomial

[4]

Beck and Pixton: Ehrhart polynomials for the Birkhoff polytopes

[5]

OEIS A259473: coefficients arising in the enumeration of doubly stochastic matrices of integers

[6]

OEIS A037302: normalized volume of the Birkhoff polytope

[7]

OEIS A002817: number of $3\times3$ nonnegative integer matrices with common line sum $t$

[8]

OEIS A001496: number of $4\times4$ nonnegative integer matrices with common line sum $t$

[9]

OEIS A003438: number of $5\times5$ nonnegative integer matrices with common line sum $t$

Similar tables

Ehrhart polynomials of the Birkhoff polytopes — gives the Ehrhart polynomial $H_n(t)$ whose generating series has this numerator; the two tables determine each other by (1) and (2)

Data properties

Entries are of type: rational polynomial

How well the digits are known: exact

Table is complete: no (it holds $h^*_{B_n}(z)$ for every matrix size $n$ with $3\leq n\leq6$, matching the companion Ehrhart polynomial table)

How they were obtained:

The $h^*$-polynomials are transcribed from OEIS A259473 [5].

Through (2), they give the Ehrhart polynomials compared with Beck and Pixton's published rows [4]; their values at $z=1$ agree with OEIS A037302 [6].