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>.



Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?
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.


