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!