Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

Question

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \cdots & \pi_{2,n} \\ \vdots & \ddots & \ddots & \vdots \\ \pi_{n,1} & \cdots & \cdots & \pi_{n,n} \end{pmatrix} \in \mathbb{R}^{n\times n}$$ for which

• all entries are nonnegative: $\pi_{i,j}\geq 0$;
• the sum along any row or column is equal to one: $\sum_{j}\pi_{i,j}=1$ for all $i$; $\sum_{i}\pi_{i,j}=1$ for all $j$.
• the sum along any upper-left to lower-right chain of entries is at most $r$: $\sum_{k} \pi_{i_k,j_k} \leq r$ for all $(i_1,j_1)<(i_2,j_2) < \cdots < (i_m,j_m)$, where $(i,j) < (i',j')$ means $i\leq i'$, $j\leq j'$ with at least one of these inequalities being strict.

By definition $\mathcal{B}^n_n$ is the Birkhoff polytope of doubly-stochastic matrices. In general $\mathcal{B}^n_r$ is a subpolytope of the Birkhoff polytope.

It is well-known that $\mathcal{B}^n_n$ is the convex hull of all permutation matrices, and so in particular $\mathcal{B}^n_n$ is an integral polytope. But this is not true of the $\mathcal{B}^n_r$ in general: for instance, $$ \begin{pmatrix} 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \end{pmatrix}$$ is a vertex of $\mathcal{B}^3_2$. The vertices of $\mathcal{B}^n_r$ which are integral are precisely the permutation matrices of $123...r+1$-avoiding permutations.

For a polytope $\mathcal{P} \subseteq \mathbb{R}^n$ I use $L(\mathcal{P};t)$ to denote the Ehrhart function which at nonnegative integers $t$ counts the number of lattice points of $t\mathcal{P}$: $$ L(\mathcal{P};t) := \# (t\mathcal{P}\cap \mathbb{Z}^n).$$

Since $\mathcal{B}^n_r$ is not an integral polytope, but it is a rational polytope, its Ehrhart function $L(\mathcal{B}^n_r;t)$ is a priori only a quasipolynomial in $t$.

Question: Is $L(\mathcal{B}^n_r;t)$ in fact always an honest polynomial in $t$?

I have verified this for $1\leq r \leq n \leq 5$ via Sage. The computation that took the longest was $L(\mathcal{B}^5_2;t)$ which is equal to

(5959/249080832000) * (t + 1) * (t + 2) * (t + 3) * (t + 4) * (t^12 + 30*t^11 + 2534915/5959*t^10 + 22404750/5959*t^9 + 137606217/5959*t^8 + 620455590/5959*t^7 + 2117653385/5959*t^6 + 5561311650/5959*t^5 + 11311600324/5959*t^4 + 17737953240/5959*t^3 + 21126074400/5959*t^2 + 18162144000/5959*t + 10378368000/5959)

$\mathcal{B}^5_2$ has over 3000 vertices. The other data is available upon request. Probably someone with better computer skills than me can produce more data.

This phenomenon whereby an Ehrhart quasipolynomial has a smaller period than a priori predicted, or in extreme cases is in fact an honest polynomial, is called Ehrhart period collapse. It has apparently attracted some attention but remains mysterious.

Even if the above question has a negative answer, I'd still be interested in what could be said about the integer points $t\mathcal{B}^n_r\cap \mathbb{Z}^{n\times n}$.

P.S., Happy New Year's and here's to a better 2021!

EDIT: This question and the answers are now in the paper https://arxiv.org/abs/2206.02276.

Answer 1

The Ehrhart function $L(\mathcal B^n_r;t)$ is an honest polynomial. We will show this by following Per's suggestion and proving that it coincides with the Ehrhart function of a certain Gelfand-Tsetlin polytope. The following two steps can probably be combined into one, but I thought it was natural to think of it this way.

Step 1: For every $k\in \mathbb N$, the lattice points of $k\mathcal B_r^n$ are in bijection with the set of arrays $\tau\in \mathbb Z_{\geq 0} ^{n\times n}$ that are plane partitions, meaning that $i\geq i', j\geq j'$ implies $\tau_{i,j}\le \tau_{i',j'}$, that also satisfy $kr\geq \tau_{1,1}$ and for each $-n\le s\le n$ we have the traces $$tr_s(\tau)=\sum_{i}\tau_{i,i+s}=k(n-|s|).$$ Proof: This bijection is simply RSK applied to the array $\pi$. The entry $\tau_{1,1}$ records the length of longest increasing subsequence in the biword recording $\pi$, which is exactly the largest possible sum of $\pi_{i,j}$'s along an upper left-lower right chain. This is where the restriction $kr\geq \tau_{1,1}$ comes from.

Let's introduce the partitions $\lambda^n_r=\{r^n0^n\}$ and $\mu^n_r=\{(r-1)^n1^n\}$.

Step 2: The plane partitions from the previous lemma are in bijection with the lattice points in the Gelfand-Tsetlin polytope $GT(k\lambda^n_r, k\mu^n_r)=kGT(\lambda^n_r, \mu^n_r)$, therefore they are counted by the Kostka number $K(k\lambda^n_r, k\mu^n_r)$.

Proof: If we write a Gelfand-Tseltin pattern with top row given by $k\lambda^n_r=\{kr,kr,\dots, kr, 0, 0,\dots, 0\}$ we can erase the leftmost entries that are forced to be $=kr$ and the rightmost entries that are forced to be $=0$ to be left with a ($45^{\circ}$ rotated) $n\times n$ array. This array is a plane partition with largest part $\le kr$ and the appropriate traces.

For $k\mathcal B^{4}_2$ this bijection looks like simply selecting the array of $*$'s. $$\begin{matrix} 2k && 2k && 2k && 2k && 0 && 0 && 0 && 0\\ & 2k && 2k && 2k && * && 0 && 0 && 0 \\ && 2k && 2k && * && * && 0 && 0\\ &&& 2k && * && * && * && 0 \\ &&&& * && * && * && * \\ &&&&& * && * && * \\ &&&&&& * && * \\ &&&&&&& * \end{matrix}$$

Combining both steps gives $L(\mathcal B^n_r ;t)=L(GT(\lambda^n_r, \mu^n_r);t)$ which implies the desired polynomiality. It is also expected that positivity of coefficients holds, but I believe it is not known yet.

Answer 2

I strongly suspect that the polytope in question is type of a (skew) Gelfand-Tsetlin polytope. The corresponding Ehrhart functions are polynomials, even though the polytopes are non-integral in general.

The classical Birkhoff polytope is an example of this; you can get it from skew Kostka polynomials associated with the skew shape, which consists of $n$ disconnected boxes. Dilation of the polytope with factor $k$ corresponds to having $n$ disjoint rows of length $k$.

Moreover, it is conjectured that the Ehrhart polynomials here always have non-negative coefficients (in fact, a more general conjecture states this for the Berenstein-Zelevinsky polytopes).