# Perturbation of central transportation polytopes of order $kn \times n$

Fu Liu¹†

¹Department of Mathematics, University of California, One Shields Avenue, Davis, California 95616.

**Abstract.** We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn \times n$, we obtain formulas for the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn \times n$.

**Résumé.** Nous décrivons une méthode de perturbation qui peut être utilisée pour calculer la fonction génératrice multivariée (MGF) d'un polyèdre non-simple, et ensuite construire une perturbation qui fonctionne pour tout polytope de transport. Appliquant cette perturbation à la famille des centraux de transport polytopes de l'ordre $kn \times n$, nous obtenons des formules pour le MGF du polytope. Les formules que nous obtenons sont énumérées par les objets combinatoires. Un cas spécial des formules récupère les résultats sur des polytopes de Birkhoff donnés par l'auteur et De Loera et Yoshida. Nous récupérons également la formule pour le nombre de sommets maximum des de transport polytopes d'ordre $kn \times n$.

**Keywords:** transportation polytope, perturbation, multivariate generating function

## 1 Introduction

Let $B_n$ be the convex polytope of $n \times n$ doubly-stochastic matrices; that is the set of real nonnegative matrices with all row and column sums equal to one. The volume and Ehrhart polynomial of $B_n$ are extremely hard to compute. The volume $Vol(B_n)$ has been computed for $n \le 10$ [BP03] and the Ehrhart polynomial of $B_n$ has only been computed for $n \le 9$. In [LLY09], the authors find a combinatorial expression for the multivariate generating function (MGF) of $B_n$, from which they obtain the first combinatorial formulas for the volume and Ehrhart polynomial of $B_n$. The majority work in [LLY09] is to find the MGF of $B_n$, from which the authors obtain formulas for the volume and Ehrhart polynomial of $B_n$ by residue calculation.

The Birkhoff polytope belongs to the family of transportation polytopes: Given $\mathbf{r} = (r_1, \dots, r_m)$ and $\mathbf{c} = (c_1, \dots, c_n)$ two vectors of positive entries whose coordinates sum to a fixed integer, the transportation polytope determined by $\mathbf{r}$ and $\mathbf{c}$, denoted by $\mathcal{T}(\mathbf{r}, \mathbf{c})$, is the set of all $m \times n$ nonnegative matrices

<footnote>†The author is partially supported by the Hellman Fellowship from UC Davis.</footnote>
in which row $i$ has sum $r_i$ and column $j$ has sum $c_j$. We call $T(\mathbf{r}, \mathbf{c})$ a transportation polytope of order $m \times n$. As the simplest generalization of Birkhoff polytopes, it is natural to study the same questions of volume and Ehrhart polynomial for the family of transportation polytopes. Since the techniques used in [LLY09] to obtain volumes and Ehrhart polynomials from MGFs can be applied to the MGF of any polytope, we will focus on finding MGFs of transportation polytopes. The problem is relatively easy when a transportation polytope is non-degenerate (see Section 3 for the definition), in which case one can apply Corollary 3.7 to find its MGF. However, if a transportation polytope is degenerate, it is usually non-simple, in which case one often has to triangulate the non-simple feasible cones. One of the main results of this paper is a perturbation method that can be used to find the MGFs of degenerate transportation polytopes.

Following a suggestion of Bernd Sturmfels through personal communication, we consider a special family of transportation polytopes that contains the Birkhoff polytope: the family of central transportation polytopes. A classical central transportation polytope of order $m \times n$ is a transportation polytope whose column sums are all $m$ and row sums are all $n$. However, strictly speaking Birkhoff polytopes do not belong to this family because the column sums and row sums are all 1 for $B_n$. Therefore, we generalize the definition of the classical central transportation polytopes a bit to include Birkhoff polytopes. A transportation polytope $T(\mathbf{r}, \mathbf{c})$ is central of order $m \times n$ if all the column sums are the same and all the row sums are the same. The family of central transportation polytopes is an interesting subset of transportation polytopes. For example, when $m$ and $n$ are coprime, the central transportation polytope of order $m \times n$ achieves the maximum possible number of vertices among all the transportation polytopes of order $m \times n$ [Bo172]. In [LLY09], the combinatorial data used to enumerate the MGF of $B_n$ is the family of rooted trees. Sturmfels asked whether we can give a nice description in terms of trees for the MGF of any central transportation polytope. We answer his question for central transportation polytopes of order $kn \times n$ by using the perturbation method we develop. Note that the Birkhoff polytope $B_n$ is a special case of this family of central transportation polytopes when $k = 1$. Our result recovers the formulas for the MGF of $B_n$ given in [LLY09].

This paper is organized as follows. In Section 2, we give background on results related to multivariate generating functions. In Section 3, we review results on properties of transportation polytopes. In Section 4, we introduce our perturbation method, and describe a perturbation that works for every transportation polytope. In Section 5, we apply the perturbation method to central transportation polytopes of order $kn \times n$ and give combinatorial formulas for the MGFs of these polytopes.

# 2 Background

## 2.1 Ehrhart polynomials and multivariate generating functions

A polyhedron is the set of points defined by a system of linear inequalities $Ax \le b$, where $A$ is an $N \times D$ matrix and $b$ is a $D$-vector. A polytope is a bounded polyhedron. We assume familiarity with basic definitions of polytopes as presented in [Zie98]. For any polyhedron $P$, we use Vert($P$) to denote the vertex set of $P$. An integral polyhedron is a polyhedron whose vertices are all lattice points, i.e., points with integer coordinates.

For any polytope $P \subset \mathbb{R}^D$, and a nonnegative integer $t$, we define

$$i(P, t) = \#(tP \cap \mathbb{Z}^D)$$

to be the number of lattice points inside $tP = \{tx \mid x \in P\}$, the $t$th dilation of $P$. It is well-known that given a $d$-dimensional integral polytope $P$, the function $i(P, t)$ is a polynomial in $t$ of degree $d$ with
leading coefficient being the normalized volume of P. Since this was first discovered by Ehrhart [Ehr62], we often refer to $i(P, t)$ as the Ehrhart polynomial of P. Because the leading coefficient of $i(P, t)$ gives the volume of P, obtaining the Ehrhart polynomials of polytopes is one way people use to compute volumes of polytopes. One can find the Ehrhart polynomial $i(P, t)$ of P using the multivariate generating function.

**Definition 2.1** Let $P \subset \mathbb{R}^D$ be a polyhedron. The multivariate generating function (or MGF) of P is:

$$f(P, \mathbf{z}) = \sum_{\alpha \in P \cap \mathbb{Z}^D} \mathbf{z}^{\alpha},$$

$$\text{where } \mathbf{z}^{\alpha} = \prod_{i=1}^{D} z_i^{\alpha_i}.$$

Note that when P is a polytope, we obtain $i(P, t)$ by plugging $z_i = 1$ for all $i$ in the MGF $f(tP, \mathbf{z})$ of $tP$.

## 2.2 Cones of polyhedra and Brion's theorem

One benefit of computing the MGF of a polyhedron is that the problem can be reduced to computing the MGF of the tangent/feasible cones of the given polyhedron by applying Brion's theorem. Let's first review some related definitions and results.

**Definition 2.2** Suppose P is a polyhedron and $v \in P$. The tangent cone of P at v is

$$\text{tcone}(P, v) = \{v + u : v + \delta u \in P \text{ for all sufficiently small } \delta > 0\}.$$

The feasible cone of P at v is

$$\text{fcone}(P, v) = \{u : v + \delta u \in P \text{ for all sufficiently small } \delta > 0\}.$$

For a set $S \subseteq \mathbb{R}^D$, the indicator function $[S] : \mathbb{R}^D \to \mathbb{R}$ of S is defined as

$$[S](x) = \begin{cases} 1 & \text{if } x \in S, \\ 0 & \text{if } x \notin S. \end{cases}$$

We assume the readers are familiar with the definition of algebra of polyhedra/polytopes and valuation presented in [BP99]. The following lemma gives the two important equations of indicator functions of cones of polyhedra.

**Lemma 2.3 (Theorems 6.4 and 6.6 in [Bar08])** Suppose P is a non-empty polyhedron. Then

$$[P] \equiv \sum_{v \in \text{Vert}(P)} [\text{tcone}(P, v)] \quad \text{modulo polyhedra with lines;} \quad (1)$$

$$[0] \equiv \sum_{v \in \text{Vert}(P)} [\text{fcone}(P, v)] \quad \text{modulo polyhedra with lines.} \quad (2)$$

It turns out that the multivariate generating functions define a valuation on the algebra of polyhedra.

**Theorem 2.4 (Theorem 3.1 and its proof in [BP99])** There is a map $\mathfrak{F}$ which, to each rational polyhedron $P \subset \mathbb{R}^D$, associates a unique rational function $f(P, \mathbf{z})$ in $D$ complex variables $\mathbf{z} \in \mathbb{C}^D$, $\mathbf{z} = (z_1, \dots, z_D)$, such that the following properties are satisfied:
(i) The map $\mathfrak{f}$ is a valuation.

(ii) If $P$ is pointed, there exists a nonempty open subset $U_p \subset \mathbb{C}^D$, such that $\sum_{\alpha \in P \cap \mathbb{Z}^D} \mathbf{z}^\alpha$ converges absolutely to $f(P, \mathbf{z})$ for all $\mathbf{z} \in U_p$.

(iii) If $P$ is pointed, then $f(P, \mathbf{z})$ satisfies

$$f(P, \mathbf{z}) = \sum_{\alpha \in P \cap \mathbb{Z}^D} \mathbf{z}^{\alpha}$$

for any $\mathbf{z} \in \mathbb{C}^D$ where the series converges absolutely.

(iv) If $P$ is not pointed, i.e., $P$ contains a line, then $f(P, \mathbf{z}) = 0$.

Using this valuation property and Equation (1), we immediately have Brion's theorem:

**Theorem 2.5 (Brion, 1988; Lawrence, 1991) Let $P$ be a rational polyhedron. Then,**

$$f(P, \mathbf{z}) = \sum_{v \in \text{Vert}(P)} f(\text{tcone}(P, v), \mathbf{z}).$$

**Corollary 2.6 If $P$ is an integral polyhedron, then**

$$f(P, \mathbf{z}) = \sum_{v \in \text{Vert}(P)} \mathbf{z}^v f(\text{fcone}(P, v), \mathbf{z}). \qquad (3)$$

Hence, for any positive integer $t$,

$$f(tP, \mathbf{z}) = \sum_{v \in \text{Vert}(P)} \mathbf{z}^{tv} f(\text{fcone}(P, v), \mathbf{z}). \qquad (4)$$

One see that to get the MGF of the $t$th dilation of an integral polyhedron, we only need to replace $v$ in (3) with $tv$. Therefore, as long as we know the formula for the MGF $f(P, \mathbf{z})$ of an integral polytope $P$ (assuming the formula is of form (3), we can easily obtain the formulas for the MGFs of its dilations. Then one can use residue calculation showed in [LLY09] to find the volume and Ehrhart polynomial of $P$. Hence, the problem of finding formulas for the volume and Ehrhart polynomial of an integral polytope is reduced to finding the formula for its MGF. However, by Corollary 2.6, it suffices to find the formulas for the MGF of the feasible cone of each vertex of $P$.

## 2.3 MGFs of unimodular cones

In general, one cannot calculate the MGF of a cone just by reading its generating rays. If a cone is not simple, i.e., the number of rays that generate the cone is larger than the dimension of the cone, one usually has to triangulate the cone into simple cones first. Even if a cone is simple, it is usually impossible to calculate its MGF directly from its generating rays. However, it can be done when the cone is unimodular. A pointed cone $K$ in $\mathbb{R}^D$ generated by the rays $\{r_i\}_{1 \le i \le d}$ is unimodular if $r_i$'s form a $\mathbb{Z}$-basis of the lattice $\mathbb{Z}^D \cap \text{span}(K)$.
**Lemma 2.7 (Lemma 4.1 in [BP99])** Suppose K is a unimodular cone generated by the rays {$r_i$}$_{1\le i\le d}$. Then

$$f(K, \mathbf{z}) = \prod_{i=1}^{d} \frac{1}{1 - \mathbf{z}^{r_i}}.$$

Because of computing the MGF of a unimodular cone is easy, it is easy to compute the MGF of an integral polyhedron/polytope whose feasible cones are all unimodular. Therefore, we give the following definition.

**Definition 2.8** A polytope $P \subset \mathbb{R}^D$ is totally unimodular if every vertex of $P$ is a lattice point and every feasible cone of $P$ is unimodular.

**Corollary 2.9** Suppose $P \subset \mathbb{R}^D$ is a totally unimodular polytope. Then

$$f(P, \mathbf{z}) = \sum_{v \in \text{Vert}(P)} \mathbf{z}^v \prod_{i=1}^{d} \frac{1}{1 - \mathbf{z}^{r_{v,i}}}$$

where $r_{v,1}, \dots, r_{v,d}$ are the generating rays of the vertex $v$.

**Proof:** It follows from Corollary 2.6 and Lemma 2.7. $\square$

<figure><img src="image_1.png" /></figure>

# 3 Properties of Transportation Polytopes

In this section, we will review properties of transportation polytopes. Most of them can be found in [YKK84].

Transportation polytopes have natural connection to the complete bipartite graphs. Let $K_{m,n}$ be the complete bipartite graph with $m$ vertices $u_1, \dots, u_m$ on the left and $n$ vertices $w_1, \dots, w_n$ on the right. In this paper, we often refer to $u_i$'s as the left vertices and $w_j$'s as the right vertices. Denote by $e_{i,j}$ the edge in $K_{m,n}$ connecting $u_i$ and the $w_j$. For any subgraph $G$ of $K_{m,n}$, we denote by $E(G)$ the edge set of $G$.

Let $A_{m,n}$ be the incidence $(m+n) \times mn$ matrix of $K_{m,n}$. (Then the column $A_{m,n}^{i,j}$ of $A_{m,n}$ corresponding to the edge $e_{i,j}$ is the $(m+n)$-vector where the $i$th and $(m+j)$th component are 1 and zero elsewhere.) Then the transportation polytope $\mathcal{T}(\mathbf{r}, \mathbf{c})$ can be described by

$$A_{m,n}\mathbf{x} = \begin{pmatrix} \mathbf{r}^T \\ \mathbf{c}^T \end{pmatrix}, \quad \mathbf{x} \ge 0.$$

We often call matrix $A_{m,n}$ the constraint matrix of the transportation polytopes of order $m \times n$.

A vertex of a transportation polytope of order $m \times n$ is non-degenerate if it has exactly $m+n-1$ entries that are positive; otherwise it is degenerate. A transportation polytope is non-degenerate if all its vertices are non-degenerate; otherwise it is degenerate. It's easy to see that every non-degenerate transportation polytope is simple. It is known that $A_{m,n}$ is a totally unimodular matrix, i.e., every minor of $A_{m,n}$ is 0, 1, or -1. Therefore, if a transportation polytope is non-degenerate or simple, it is a totally unimodular polytope. Then we can apply Corollary 2.9 to find its MGF.

There is an easy way to identify non-degenerate transportation polytopes.
**Theorem 3.1 (Theorem 1.2 of Chapter 6 in [YKK84])** The transportation polytope $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is non-degenerate if and only if the only nonempty index subsets $I \subseteq [m]$ and $J \subseteq [n]$ satisfying $\sum_{i \in I} r_i = \sum_{j \in J} c_j$ are $I = [m]$ and $J = [n]$.

To express the MGF of a totally unimodular polytope, we need to know how to describe its vertices, and the generating rays of each feasible cone.

## 3.1 Vertices of transportation polytopes

The vertices of a transportation polytope can be characterized with the auxiliary graphs.

**Definition 3.2** For any $M \in \mathcal{T}(\mathbf{r}, \mathbf{c})$, we define $\text{supp}(M)$ to be the set of indices $(i, j)$ such that $M(i, j)$ is positive.

The auxiliary graph of $M$, denoted by $\text{aux}(M)$, is the induced subgraph of $K_{m,n}$ with edge set $\{e_{i,j} | (i, j) \in \text{supp}(M)\}$.

We denote by $\text{vertAux}(\mathbf{r}, \mathbf{c})$ the set of all the auxiliary graphs obtained from vertices of $\mathcal{T}(\mathbf{r}, \mathbf{c})$.

We have that a point $M \in \mathcal{T}(\mathbf{r}, \mathbf{c})$ is a vertex of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ if and only if the column vectors $\{A_{m,n}^{i,j} | (i, j) \in \text{supp}(M)\}$ are linearly independent. However, one can show that given any index set $\text{ind} \subset [m] \times [n]$, the column vectors $\{A_{m,n}^{i,j} | (i, j) \in \text{ind}\}$ are linearly independent if and only if the induced subgraph of $K_{m,n}$ with edge set $\{e_{i,j} | (i, j) \in \text{ind}\}$ is a forest. Therefore, we have the following theorem, which follows from Theorem 2.2 of Chapter 6 in [YKK84].

**Theorem 3.3** Let $M \in \mathcal{T}(\mathbf{r}, \mathbf{c})$. Then $M$ is a vertex of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ if and only if $\text{aux}(M)$ is a spanning forest of $K_{m,n}$. Furthermore, $\text{aux}$ induces a bijection between the vertex set of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ and the set of spanning forests of $K_{m,n}$ that are auxiliary graphs of some points in $\mathcal{T}(\mathbf{r}, \mathbf{c})$.

In particular, if $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is non-degenerate, $M$ is a vertex of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ if and only if $\text{aux}(M)$ is a spanning tree of $K_{m,n}$. Thus, $\text{aux}$ induces a bijection between the vertex set of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ and the set of spanning trees of $K_{m,n}$ that are auxiliary graphs of some points in $\mathcal{T}(\mathbf{r}, \mathbf{c})$.

## 3.2 Feasible cones of transportation polytopes

Section 4.1 of Chapter 6 in [YKK84] gives a complete description of the generating rays of feasible cones of transportation polytopes, as well as a characterization of when two vertices are adjacent in a transportation polytope. We summarize the results as two lemmas below (Lemma 3.5 and Lemma 3.6). We begin with a preliminary definition.

**Definition 3.4** Let $T$ be a spanning forest of $K_{m,n}$ and $e \notin E(T)$. Suppose $T \cup e$ creates a cycle. Note this cycle is unique if it exists. The edge $e$ must be contained in the cycle. Suppose this cycle is:

$$e = e_{i_1,j_1}, e_{i_2,j_1}, e_{i_2,j_2}, \dots, e_{i_s,j_s}, e_{i_1,j_s}.$$

We define cycle($T$, $e$) to be the $m \times n$ matrix whose entries are defined as

$$\text{cycle}(T, e)(i, j) = \begin{cases} 1, & \text{if } (i, j) \in \{(i_1, j_1), (i_2, j_2), \dots, (i_s, j_s)\}; \\ -1, & \text{if } (i, j) \in \{(i_2, j_1), (i_3, j_2), \dots, (i_1, j_s)\}; \\ 0, & \text{otherwise.} \end{cases} \qquad (5)$$
**Lemma 3.5** Let M be a vertex in $\mathcal{T}(\mathbf{r}, \mathbf{c})$, and $T = \text{aux}(M)$ the auxiliary graph of M. (By Theorem 3.3, $T$ is a spanning forest of $K_{m,n}$.) Then

$$ \{\text{cycle}(T, e) \mid T \cup e \text{ creates a cycle}\} \qquad (6) $$

is the set of rays that generates the feasible cone of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ at the vertex M. In particular, if $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is non-degenerate. Then the generating set (6) can be rewritten as

$$ \{\text{cycle}(T, e) \mid e \notin E(T)\}. \qquad (7) $$

**Lemma 3.6** Let M and N be two distinct vertices in $\mathcal{T}(\mathbf{r}, \mathbf{c})$. Then M and N are adjacent if and only if the union of $\text{aux}(M)$ and $\text{aux}(N)$ has a unique cycle.

Moreover, if M and N are two adjacent vertices, the unique cycle in the union of $\text{aux}(M)$ and $\text{aux}(N)$ is the same as cycle($\text{aux}(M), e$), for some $e \notin E(\text{aux}(M))$. Thus, the unique cycle determines the ray from M to N as described in (5).

It turns out that the transportation polytope $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is integral if $\mathbf{r}$ and $\mathbf{c}$ are both integer vectors. Hence, the following corollary follows immediately from Corollary 2.9 and Lemma 3.5.

**Corollary 3.7** Suppose $\mathbf{r}$ and $\mathbf{c}$ are integer vectors and $\mathcal{T}(\mathbf{r}, \mathbf{c})$ a non-degenerate transportation polytope. Then the multivariate generating function of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is

$$ f(\mathcal{T}(\mathbf{r}, \mathbf{c}), \mathbf{z}) = \sum_{M \in \text{Vert}(\mathcal{T}(\mathbf{r}, \mathbf{c}))} \mathbf{z}^M \prod_{e \notin E(\text{aux}(M))} \frac{1}{1 - \mathbf{z}^{\text{cycle}(\text{aux}(M), e)}}. \qquad (8) $$

We also have the following corollary to Lemma 3.6.

**Corollary 3.8** Suppose $\mathcal{T}(\mathbf{r}, \mathbf{c})$ and $\mathcal{T}(\mathbf{r}', \mathbf{c}')$ are two transportation polytopes of order $m \times n$ satisfying

$$ \text{vertAux}(\mathbf{r}, \mathbf{c}) = \text{vertAux}(\mathbf{r}', \mathbf{c}'). $$

Let $T \in \text{vertAux}(\mathbf{r}, \mathbf{c})$, and $M_T$ and $M'_T$ be the vertices of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ and $\mathcal{T}(\mathbf{r}', \mathbf{c}')$, respectively, corresponding to T. Then

$$ \text{fcone}(\mathcal{T}(\mathbf{r}, \mathbf{c}), M_T) = \text{fcone}(\mathcal{T}(\mathbf{r}', \mathbf{c}'), M'_T). $$

# 4 A perturbation method

When calculating the MGF of a polytope/polyhedron which has non-simple feasible cones, we usually triangulate those non-simple feasible cones into simple cones, and then apply various algorithms [Bar08, Chapter 16] for computing MGFs of simple cones to find the final formula. In this section, we introduce a perturbation method that can be used to replace the triangulation step in the above procedure. We then apply this method to transportation polytopes. Because the constraint matrix $A_{m,n}$ of transportation polytopes is totally unimodular, the simple cones we obtain from the perturbation are all unimodular. Hence, instead of using other algorithms, it suffices to use Corollary 2.7 to obtain the MGFs.

**Lemma 4.1** Let P be a non-empty rational polyhedron defined by $A\mathbf{x} \le \mathbf{b}$. Let $\{\mathbf{b}_1, \mathbf{b}_2, \dots\}$ be a sequence of vectors that converges to $\mathbf{b}$, and $\ell$ a fixed integer. Suppose each $\mathbf{b}_i$ defines a non-empty polyhedron $P_i = \{\mathbf{x} \mid A\mathbf{x} \le \mathbf{b}_i\}$ with exactly $\ell$ vertices: $w_{i,1}, \dots, w_{i,\ell}$ satisfying the following conditions:
a) The feasible cone of $P_i$ at $w_{i,j}$ does not depend on $i$, i.e., there exists a cone $K_j$ for each $1 \le j \le \ell$, such that

$$fcone(P_i, w_{i,j}) = K_j, \forall i \in \mathbb{N}.$$

b) For each $1 \le j \le \ell$, the sequence of vertices $\{w_{1,j}, w_{2,j}, \dots\}$ converges to some vertex of $P$.

For each $v \in \text{Vert}(P)$, let $J_v$ be the set of $j$'s where $\{w_{1,j}, w_{2,j}, \dots\}$ converges to $v$. Then

$$[fcone(P, v)] \equiv \sum_{j \in J_v} [K_j] \text{ modulo polyhedra with lines.}$$

Therefore,

$$f(fcone(P, v), \mathbf{z}) = \sum_{j \in J_v} f(K_j, \mathbf{z}).$$

**Proof:** Omit. □

It is clear that we have the following lemma.

**Lemma 4.2** Lemma 4.1 still holds if we replace the sequence $\{\mathbf{b}_1, \mathbf{b}_2, \dots\}$ with a continuous function $\mathbf{b}(t)$ on some interval $(c, 0)$ or $(0, d)$ which converges to $\mathbf{b}$ as $t$ goes to 0.

**Corollary 4.3** We assume the same conditions as Lemma 4.1 or Lemma 4.2, and assume further that $P$ is integral. Then

$$f(P, \mathbf{z}) = \sum_{v \in \text{Vert}(P)} \mathbf{z}^v \sum_{j \in J_v} f(K_j, \mathbf{z}) = \sum_{j=1}^{\ell} \mathbf{z}^{\lim_{i \to \infty} w_{i,j}} f(K_j, \mathbf{z}).$$

### A universal perturbation

We will describe a perturbation that works for any transportation polytope.

**Lemma 4.4** Suppose $\mathbf{r} = (r_1, r_2, \dots, r_m)$ and $\mathbf{c} = (c_1, c_2, \dots, c_n)$ are two rational vectors. We define

$$\mathbf{r}(t) = (r_1 - t, \dots, r_m - t), \quad \mathbf{c}(t) = (c_1, \dots, c_{n-1}, c_n - mt), \quad 0 \le t < \frac{1}{Km},$$

where $K$ is the greatest common divisor of the denominators of $\mathbf{r}$ and $\mathbf{c}$. Then we have the following:

(i) For any $t \in (0, \frac{1}{Km})$, the transportation polytope $\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t))$ is non-degenerate.

(ii) For any $t \in (0, \frac{1}{Km})$, the set $\text{vertAux}(\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t)))$ is in dependent of $t$.

(iii) $\{\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t)) \mid t \in (0, \frac{1}{Km})\}$ is a family of transportation polytopes satisfying the condition of Lemma 4.2.

We give the following two definitions before the proof of the above lemma.

**Definition 4.5** Let $x$ be a real number. The floor or integer part of $x$, denoted by $\lfloor x \rfloor$ is the biggest integer that is not greater than $x$, and the fractional part of $x$, denoted by $\text{frac}(x)$, is $x - \lfloor x \rfloor$. The ceiling of $x$, denoted by $\lceil x \rceil$ is the smallest integer that is not smaller than $x$, and the co-fractional part of $x$, denoted by $\text{cofrac}(x)$, is $\lceil x \rceil - x$.
**Definition 4.6** Let G be a subgraph of the complete bipartite graph $K_{m,n}$.

Let $d_j$ be the number of edges in G connecting to $w_j$, the jth right vertex of $K_{m,n}$. We call $(d_1, d_2, \dots, d_n)$ the right degree sequence of G and write $\delta(G) = (d_1, \dots, d_n)$.

We also define

$$l(G) := \text{the number of } u_i\text{'s in G, i.e., the number of left vertices in G.}$$

For convenience, for any spanning tree T of $K_{m,n}$, we consider T as a rooted tree rooted at $w_n$, the nth right vertex. For any vertex v of T, we denote by $T_v$ the subtree of T rooted at v.

**Proof of Lemma 4.4:** Because $\mathcal{T}(Kr(t), Kc(t))$ is a dilation of $\mathcal{T}(r(t), c(t))$, the polytopes $\mathcal{T}(Kr(t), Kc(t))$ and $\mathcal{T}(r(t), c(t))$ have exactly the same combinatorial structures. Therefore, without loss of generality, we can assume that $r$ and $c$ are integer vectors, and $K = 1$.

(i) Suppose $\emptyset \neq I \subset [m]$ and $\emptyset \neq J \subset [n]$ are two index sets satisfying

$$\sum_{i \in I} \mathbf{r}(t)_i = \sum_{j \in J} \mathbf{c}(t)_j. \qquad (9)$$

The co-fractional part of the left hand side of (9) is $|I|t \neq 0$. Hence, $n \in J$, because otherwise the right hand side of (9) is an integer. Then the co-fractional part of the right hand side of (9) is $mt$. Therefore, $|I| = m$ and $I = [m]$. This implies that $J = [n]$. Therefore, by Theorem 3.1, the polytope $\mathcal{T}(r(t), c(t))$ is non-degenerate.

(ii) Let $t_0 \in (0, \frac{1}{Km} = \frac{1}{m})$, and let $T \in \text{vertAux}(\mathcal{T}(r(t_0), c(t_0)))$. By Theorem 3.3, T is a spanning tree of $K_{m,n}$. It suffices to show that for any $t \in (0, \frac{1}{m})$, the tree T is the auxiliary graph of a vertex of $\mathcal{T}(r(t), c(t))$. Let $M_T(t_0)$ be the vertex of $\mathcal{T}(r(t_0), c(t_0))$ corresponding to the tree T.
We claim that

$$\text{cofrac}(M_T(t_0)(i, j)) = l(T_{u_i}) t_0, \quad \text{if } w_j \text{ is the parent of } u_i \text{ in } T;$$

$$\text{frac}(M_T(t_0)(i, j)) = l(T_{w_j}) t_0, \quad \text{if } u_i \text{ is the parent of } w_j \text{ in } T;$$

and the matrix $M_T$ whose entries defined by the following equation is a vertex of $\mathcal{T}(r, c)$.

$$M_T(i, j) = \begin{cases} [M_T(t_0)(i, j)], & \text{if } w_j \text{ is the parent of } u_i \text{ in } T; \\ [M_T(t_0)(i, j)], & \text{if } u_i \text{ is the parent of } w_j \text{ in } T; \\ 0, & \text{otherwise.} \end{cases} \qquad (10)$$

The claim can be proved by induction on hook lengths of vertices of T. (Recall the hook length of a vertex v in a rooted tree is the number of descendants of v.) We define the matrix $M_T(t)$ as follows:

$$M_T(t)(i, j) = \begin{cases} [M_T(t_0)(i, j)] - l(T_{u_i}) t, & \text{if } w_j \text{ is the parent of } u_i \text{ in } T; \\ [M_T(t_0)(i, j)] + l(T_{w_j}) t, & \text{if } u_i \text{ is the parent of } w_j \text{ in } T; \\ 0, & \text{otherwise.} \end{cases} \qquad (11)$$

It is clear that $M_T(t)$ is a vertex of $\mathcal{T}(r(t), c(t))$ with auxiliary graph T.
(iii) It follows from (ii) and Corollary 3.8.

□

**Corollary 4.7** Assume the conditions of Lemma 4.4 and further assume that **r** and **c** are integer vectors. Let $t_0 \in (0, \frac{1}{m})$. Then the multivariate generating function of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is

$$f(\mathcal{T}(\mathbf{r}, \mathbf{c}), \mathbf{z}) = \sum_{T \in \text{vertAux}(\mathbf{r}(t_0), \mathbf{c}(t_0))} \mathbf{z}^{M_T} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\text{cycle}(T,e)}}, \quad (12)$$

where $M_T$ is defined as in (10).

Also, for any vertex $M$ of $\mathcal{T}(\mathbf{r}, \mathbf{c})$, let

$$\text{PertAux}(M) := \{T \in \text{vertAux}(\mathbf{r}(t_0), \mathbf{c}(t_0)) \mid \text{aux}(M) \text{ is a subgraph of } T\}. \quad (13)$$

Then

$$[\text{fcone}(\mathcal{T}(\mathbf{r}, \mathbf{c}), M)] \equiv \sum_{T \in \text{PertAux}(M)} [\text{fcone}(\mathcal{T}(\mathbf{r}(t_0), \mathbf{c}(t_0)), M_T(t_0))] \quad (14)$$

modulo polyhedra with lines.

Hence,

$$f(\text{fcone}(\mathcal{T}(\mathbf{r}, \mathbf{c}), M), \mathbf{z}) = \sum_{T \in \text{PertAux}(M)} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\text{cycle}(T,e)}}. \quad (15)$$

**Proof:** Omit. □

We finish this section by a remark.

**Remark 4.8** Using Theorem 7.1 of Chapter 6 in [YKK84], we can show that when $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is a central transportation polytope, the transportation polytopes $\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t))$ we defined in Lemma 4.4 achieve the maximum number of vertices among all the transportation polytopes of order $m \times n$.

# 5 Central transportation polytope of order $kn \times n$

In this section, We always assume that $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is a central transportation polytope of order $m \times n$, where $m = kn$, and $\mathbf{r} = (a, \dots, a)$ and $\mathbf{c} = (b, \dots, b)$ are two integer vectors. We will apply the perturbation defined in the last section to $\mathcal{T}(\mathbf{r}, \mathbf{c})$, and show that $\{\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t)) \mid t \in (0, \frac{1}{m})\}$ is a family of central transportation polytopes satisfying the condition of Lemma 4.2 so that we are able to use Lemma 4.2 to find the MGF of the original (non-simple) transportation polytope.

Define

$$\mathbf{r}(t) = (a - t, \dots, a - t), \quad \mathbf{c}(t) = (b, \dots, b, b - mt), \quad 0 \le t < \frac{1}{m},$$
**Theorem 5.1** The set of vertices of $\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t))$ is in bijection with the set of the spanning trees $T$ of $K_{m,n}$ satisfying $\delta(T) = (k+1, \dots, k+1, k)$. Furthermore, for any spanning tree $T$ of $K_{m,n}$ with $\delta(T) = (k+1, \dots, k+1, k)$, the corresponding vertex of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is the matrix $M_T(t)$ whose entries are defined as:

$$ M_T(t)(i, j) = \begin{cases} a - l(T_{u_i}) t, & \text{if } w_j \text{ is the parent of } u_i \text{ in } T; \\ l(T_{w_j}) t, & \text{if } u_i \text{ is the parent of } w_j \text{ in } T; \\ 0, & \text{otherwise.} \end{cases} \qquad (16) $$

**Proof:** Omit. $\square$

It is clear that the vertices of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ are the $\{0, a\}$-matrices in which each row has exact one entry of $a$ and each column has exactly $k$ entries of $a$. These matrices corresponding to “$k$ to 1” matching from the $m = kn$ left vertices to the $n$ right vertices. This motivates the following definition.

**Definition 5.2** We call an $kn \times n$ matrix $M$ a $k$-to-$1$ matching matrix if $M$ is a $\{0, 1\}$-matrix such that there is exactly one $1$ in each row and exactly $k$ $1$'s in each column. We denote by $\mathcal{M}at_{k,n}$ the set of all the $kn \times n$ $k$-to-$1$ matching matrices.

We also call the auxiliary graph of each $k$-to-$1$ matching matrix a $k$-to-$1$ matching graph.

With this definition, the vertices of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is the set

$$ \mathrm{Vert}(\mathcal{T}(\mathbf{r}, \mathbf{c})) = \{aM \mid M \in \mathcal{M}at_{k,n}\} =: a\mathcal{M}at_{k,n}. $$

We now apply Equation (15) to get the MGF of the feasible cone of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ at each vertex and then the MGF of $\mathcal{T}(\mathbf{r}, \mathbf{c})$.

**Corollary 5.3** Suppose $M \in \mathcal{M}at_{k,n}$. Then the MGF of the feasible cone of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ at $aM$ is

$$ f(\mathrm{fcone}(\mathcal{T}(\mathbf{r}, \mathbf{c}), aM), \mathbf{z}) = \sum_{T \in \mathrm{PertAux}(aM)} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\mathrm{cycle}(T,e)}}. $$

Thus, the MGF of $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is

$$ f(\mathcal{T}(\mathbf{r}, \mathbf{c}), \mathbf{z}) = \sum_{M \in \mathcal{M}at_{k,n}} \mathbf{z}^{aM} \sum_{T \in \mathrm{PertAux}(aM)} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\mathrm{cycle}(T,e)}}. $$

In both equations,

$$ \mathrm{PertAux}(aM) = \{ \begin{array}{l} \text{all the spanning trees of } K_{kn,n} \text{ with right degree sequence} \\ (k+1, \dots, k+1, k) \text{ that contains } \mathrm{aux}(M) \end{array}. $$

The set $\mathrm{PertAux}(M)$ defined in Corollary 5.3 can be described by basic combinatorial objects. Denote by $\mathcal{R}_n$ the set of all the rooted trees on $\{w_1, w_2, \dots, w_n\}$ rooted at $w_n$.

**Lemma 5.4** Let $v$ be a vertex of $\mathcal{T}(\mathbf{r}, \mathbf{c})$, i.e., $v = aM$ for some $M \in \mathcal{M}at_{k,n}$. There is a bijection between $\mathrm{PertAux}(v)$ and the set $\mathcal{R}_n \times [k]^{n-1}$.

Therefore, the cardinality of $\mathrm{PertAux}(v)$ is $n^{n-2}k^{n-1}$.
**Proof:** Given a rooted tree $R \in \mathcal{R}_n$ and $\mathbf{f} = (f_1, \dots, f_{n-1}) \in [k]^{n-1}$, we can construct a tree $T \in \text{PertAux}(v)$ from $(R, \mathbf{f})$ in the following way: We start with the $k$-to-1 matching graph $\text{aux}(M)$. If $w_{j_0}$ is the parent of $w_j$ in $R$, we add an edge connecting $w_j$ and the $(f_j)$th left vertex that is matched to $w_{j_0}$ in $\text{aux}(M)$. After adding these $n-1$ edges, one can check that we actually obtain a spanning tree $T$ of $K_{k,n}$ rooted at $w_n$ and each right vertex $w_j$ has exactly $k$ children. We can ignore the root. Then $T$ is in $\text{PertAux}(v)$.

One sees that the above procedure can be reversed. Thus, we give a bijection between $\text{PertAux}(v)$ and $\mathcal{R}_n \times [k]^{n-1}$.

The cardinality result follows from the famous result that the $|\mathcal{R}_n| = n^{n-2}$. $\square$

When $k=1$ and $a=1$, the set $\mathcal{M}_{k,n}$ is actually the symmetric group $\mathfrak{S}_n$, and the polytope $\mathcal{T}(\mathbf{r}, \mathbf{c})$ is the Birkhoff polytope $B_n$. Therefore, for any $\sigma \in \mathfrak{S}_n$, we have a bijection between $\mathcal{R}_n$ and $\text{PertAux}(\sigma)$. We call this map $\Phi_\sigma$. Then we obtain the following theorem for the Birkhoff polytopes, which is equivalent to Theorem 1.1 and Corollary 4.1 in [LLY09].

**Theorem 5.5** Suppose $\sigma \in \mathfrak{S}_n$ is a vertex of the Birkhoff polytope $B_n$. Then the MGF of the feasible cone of $B_n$ at $\sigma$ is

$$f(\text{fcone}(B_n, \sigma), \mathbf{z}) = \sum_{T \in \Phi_\sigma(\mathbb{R}_n)} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\text{cycle}(T,e)}}.$$

Thus, the MGF of $B_n$ is

$$f(B_n, \mathbf{z}) = \sum_{\sigma \in \mathfrak{S}_n} \mathbf{z}^{\sigma} \sum_{T \in \Phi_\sigma(\mathbb{R}_n)} \prod_{e \notin E(T)} \frac{1}{1 - \mathbf{z}^{\text{cycle}(T,e)}}.$$

Lemma 5.4 also induces a bijection between $\text{Mat}_{k,n} \times \mathcal{R}_n \times [k]^{n-1}$ and $\text{vertAux}(\mathbf{r}(t), \mathbf{c}(t))$ (for any $t \in (0, \frac{1}{m})$). Therefore, we have the following Corollary.

**Corollary 5.6** The number of vertices of $\mathcal{T}(\mathbf{r}(t), \mathbf{c}(t))$ is $\frac{(kn)!}{(k!)^n} n^{n-2} k^{n-1}$.

By Remark 4.8, we obtain another known result.

**Corollary 5.7 (Corollary 8.6 of Chapter 6 in [YKK84])** The maximum number of vertices among all the transportation polytopes of order $kn \times n$ is $\frac{(kn)!}{(k!)^n} n^{n-2} k^{n-1}$.

## References

[Bar08] A. Barvinok. Integer points in Polyhedra. Zurich Lectures in Advanced Mathematics, 2008.

[Bol72] E. Bolker. Transportation polytopes. J. Combin. Th., 13B, 1972.

[BP99] A.I. Barvinok and J. Pommersheim. An algorithmic theory of lattice points in polyhedra, in: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–1997), 91–147, Math. Sci. Res. Inst. Publ. 38, Cambridge Univ. Press, Cambridge, 1999.

[BP03] M. Beck and D. Pexton. The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom., 30:623–637, 2003.
[Ehr62] E. Ehrhart. Sur les polyèdres rationnels homothétiques à *n* dimensions. *C. R. Acad. Sci. Paris*, 254:616–618, 1962.

[LLY09] J.A. De Loera, F. Liu, and R. Yoshida. A generating function for all semi-magic squares and the volume of the Birkhoff polytope. *J. Algebraic Combin.*, 30:113–139, 2009.

[YKK84] V.A. Yemelichev, M.M. Kovalev, and M.K. Kravtsov. *Polytopes, Graphs and Optimisation*. Cambridge University Press, Cambridge, 1984.

[Zie98] G. M. Ziegler. *Lectures on Polytopes*. Springer-Verlag, New York, revised edition, 1998.