Deformation cones of Tesler polytopes

Yonggyu Lee and Fu Liu Yonggyu Lee, Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616 USA. [email protected] Fu Liu, Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616 USA. [email protected]

Abstract.

For ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , the Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is the set of upper triangular matrices with non-negative entries whose hook sum vector is ${\boldsymbol{a}}$ . We first give a different proof of the known fact that for every fixed ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ , all the Tesler polytopes $\operatorname{Tes}_{n}({\boldsymbol{a}})$ are deformations of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . We then calculate the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . In the process, we also show that any deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ is a translation of a Tesler polytope. Lastly, we consider a larger family of polytopes called flow polytopes which contains the family of Tesler polytopes and give a characterization on which flow polytopes are deformations of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ .

1. Introduction

For ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , the Tesler polytope, denoted as $\operatorname{Tes}_{n}({\boldsymbol{a}})$ , is defined as the set of upper triangular matrices with non-negative entries whose “hook sum vector” is ${\boldsymbol{a}}$ . When ${\boldsymbol{a}}=\boldsymbol{1}:=(1,\dots,1)\in\mathbb{R}^{n}$ , elements of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ with integer coordinates are called Tesler matrices. Tesler matrices were initially introduced by Tesler in the context of Macdonald polynomials and subsequently rediscovered by Haglund in his work on the diagonal Hilbert series [14]. As a result, Tesler matrices play a central role in the field of diagonal harmonics [1, 12, 13, 15, 25]. Motivated by this significance of Tesler matrices, Mészáros, Morales and Rhoades [18] defined and studied the Tesler polytopes of hook sum ${\boldsymbol{a}}\in\mathbb{Z}_{>0}^{n}$ . Their research led to several intriguing findings, including the observation that Tesler polytopes are unimodularly equivalent to certain flow polytopes, which is a family of polytopes that have connection to various areas of mathematics such as toric geometry, representation theory, special functions and algebraic combinatorics, as detailed in [4] and its references. Please refer to [18] for more background about Tesler polytopes.

Beyond their general link to flow polytopes, specific subfamilies of Tesler polytopes are fascinating objects due to their own interesting combinatorial properties and their association with other mathematics domains. We have already mentioned that the importance of the Tesler matrix polytope $\operatorname{Tes}_{n}({\boldsymbol{1}})$ in the study of diagonal harmonics. Additionally, it is known [8] that $\operatorname{Tes}_{n}(1,0,\dots,0)$ is unimodularly equivalent to the Chan-Robbins-Yuen (CRY) polytope, whose volume is the product of the first $n-2$ Catalan numbers [7, 26]. As of today, simple proofs for this surprising result are still undiscovered. Moreover, the CRY polytope is a face of the Birkhoff polyope which is also a well-studied subject. In particular, computing volumes of Birkhoff polytopes remains a challenging problem that has attracted a lot of recent research attention [5, 10, 21].

Noticing that important features remain the same, in our prior work [16], we extend the domain of Tesler polytopes $\operatorname{Tes}_{n}({\boldsymbol{a}})$ to $\mathbb{R}_{\geq 0}^{n}$ , and study a conjecture regarding Ehrhart positivity for both $\operatorname{Tes}_{n}(\boldsymbol{1})$ and $\operatorname{Tes}_{n}(1,0,\dots,0)$ , originally posed by Morales [19]. In this paper, we will continue our study on this broader family of Tesler polytopes. However, our primary focus will be directed towards investigating their deformation cones.

There are many ways of defining deformations of polytopes. The most commonly used one is stated in terms of the normal cone: a polytope $Q$ is a deformation of a polytope $P$ if the normal fan of $P$ is a refinement of the normal fan of $Q$ .

However, in this paper we use the one introduced in [6] by Castillo and the second author; see Definition 2.1 for details. It was shown in [6, Proposition 2.6] that Definition 2.1 is equivalent to the normal fan definition of deformations. We parametrize each deformation $Q$ of $P$ by a “deformation vector” and the collection of the deformation vectors forms the “deformation cone” of $P$ . Notably, the relative interior of the deformation cone is called the type cone [17], which contains the deformation vectors of all the polytopes with the same normal fan as $P$ . In the case when $P$ is a rational polytope, the type cone of $P$ is related to the nef cone of the toric variety associated to the normal fan of $P$ [9, Section 6.3].

One of the most famous family of deformations is generalized permutohedra, which are deformations of the regular permutohedron [11, 22, 23]. In the last decade, different directions of research have been done on determining the deformation cones of polytopes that are related to generalized permutohedra. In [6], Castillo and the second author define the nested permutohedron whose normal fan refines that of the regular permutohedron (so the regular permutohedron is a deformation of the nested permutohedron), and describe the deformation cone of the nested permutohedron. On the other hand, Padrol, Pilaud and Poullot [20] determine the deformation cones of nestohedra, which is a family of deformations of the regular permutohedron.

In this paper, we first give a new proof of a known fact ([2, Remark 9]) that for any fixed positive integer $n$ and ${\boldsymbol{a}}_{0}\in\mathbb{R}^{n}_{>0}$ , the Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ for all ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ (Theorem 3.1).

Then we prove the following theorem - one of our main results - which gives a description of a deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ .

(Please refer to Section 2, especially Definition 2.1 and Section 2.3.1, for necessary definitions and notations.)

Theorem 1.1.

Let ${\boldsymbol{a}}_{0}\in\mathbb{R}^{n}_{>0}$ . Then the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ with respect to $(L_{n},-P_{n})$ is

(1.1)

\{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n)~{}~{}|~{}~{}\eta_{i}(\tilde{{\boldsymbol{b}}})\geq-a_{i}\text{ for all }1\leq i\leq n-1\}

where $a_{i}$ is the $i$ -th coordinate of ${\boldsymbol{a}}$ .

Moreover, any deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ is a translation of a Tesler polytope.

It is worth mentioning that the above description of the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ is clearly minimal, i.e., none of the inequalities is redundant. Therefore, each of the linear inequality defines a facet of the deformation cone. Furthermore, the face structure of the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ is extremely easy to understand. This will allow us to give a complete characterization on which Tesler polytopes have the same normal fan (Theorem 3.9).

Recall that Mészáros et al [18] establish that Tesler polytopes is a subfamily of flow polytopes. In the last part of this paper, we strengthen this connection by providing the following characterization on which flow polytopes are deformations of $\operatorname{Tes}_{n}(\boldsymbol{1})$ . (Please see Definitions 5.1 and 5.4 for the definitions of flow polytopes and critical position.)

Theorem 1.2.

Let ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ and let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}^{n}$ such that $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is non-empty. Suppose $l$ is the critical position of ${\boldsymbol{a}}$ . Then the flow polytope $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ if and only if $l=n$ or $a_{i}\geq 0$ for all $l+2\leq i\leq n$ .

Organization of the paper

In Section 2, we provide background on polyhedra theory, deformations of polytopes, and Tesler polytopes. In Section 3, we give a different proof for the known fact that for every fixed ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ , all Tesler polytopes $\operatorname{Tes}_{n}({\boldsymbol{a}})$ are deformations of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ , as well as provide a generalization of this fact in Theorem 3.9. In Section 4, we determine the deformation cone of Tesler polytopes (Theorem 2.1), and then use it to prove Theorem 3.9. In Section 5, we discuss which flow polytopes on the complete graph are deformations of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ and complete the proof of Theorem 1.2.

Acknowledgements

The second author is partially supported by a grant from the Simons Foundation #426756 and an NSF grant #2153897-0.

We are grateful to the two anonymous referees for their valuable comments and suggestions. In particular, we are thankful for one of the referees who bring out attention to the result stated in Theorem 3.9 which was not in a previous version of this article.

2. Preliminaries

In this section, we provide preliminaries and background for this paper. We start with basic definitions for polytopes required for introducing the concepts of deformation cones.

2.1. Polytopes

A polyhedron $P$ is a subset of $\mathbb{R}^{m}$ defined by finitely many linear inequalities

(2.1)

c_{i,1}x_{1}+\cdots+c_{i,k}x_{k}\leq d_{i}\text{ for }1\leq i\leq s

where $c_{i,j}$ and $d_{i,j}$ are real numbers. We call (2.1) a tight inequality description for $P$ if for every $1\leq i\leq s$ , there exists a point $(x_{i,1},\dots,x_{i,k})$ in $P$ such that $c_{i,1}x_{i,1}+\cdots+c_{i,k}x_{i,k}=d_{i}$ . Note that (2.1) can also be written as $\langle{\boldsymbol{c}}_{i},\boldsymbol{x}\rangle\leq d_{i}$ where $\langle\cdot,\cdot\rangle$ is the dot product on $\mathbb{R}^{m}$ . If we let $C=(c_{i,j})$ and $\boldsymbol{d}$ be the column vector $[d_{1},\dots,d_{l}]^{t}$ then the above system can be written in the following matrix form

C\boldsymbol{x}\leq\boldsymbol{d}.

A polytope is a bounded polyhedron. Equivalently, a polytope $P\subset\mathbb{R}^{m}$ may be defined as the convex hull of finitely many points in $\mathbb{R}^{m}$ . A polyhedron defined by homogeneous linear inequalities is called a (polyhedral) cone. We assume that readers are familiar with the basic concepts related to polytopes, such as face and dimension, presented in [3, 27]. There are many ways to choose a linear system to define a polytope.

Let $P_{0}\subset\mathbb{R}^{m}$ be a polytope. We will use the following form to describe $P_{0}$ :

(2.2)

E\boldsymbol{x}=\boldsymbol{\alpha}_{0}\text{ and }G\boldsymbol{x}\leq\boldsymbol{\beta}_{0},

where $E\boldsymbol{x}=\boldsymbol{\alpha}_{0}$ defines the affine span of $P_{0}$ and each inequality in $G\boldsymbol{x}\leq\boldsymbol{\beta}_{0}$ defines a facet of $P_{0}$ . Any such a description is called a minimal linear inequality description for $P_{0}$ if matrices $E$ and $G$ are minimal in size, i.e, none of the equalities or inequalities are redundant. Note that any minimal inequality description is tight. It is not hard to see that minimal inequality descriptions for a non full dimensional polytope $P_{0}$ are not unique. In particular, there are different choices for the matrices $E$ and $G$ in the expression (2.2). However, any choice of $E$ and $G$ must satisfy that the rows of $E$ are $m-d$ linearly independent vectors and the rows of $A$ are in bijection with the facets of $P_{0}$ , where $d$ is the dimension of $P_{0}$ .

2.2. Deformations

In this part, we will start with the following definition of deformations initially introduced in [6]. As we mentioned earlier, this definition is equivalent to the normal fan definition of deformations given in the introduction. Another different but equivalent definition of deformation will then be given in Lemma 2.4. We finish this part with a discussion on the connection between deformation cones and type cones.

Definition 2.1.

Let $P_{0}\subset\mathbb{R}^{m}$ be a $d$ -dimensional polytope, and suppose (2.2) is a minimal linear inequality description for $P_{0}$ . Suppose $G$ has $k$ rows where ${\boldsymbol{g}}_{i}$ is the $i$ -th row vector of $G$ . For each $i$ , let $F_{i}$ be the facet of $P$ defined by $\langle{\boldsymbol{g}}_{i},\boldsymbol{x}\rangle=b_{0,i}$ where $b_{0,i}$ is the $i$ -th entry of ${\boldsymbol{b}}_{0}$ .

A polytope $Q\subset\mathbb{R}^{m}$ is a deformation of $P_{0}$ , if there exists ${\boldsymbol{a}}\in\mathbb{R}^{m-d}$ and ${\boldsymbol{b}}\in\mathbb{R}^{k}$ such that the following two conditions are satisfied :

(1)

$Q$ is defined by the system of linear inequalities:

(2.3) $E\boldsymbol{x}={\boldsymbol{a}}\text{ and }G\boldsymbol{x}\leq{\boldsymbol{b}},$

which is tight (but not necessarily minimal).
(2)

For any vertex ${\boldsymbol{v}}$ of $P_{0}$ , if $F_{i_{1}},F_{i_{2}},...,F_{i_{s}}$ are the facets of $P_{0}$ where ${\boldsymbol{v}}$ lies on, then the intersection:

$Q\cap\{\boldsymbol{x}\in\mathbb{R}^{m}:\langle{\boldsymbol{g}}_{i_{j}},\boldsymbol{x}\rangle=b_{i_{j}},1\leq j\leq s\}$

where $b_{i_{j}}$ is the $i_{j}$ -th component of ${\boldsymbol{b}}$ , is a vertex of $Q$ denoted by ${\boldsymbol{v}}_{({\boldsymbol{a}},{\boldsymbol{b}})}$ .

We call $({\boldsymbol{a}},{\boldsymbol{b}})$ the deforming vector for $Q$ with respect to ( $E$ , $G$ ). Furthermore, if ${\boldsymbol{v}}\mapsto{\boldsymbol{v}}_{({\boldsymbol{a}},{\boldsymbol{b}})}$ gives a bijection from the vertex set of $P_{0}$ to the vertex set of $Q,$ we say $Q$ is a weak deformation of $P_{0}$ ; otherwise, we say $Q$ is a strong deformation of $P_{0}.$

The deformation cone of $P_{0}$ with respect to ( $E,G$ ), denoted by $\operatorname{Def}_{(E,G)}({P_{0}})$ , is the collection of all the deforming vectors $({\boldsymbol{a}},{\boldsymbol{b}})$ with respect to ( $E,G$ ).

Clearly, if we use a different minimal inequality description for $P_{0}$ with matrices $(E^{\prime},G^{\prime})$ , we will obtain a different deformation cone $\operatorname{Def}_{(E^{\prime},G^{\prime})}(P_{0})$ . However, one can check that $\operatorname{Def}_{(E^{\prime},G^{\prime})}(P_{0})$ can be obtained from $\operatorname{Def}_{(E,G)}(P_{0})$ via an invertible linear transformation. In this paper, we will fix a minimal linear inequality description for the family of polytopes we consider, and thus we will sometimes omit the subscript $(E,G)$ and just write $\operatorname{Def}(P_{0})$ .

Remark 2.2.

With a fixed minimal inequality description for $P_{0}$ , the tightness requirement of the description (2.3) for $Q$ in Definition 2.1 guarantees the uniqueness of the deforming vector $({\boldsymbol{a}},{\boldsymbol{b}})$ for any deformation $Q$ of $P_{0}$ , and establishes a one to one correspondence between deformations $Q$ of $P_{0}$ and deforming vectors $({\boldsymbol{a}},{\boldsymbol{b}})$ .

In particular, we want to emphasize that if $Q$ is a deformation of $P_{0}$ , its corresponding deforming vector is the unique vector $({\boldsymbol{a}},{\boldsymbol{b}})$ such that the description (2.3) is a tight linear inequality description.

Remark 2.3.

Recall that a polytope $Q_{1}\subset\mathbb{R}^{m}$ is a translation of another polytope $Q_{2}\subset\mathbb{R}^{m}$ if $Q_{1}=Q_{2}+\boldsymbol{t}$ for some $\boldsymbol{t}\in\mathbb{R}^{m}$ . It is easy to see that if $Q$ is a deformation of $P$ , then any translation of $Q$ is a deformation of $P$ .

The following lemma provides an alternative definition of deformations that will be used in our proofs. We use $\operatorname{Vert}(P)$ to denote the set of vertices of a polytope $P$ :

Lemma 2.4.

[24] Let $P_{0}$ and $Q$ be two polytopes in $\mathbb{R}^{m}$ . Then the following two statements are equivalent:

(1)

$Q$ is a deformation of $P_{0}$ .
(2)

There exists a surjective map $\phi$ from $\operatorname{Vert}(P_{0})$ to $\operatorname{Vert}(Q)$ satisfying that for any adjacent vertices ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ of $P_{0}$ , there exists $r_{{\boldsymbol{v}},{\boldsymbol{w}}}\in\mathbb{R}_{\geq 0}$ such that $\phi({\boldsymbol{v}})-\phi({\boldsymbol{w}})=r_{{\boldsymbol{v}},{\boldsymbol{w}}}({\boldsymbol{v}}-{\boldsymbol{w}})$ .

Moreover, suppose (2) is true, then $Q$ is a weak deformation of $P_{0}$ if all $r_{{\boldsymbol{v}},{\boldsymbol{w}}}$ ’s are positive and $Q$ is a strong deformation of $P_{0}$ if some of $r_{{\boldsymbol{v}},{\boldsymbol{w}}}$ ’s are zero.

Recall that the direction of a non-zero vector ${\boldsymbol{v}}$ is $\dfrac{{\boldsymbol{v}}}{\sqrt{\langle{\boldsymbol{v}},{\boldsymbol{v}}\rangle}}$ . For any two adjacent vertices ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ of a polytope, we call the vector ${\boldsymbol{w}}-{\boldsymbol{v}}$ the edge vector from ${\boldsymbol{v}}$ to ${\boldsymbol{w}}$ , and the direction of ${\boldsymbol{w}}-{\boldsymbol{v}}$ the edge direction from ${\boldsymbol{v}}$ to ${\boldsymbol{w}}$ . It is not explicitly stated in the above lemma, but when ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ are adjacent vertices of $P_{0}$ , the vertices $\phi({\boldsymbol{v}})$ and $\phi({\boldsymbol{w}})$ of $Q$ are either the same or adjacent. Moreover, when $\phi({\boldsymbol{v}})$ and $\phi({\boldsymbol{w}})$ are adjacent, the edge direction of $\phi({\boldsymbol{v}})$ and $\phi({\boldsymbol{w}})$ is the same as that of ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ .

In [6, Proposition 2.16], the authors gave connection between Definition 2.1 and the alternative definition of deformations provided by Lemma 2.4 which we summarize in the following lemma.

Lemma 2.5.

[6, Section 2] Let $Q$ be a deformation of $P_{0}$ with deforming vector $({\boldsymbol{a}},{\boldsymbol{b}})$ . Then, the map

\phi:\operatorname{Vert}(P_{0})\rightarrow\operatorname{Vert}(Q),

defined by $\phi({\boldsymbol{v}})={\boldsymbol{v}}_{({\boldsymbol{a}},{\boldsymbol{b}})}$ where ${\boldsymbol{v}}_{({\boldsymbol{a}},{\boldsymbol{b}})}$ is given as in Definition 2.1/(2) satisfies the condition given in Lemma 2.4/(2).

Connection to type cones

It is straightforward to verify that $Q$ is a weak deformation of $P_{0}$ if and only if $Q$ has the same normal fan as $P_{0}$ . Thus, in this case, we also say that $Q$ and $P_{0}$ are normally equivalent. In [17], McMullen introduced the concept of type cones of normally equivalent polytopes. We give its definition using the language developed in this paper.

Definition 2.6.

Assuming the hypothesis of $P_{0}$ given in Definition 2.1. The type cone of $P_{0}$ with respect to $(E,G),$ denoted by $\operatorname{TC}_{(E,G)}(P_{0})$ , is the collection of all the deforming vectors $({\boldsymbol{a}},{\boldsymbol{b}})$ for weak deformations of $P_{0}$ with respect to ( $E,G$ ).

Therefore, the type cone of $P_{0}$ containing the deformation vectors of all the polytopes that are normally equivalent to $P_{0}$ . Even though McMullen [17] did not introduce the terminology “deformation cone”, his analysis on type cones indicates the following connection between these two families of cones.

Lemma 2.7.

The relative interior of the deformation cone $\operatorname{Def}_{(E,G)}(P_{0})$ of $P_{0}$ is exactly the type cone $\operatorname{TC}_{(E,G)}(P_{0})$ of $P_{0}$ .

Furthermore, suppose $K$ is a face of the deformation cone $\operatorname{Def}_{(E,G)}(P_{0})$ of $P_{0}$ , and $Q$ is a deformation of $P_{0}$ corresponding to a deforming vector in the relative interior of $K$ . Then $K$ is exactly the deformation cone $\operatorname{Def}_{(E,G)}(Q)$ of $Q$ and hence the relative interior of $K$ is the type cone $\operatorname{TC}_{(E,G)}(Q)$ of $Q$ .

The following immediate consequence of the above lemma will be useful to us.

Corollary 2.8.

For $i=1,2$ , suppose $Q_{i}$ is a deformation of $P_{0}$ with the deforming vector $({\boldsymbol{a}}_{i},{\boldsymbol{b}}_{i})$ , and suppose $K_{i}$ is the (unique) face of $\operatorname{Def}_{(E,G)}(P_{0})$ such that $({\boldsymbol{a}}_{i},{\boldsymbol{b}}_{i})$ is in the relative interior of $K_{i}$ . Then $Q_{1}$ is a deformation of $Q_{2}$ if and only if $K_{1}$ is a face of $K_{2}$ . Moreover, $Q_{1}$ is normally equivalent to $Q_{2}$ if and only if $K_{1}=K_{2}$ .

2.3. Tesler polytopes

In this part, we formally introduce Tesler polytopes and provide necessary setup and notations to study the deformation cones of Tesler polytopes. We start by setting up the space that Tesler polytopes live in. Recall that the directed complete graph $\vec{K}_{n+1}$ is the graph on the vertex set $[n+1]=\{1,2,\dots,n+1\}$ in which there is an edge from the vertex $i$ to the vertex $j$ for all $1\leq i<j\leq n+1$ . For convenience, we use

E_{n+1}:=\{(i,j)~{}~{}|~{}~{}1\leq i<j\leq n+1\}

to represent the edge set of $\vec{K}_{n+1}$ . Let $\mathbb{U}(n)=\mathbb{R}^{E_{n+1}}$ . We will represent the elements $\boldsymbol{m}\in\mathbb{U}(n)$ as upper triangular matrices $(m_{i,j})$ in the following way: we use $m_{i,i}$ to denote the coordinate of $\boldsymbol{m}$ corresponding to the edge $(i,n+1)$ for each $1\leq i\leq n$ , and $m_{i,j}$ to denote the coordinate of $\boldsymbol{m}$ corresponding to the edge $(i,j)$ for each pair $1\leq i<j\leq n$ . Then for any $1\leq i\leq n$ , we define the $i$ -th hook sum of $\boldsymbol{m}\in\mathbb{U}(n)$ to be

\eta_{i}(\boldsymbol{m}):=m_{i,i}+\sum_{i<j}m_{i,j}-\sum_{j<i}m_{j,i}

and the hook sum vector of $\boldsymbol{m}$ to be $\eta(\boldsymbol{m})=(\eta_{1}(\boldsymbol{m}),\dots,\eta_{n}(\boldsymbol{m}))$ .

Example 2.9.

Let $\boldsymbol{m}=\begin{bmatrix}1&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&3\\ &{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}\\ &&10\\ \end{bmatrix}$ . The second hook sum of $\boldsymbol{m}$ is $\eta_{2}(\boldsymbol{m})={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}$ =7. One can see that the elements involved in $\eta_{2}(\boldsymbol{m})$ forms a hook in $\boldsymbol{m}$ . We can similarly compute the other two hook sums of $\boldsymbol{m}$ and the hook sum vector of $\boldsymbol{m}$ is $\eta(\boldsymbol{m})=(6,7,2)$

For any ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , we define the Tesler polytope of hook sum ${\boldsymbol{a}}$ to be

(2.4)

\operatorname{Tes}_{n}({\boldsymbol{a}}):=\biggl{\{}\boldsymbol{m}\in\mathbb{U}(n)~{}~{}\biggl{|}\begin{array}[]{c}\boldsymbol{\eta}(\boldsymbol{m})={\boldsymbol{a}},\\[5.69054pt] m_{i,j}\geq 0\text{ for }1\leq i\leq j\leq n\end{array}\biggl{\}}.

One sees that the condition $m_{n,n}\geq 0$ is implied by the conditions that $m_{i,n}\geq 0$ for each $1\leq i\leq n-1$ and that the $n$ -th hook sum $a_{n}$ is non-negative. Hence, the inequality $m_{n,n}\geq 0$ is redundant in the above description. Therefore, we use the following inequality description as the definition of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ :

(2.5)

\operatorname{Tes}_{n}({\boldsymbol{a}}):=\biggl{\{}\boldsymbol{m}=(m_{i,j})\in\mathbb{U}(n)~{}~{}\biggl{|}\begin{array}[]{c}\boldsymbol{\eta}(\boldsymbol{m})={\boldsymbol{a}},\\[5.69054pt] m_{i,j}\geq 0\text{ for }1\leq i\leq j\leq n\text{ where }(i,j)\neq(n,n)\end{array}\biggl{\}}.

2.3.1. Notations for Theorem 1.1

In order to describe deformation cones of Tesler polytopes (in Theorem 1.1), we need to express Tesler polytopes in the form of (2.2). Note that $\boldsymbol{m}\mapsto\boldsymbol{\eta}(\boldsymbol{m})$ is a linear transformation from $\mathbb{U}(n)$ to $\mathbb{R}^{n}$ . Let $L_{n}$ be the matrix associated with this linear transformation. More precisely, we can describe $L_{n}$ in the following way: $L_{n}$ can be obtained from removing the last row of the incidence matrix¹¹1Incidence matrix of a directed graph on $n+1$ nodes {1, 2, …, n+1} is a matrix $\rm{B}$ $=(b_{i,e})$ where $b_{i,e}=1$ if the vertex $i$ is the initial vertex of the edge $e$ , $b_{i,e}=-1$ if the vertex $i$ is the terminal vertex, and $b_{i,e}=0$ otherwise. of $\vec{K}_{n+1}$ . The columns of $L_{n}$ are indexed by $E_{n+1}$ . Hence, the row vectors of $L_{n}$ can be considered to be in $\mathbb{U}(n)$ . For any $\boldsymbol{m}\in\mathbb{U}(n)$ , we consider $L_{n}\boldsymbol{m}$ to be the vector whose $i$ -th entry is the dot product of the $i$ -th row of $L_{n}$ and $\boldsymbol{m}$ . With this notation, one can check that $\boldsymbol{\eta}(\boldsymbol{m})=L_{n}\boldsymbol{m}$ . Similarly, let $\psi$ be the projection that deletes $m_{n,n}$ for all $\boldsymbol{m}=(m_{i,j})\in\mathbb{U}(n)$ and let $P_{n}$ be the matrix associated with the map $\psi$ . Then the inequality description in (2.5) can be written as $\psi(\boldsymbol{m})\geq{\boldsymbol{0}}$ or equivalently, $-P_{n}\boldsymbol{m}\leq{\boldsymbol{0}}$ . Combining these together, we obtain a matrix description for $\operatorname{Tes}_{n}({\boldsymbol{a}})$ :

\operatorname{Tes}_{n}({\boldsymbol{a}})=\{\boldsymbol{m}\in\mathbb{U}(n)~{}~{}|~{}~{}L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-P_{n}\boldsymbol{m}\leq\boldsymbol{0}\},

It was shown in [16, Lemma 4.2] that for all ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}_{\geq 0}^{n}$ with $a_{1}>0$ , we have that $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a full dimensional polytope in the subspace of $\mathbb{U}(n)$ defined by $L_{n}\boldsymbol{m}={\boldsymbol{a}}$ . Furthermore, by [16, Corollary 4.6] that for all ${\boldsymbol{a}}\in\mathbb{R}_{>0}^{n}$ , we have that each inequality in $-P_{n}\boldsymbol{m}\leq\boldsymbol{0}$ defines a facet of $\operatorname{Tes}_{n}({\boldsymbol{a}}).$ Therefore, for ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ , the matrix description

(2.6)

L_{n}\boldsymbol{m}={\boldsymbol{a}}_{0}\text{ and }-P_{n}\boldsymbol{m}\leq\boldsymbol{0}

is a minimal linear inequality description for $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . Hence, The deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ studied in this paper and described in Theorem 1.1 is with respect to $(L_{n},-P_{n})$ .

Clearly, each deforming vector $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ lives in $\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n)$ , where $\widetilde{\mathbb{U}}(n)$ is the image of $\mathbb{U}(n)$ under the projection $\psi$ . One sees that the concept of $i$ -th hook sum of a matrix in $\widetilde{\mathbb{U}}(n)$ still makes sense as long as $i\neq n$ . Therefore, by abusing the notation, for any $1\leq i\leq n-1$ , we define the $i$ -th hook sum of $\tilde{{\boldsymbol{b}}}=(\tilde{b}_{i,j})\in\widetilde{\mathbb{U}}(n)$ to be

\eta_{i}(\tilde{{\boldsymbol{b}}}):=\tilde{b}_{i,i}+\sum_{i<j}\tilde{b}_{i,j}-\sum_{j<i}\tilde{b}_{j,i}.

2.4. Prior work on Tesler polytopes

In this part, we review definitions and results related to Tesler polytopes given in [18] and [16] that are relevant to this paper. Because we treat $\boldsymbol{m}\in\mathbb{U}(n)$ as an upper triangular matrix, we will talk about the $i$ -th row or $i$ -th column of $\boldsymbol{m}$ .

For any positive integer $n$ and ${\boldsymbol{a}}\in\mathbb{Z}_{\geq 0}^{n}$ , Mészáros, Morales and Rhoades [18] gave the characterization for the face poset of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ using the concept of support. Their characterization can be easily generalized to any ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ by the same proof.

Definition 2.10.

For any matrix $\boldsymbol{m}$ in $\mathbb{U}(n)$ , define the support of $\boldsymbol{m}$ , denoted by $\operatorname{supp}(\boldsymbol{m})$ , to be the matrix $(s_{i,j})\in\mathbb{U}(n)$ ,

\text{ where }s_{i,j}=\begin{cases}1,&\text{if the $(i,j)$-th entry of $\boldsymbol{m}$ is not zero,}\\ 0,&\text{otherwise.}\end{cases}

Let $\boldsymbol{m}$ and $\boldsymbol{m}^{\prime}$ be two matrices in $\mathbb{U}(n)$ . We write $\operatorname{supp}(\boldsymbol{m})\leq\operatorname{supp}(\boldsymbol{m}^{\prime})$ , if $\operatorname{supp}(\boldsymbol{m})=(a_{i,j})$ and $\operatorname{supp}(\boldsymbol{m}^{\prime})=(b_{i,j})$ satisfying $a_{i,j}\leq b_{i,j}$ for any $1\leq i\leq j\leq n$ .

For $1\leq i\leq j\leq n$ , let $H_{i,j}^{n}$ be the hyperplane consisting of $\boldsymbol{m}\in\mathbb{U}(n)$ whose $(i,j)$ -th entry is $0,$ that is,

(2.7)

H_{i,j}^{n}:=\{\boldsymbol{m}=(m_{l,k})\in\mathbb{U}(n)~{}~{}|~{}~{}m_{i,j}=0\}.

We say the intersection $H_{i_{1},j_{1}}^{n}\cap\cdots\cap H_{i_{k},j_{k}}^{n}$ does not make any zero rows if the intersection is not contained in $H_{i,i}^{n}\cap H_{i,i+1}^{n}\cap\cdots\cap H_{i,n}^{n}$ for any $1\leq i\leq n$ .

Theorem 2.11.

[18, Lemma 2.4] Suppose ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ and let ${\boldsymbol{v}}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ . Then ${\boldsymbol{v}}$ is a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ if and only if $\operatorname{supp}({\boldsymbol{v}})$ has at most one $1$ on each row. In particular, when ${\boldsymbol{a}}\in\mathbb{R}_{>0}^{n}$ , we have that ${\boldsymbol{v}}$ is a vertex in $\operatorname{Tes}_{n}({\boldsymbol{a}})$ if and only if each row of $\operatorname{supp}({\boldsymbol{v}})$ has exactly one $1$ .

Lemma 2.12.

[18, Lemmas 2.1 and 2.4] Let ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , and ${\boldsymbol{v}}$ be a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}}).$ If $\boldsymbol{u}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ satisfying $\operatorname{supp}(\boldsymbol{u})\leq\operatorname{supp}({\boldsymbol{v}})$ , then $\boldsymbol{u}={\boldsymbol{v}}.$

Recall that two vertices of a polytope are said to be adjacent if they are connected by an edge. The last two results of [18] we include here are a characterization for adjacent vertices of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ and a characterization for a specific type of vertex.

Lemma 2.13.

[18, Theorem 2.7] Let ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ . Two vertices ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ are adjacent if and only if for every $1\leq k\leq n$ , the $k$ -th row of $\operatorname{supp}({\boldsymbol{w}})$ can be obtained from the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ by exactly one of the following operations:

(O1)

Leaving the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ unchanged.
(O2)

Changing the unique $1$ in $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ to $0$ .
(O3)

Changing a single $0$ in the $k$ -th row to a $1$ (if $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ is a zero row).
(O4)

Moving the unique $1$ in the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ to a different position in the $k$ -th row (this operation must take place in precisely one row of $\operatorname{supp}({\boldsymbol{v}})$ ).

In particular, when ${\boldsymbol{a}}\in\mathbb{R}_{>0}^{n}$ , two vertices ${\boldsymbol{v}},{\boldsymbol{w}}$ are adjacent if and only if there exists a unique $k:1\leq k\leq n$ such that $supp({\boldsymbol{w}})$ is obtained from $supp({\boldsymbol{v}})$ by moving $1$ on the $k$ -th row to a different place on the same row.

Lemma 2.14.

[18, Lemma 2.4] Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}_{\geq 0}^{n}$ . The $k$ -th row of a vertex ${\boldsymbol{v}}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a zero row if and only if $a_{k}=0$ and the entries of $k$ -th column of ${\boldsymbol{v}}$ above the diagonal (excluding the diagonal entry) are all zero.

Example 2.15.

Let ${\boldsymbol{a}}=(2,2,3,4)$ , and

{\boldsymbol{v}}=\begin{pmatrix}0&2&0&0\\ &0&0&4\\ &&3&0\\ &&&8\\ \end{pmatrix}\text{ and }{\boldsymbol{w}}=\begin{pmatrix}0&0&2&0\\ &0&0&2\\ &&5&0\\ &&&6\\ \end{pmatrix}.

Then

\operatorname{supp}({\boldsymbol{v}})=\begin{pmatrix}0&1&0&0\\ &0&0&1\\ &&1&0\\ &&&1\\ \end{pmatrix}\text{ and }\operatorname{supp}({\boldsymbol{w}})=\begin{pmatrix}0&0&1&0\\ &0&0&1\\ &&1&0\\ &&&1\\ \end{pmatrix}.

Using Theorem 2.11, one can easily check that ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ are vertices of $\operatorname{Tes}_{4}(2,2,3,4)$ . Also, they are adjacent vertices, because $\operatorname{supp}({\boldsymbol{w}})$ can be obtained by moving 1 on the first row of $\operatorname{supp}({\boldsymbol{v}})$ to the right.

3. All Tesler polytopes are deformations of $\operatorname{Tes}_{n}({\boldsymbol{1}})$

The main goal of this section is to prove the following theorem:

Theorem 3.1.

Let ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ . Then for any ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}_{\geq 0}^{n}$ , the Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . More precisely, $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a weak deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ (equivalently, is normally equivalent to $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ ) if ${\boldsymbol{a}}\in\mathbb{R}_{>0}^{n-1}\times\mathbb{R}_{\geq 0}$ , and is a strong deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ if $a_{i}=0$ for some $1\leq i\leq n-1$ .

In particular, all Tesler polytopes $\operatorname{Tes}_{n}({\boldsymbol{a}})$ (for ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ ) are deformations of the Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{1}})$ .

Throughout this section, we use the alternative definition of deformations introduced in Lemma 2.4. We will utilize a machinery that was used in the proof of Lemma 2.4 in [18].

Definition 3.2.

Let ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ and ${\boldsymbol{v}}=(v_{i,j})$ be a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ .

(1)

Define $j_{{\boldsymbol{v}}}:\{0,1,2,\dots,n\}\longrightarrow\{0,1,2,\dots,n\}$ by

j_{{\boldsymbol{v}}}(k)=\begin{cases}0&\text{if $k=0$ or the $k$-th row of ${\boldsymbol{v}}$ is a zero row},\\ l&\text{if $k\neq 0$ and $v_{k,l}$ is the unique nonzero entry on the $k$-th row.}\end{cases}

(This is well-defined by Theorem 2.11).

(2)

Since ${\boldsymbol{v}}$ is upper triangular, the sequence $\{k,j_{{\boldsymbol{v}}}(k),j_{{\boldsymbol{v}}}^{2}(k),\dots\}$ is strictly increasing until it stabilizes. Assume that $q$ is the smallest integer such that $j_{{\boldsymbol{v}}}^{q-1}(k)=j_{{\boldsymbol{v}}}^{q}(k)$ . Define

\operatorname{Dep}_{{\boldsymbol{v}}}(k)=\{(k,j_{{\boldsymbol{v}}}(k)),(j_{{\boldsymbol{v}}}(k),j_{{\boldsymbol{v}}}^{2}(k)),\dots,(j_{{\boldsymbol{v}}}^{q-1}(k),j_{{\boldsymbol{v}}}^{q}(k))\}.

(3)

Let $D_{{\boldsymbol{v}}}(k)\in\mathbb{U}(n)$ be the upper triangular $\{0,1\}$ -matrix recording the positions appearing in $\operatorname{Dep}_{{\boldsymbol{v}}}(k)$ . More precisely,

D_{{\boldsymbol{v}}}(k):=(m_{i,j})\text{ where }m_{i,j}=\begin{cases}1,&\text{if }(i,j)\in\operatorname{Dep}_{{\boldsymbol{v}}}(k),\\ 0,&\text{if }(i,j)\notin\operatorname{Dep}_{{\boldsymbol{v}}}(k)\end{cases}.

The purpose of this definition is to describe the edge vector from a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ to one of its adjacent vertices.

Proposition 3.3.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}_{\geq 0}^{n}$ . Suppose ${\boldsymbol{v}}=(v_{i,j})$ and ${\boldsymbol{w}}=(w_{i,j})$ are adjacent vertices of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ , and suppose the first row that $\operatorname{supp}({\boldsymbol{v}})$ and $\operatorname{supp}({\boldsymbol{w}})$ differ is the $k$ -th row. Then

{\boldsymbol{w}}-{\boldsymbol{v}}=c(D_{{\boldsymbol{w}}}(k)-D_{{\boldsymbol{v}}}(k))

where $c\in\mathbb{R}_{>0}$ is the unique non-zero entry in the $k$ -th row of ${\boldsymbol{v}}$ (or that of ${\boldsymbol{w}}$ ).

Example 3.4.

Let ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ be as in Example 2.15. The supports of ${\boldsymbol{w}}$ and ${\boldsymbol{v}}$ differ at the $1$ st row already. Hence $k=1.$ We now compute $D_{{\boldsymbol{w}}}(k)-D_{{\boldsymbol{v}}}(k)=D_{{\boldsymbol{w}}}(1)-D_{{\boldsymbol{v}}}(1)$ :

D_{{\boldsymbol{w}}}(1)-D_{{\boldsymbol{v}}}(1)=\begin{pmatrix}0&0&1&0\\ &0&0&0\\ &&1&0\\ &&&0\end{pmatrix}-\begin{pmatrix}0&1&0&0\\ &0&0&1\\ &&0&0\\ &&&1\end{pmatrix}=\begin{pmatrix}0&-1&1&0\\ &0&0&-1\\ &&1&0\\ &&&-1\end{pmatrix}.

Next, we compute the edge vector from ${\boldsymbol{v}}$ to ${\boldsymbol{w}}$ directly:

{\boldsymbol{w}}-{\boldsymbol{v}}=\begin{pmatrix}0&0&2&0\\ &0&0&2\\ &&5&0\\ &&&6\end{pmatrix}-\begin{pmatrix}0&2&0&0\\ &0&0&4\\ &&3&0\\ &&&8\end{pmatrix}=2\begin{pmatrix}0&-1&1&0\\ &0&0&-1\\ &&1&0\\ &&&-1\end{pmatrix},

which is $2(D_{{\boldsymbol{w}}}(1)-D_{{\boldsymbol{v}}}(1))$ , agreeing with the assertion of Proposition 3.3.

We need two preliminary lemmas before proving Proposition 3.3.

Lemma 3.5.

Let ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ and ${\boldsymbol{v}}=(v_{i,j})\in\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}))$ . Suppose the $k$ -th row of ${\boldsymbol{v}}$ is a non-zero row, and $c$ is the non-zero entry in the $k$ -th row. Assume

\operatorname{Dep}_{{\boldsymbol{v}}}(k)=\{(k,j_{{\boldsymbol{v}}}(k)),(j_{{\boldsymbol{v}}}(k),j_{{\boldsymbol{v}}}^{2}(k)),\dots,(j_{{\boldsymbol{v}}}^{q-1}(k),j_{{\boldsymbol{v}}}^{q}(k))\}.

Then $D_{{\boldsymbol{v}}}(k)$ has the following properties:

(1)

$\boldsymbol{\eta}(D_{{\boldsymbol{v}}}(k))={\boldsymbol{e}}_{k}$ where ${\boldsymbol{e}}_{k}$ is the $k$ -th standard basis vector of $\mathbb{R}^{n}$ .
(2)

The entries of ${\boldsymbol{v}}-cD_{{\boldsymbol{v}}}(k)$ are all non-negative.

Proof.

For convenince, we use $d_{i,j}$ to denote the $(i,j)$ -th entry of $D_{{\boldsymbol{v}}}(k)$ .

By convention, we let $j_{{\boldsymbol{v}}}^{0}(k)=k.$ Then it follows from the definition of $\operatorname{Dep}_{{\boldsymbol{v}}}(k)$ that

1\leq j_{{\boldsymbol{v}}}^{0}(k)<j_{{\boldsymbol{v}}}^{1}(k)<j_{{\boldsymbol{v}}}^{2}(k)<\cdots<j_{{\boldsymbol{v}}}^{q-2}(k)<j_{{\boldsymbol{v}}}^{q-1}(k)=j_{{\boldsymbol{v}}}^{q}(k)\leq n.

Therefore, $d_{i,j}$ is $1$ if $(i,j)=(j_{{\boldsymbol{v}}}^{l-1}(k),j_{{\boldsymbol{v}}}^{l}(k))$ for some $l=1,2,\dots,q,$ and is $0$ otherwise. Clearly, if $i\neq j_{{\boldsymbol{v}}}^{l}(k)$ for some $l=0,1,\dots,q-1,$ then $\eta_{i}(D_{{\boldsymbol{v}}}(k))=0.$ If $i=j_{{\boldsymbol{v}}}^{l}(k)$ for some $l=1,2,\dots,q-1,$ then

\eta_{i}(D_{{\boldsymbol{v}}}(k))=\sum_{j\geq j_{{\boldsymbol{v}}}^{l}(k)}d_{j_{{\boldsymbol{v}}}^{l}(k),j}-\sum_{j<j_{{\boldsymbol{v}}}^{l}(k)}d_{j,j_{{\boldsymbol{v}}}^{l}(k)}=d_{j_{{\boldsymbol{v}}}^{l}(k),j_{{\boldsymbol{v}}}^{l+1}(k)}-d_{j_{{\boldsymbol{v}}}^{l-1}(k),j_{{\boldsymbol{v}}}^{l}(k)}=1-1=0.

If $i=k=j_{{\boldsymbol{v}}}^{0}(k),$ then

\eta_{i}(D_{{\boldsymbol{v}}}(k))=\eta_{k}(D_{{\boldsymbol{v}}}(k))=\sum_{j\geq k}d_{k,j}-\sum_{j<k}d_{j,k}=d_{k,j_{{\boldsymbol{v}}}^{1}(k)}=1.

Thus, $\boldsymbol{\eta}(D_{{\boldsymbol{v}}}(k))={\boldsymbol{e}}_{k}$ , i.e. Property (1) follows.

For Property (2), we first show that

(3.1)

v_{j_{{\boldsymbol{v}}}^{l-1}(k),j_{{\boldsymbol{v}}}^{l}(k)}\leq v_{j_{{\boldsymbol{v}}}^{l}(k),j_{{\boldsymbol{v}}}^{l+1}(k)},\quad\text{for any $l=1,2,\dots,q-1.$}

Since ${\boldsymbol{v}}\in\operatorname{Tes}_{n}({\boldsymbol{a}}),$ by the definition of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ , we have that all the entries in ${\boldsymbol{v}}$ are non-negative, and $\eta_{j_{{\boldsymbol{v}}}^{l}(k)}({\boldsymbol{v}})$ , the $j_{{\boldsymbol{v}}}^{l}(k)$ -th hook sum of ${\boldsymbol{v}}$ is non-negative. However,

\eta_{j_{{\boldsymbol{v}}}^{l}(k)}({\boldsymbol{v}})=\sum_{j\geq j_{{\boldsymbol{v}}}^{l}(k)}v_{j_{{\boldsymbol{v}}}^{l}(k),j}-\sum_{i<j_{{\boldsymbol{v}}}^{l}(k)}v_{i,j_{{\boldsymbol{v}}}^{l}(k)}.

Hence, (3.1) follows from the fact that $v_{j_{{\boldsymbol{v}}}^{l}(k),j_{{\boldsymbol{v}}}^{l+1}(k)}$ is the only positive element in the $j_{{\boldsymbol{v}}}^{l}(k)$ -th row of ${\boldsymbol{v}}.$ Given (3.1), we immediately have that

c=v_{k,j_{{\boldsymbol{v}}}(k)}\leq v_{j_{{\boldsymbol{v}}}^{l}(k),j_{{\boldsymbol{v}}}^{l+1}(k)},\quad\text{for any $l=1,2,\dots,q-1$.}

Thus, Property (2) follows. ∎

Lemma 3.6.

Let ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ . Suppose ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ are adjacent vertices of $\operatorname{Tes}_{n}({\boldsymbol{a}}),$ and suppose that the first row in which $\operatorname{supp}({\boldsymbol{v}})$ and $\operatorname{supp}({\boldsymbol{w}})$ differ is the $k$ -th row. Then the followings are true.

(1)

The first $k-1$ rows of ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ are the same.
(2)

The $k$ -th row is the (unique) row of $\operatorname{supp}({\boldsymbol{w}})$ that is obtained from that of $\operatorname{supp}({\boldsymbol{v}})$ by operation (O4) of Lemma 2.13. Furthermore, the unique non-zero entries in the $k$ -th rows of ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ are equal to one another.
(3)

Let $c$ be the non-zero entry in the $k$ -th row of ${\boldsymbol{w}}.$ For any $k\leq i\leq j\leq n,$ if $w_{i,j}\neq 0$ (or equivalently $w_{i,j}>0$ ) but $v_{i,j}=0$ , then we have that $(i,j)\in\operatorname{Dep}_{\boldsymbol{w}}(k)$ and $w_{i,j}=c.$

Proof.

By Theorem 2.11, each row of ${\boldsymbol{v}}$ has at most one non-negative entry. This implies that for any $i,$ the first $i$ rows of $\operatorname{supp}({\boldsymbol{v}})$ , together with the hook sum condition $\eta({\boldsymbol{v}})={\boldsymbol{a}},$ determine the first $i$ rows of ${\boldsymbol{v}}.$ The same thing holds for ${\boldsymbol{w}}.$ Therefore, since $\operatorname{supp}({\boldsymbol{v}})$ and $\operatorname{supp}({\boldsymbol{w}})$ agree at the first $k-1$ rows, we conclude that (1) is true.

Then using the fact that $\eta_{k}({\boldsymbol{w}})=a_{k}=\eta_{k}({\boldsymbol{v}})$ , we see that

(3.2)

\sum_{j=k}^{n}v_{k,j}=\sum_{j=k}^{n}w_{k,j}.

Since $\operatorname{supp}({\boldsymbol{v}})$ and $\operatorname{supp}({\boldsymbol{w}})$ differ at the $k$ -th row, the equation (3.2) implies that the only operation (among the four operations) listed in Lemma 2.13 that can be applied to the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}})$ to obtain that of $\operatorname{supp}({\boldsymbol{w}})$ is operation (O4). Thus, ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ each has exactly one non-zero entry in their $k$ -th row, but in different places. This together with (3.2) completes our proof for (2).

Finally, we prove (3) by induction on $i.$ Clearly, it holds when $i=k.$ Assume (3) holds for any $i:k\leq i<i_{0}$ for some $i_{0}\leq n,$ and we consider the cases when $i=i_{0}.$ One observes that the $i$ -th row of $\operatorname{supp}({\boldsymbol{w}})$ must be obtained from $\operatorname{supp}({\boldsymbol{v}})$ by operation (O3) of Lemma 2.13. Hence, the $i$ -th row of ${\boldsymbol{v}}$ is a zero row, and $w_{i,j}$ is the unique non-zero entry in the $i$ -th row of ${\boldsymbol{w}}.$ Applying Lemma 2.14 to ${\boldsymbol{v}}$ , we have that

a_{i}=0\quad\text{and}\quad v_{1,i}=v_{2,i}=\cdots=v_{i-1,i}=0.

Thus, $\eta_{i}({\boldsymbol{w}})=a_{i}=0$ , which implies that $w_{i,j}=\sum_{l=1}^{i-1}w_{l,i}.$ Since we have already shown (1) holds, we can rewrite this equality as

w_{i,j}=\sum_{l=k}^{i-1}w_{l,i}.

Let $L=\{k\leq l\leq i-1\ |\ w_{l,i}\neq 0\}.$ Because $w_{i,j}\neq 0,$ we have that $L\neq\emptyset.$ For any $l\in L,$ we have $w_{l,i}\neq 0$ and $v_{l,i}=0,$ and thus by the induction hypothesis $(l,i)\in\operatorname{Dep}_{\boldsymbol{w}}(k)$ and $w_{l,i}=c.$ However, it follows from the definition of $\operatorname{Dep}_{\boldsymbol{w}}(k)$ that no two pairs in $\operatorname{Dep}_{\boldsymbol{w}}(k)$ share the same second coordinates unless one of the pair is in the form of $(x,x).$ But $l<i$ for any $l\in L.$ We conclude that $L$ contains a unique element, say $l_{0}.$ Then clearly we have that $w_{i,j}=w_{l_{0},i}=c$ . Furthermore, since $(l_{0},i)\in\operatorname{Dep}_{\boldsymbol{w}}(k)$ , one verifies that $(i,j)\in\operatorname{Dep}_{\boldsymbol{w}}(k),$ completing our inductive proof. ∎

Proof of Proposition 3.3.

By Lemma 3.6/(2), we must have that the two non-zero entries in the $k$ -th rows of ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ agree, i.e., $v_{k,j_{{\boldsymbol{v}}}(k)}=w_{k,j_{{\boldsymbol{w}}}(k)}$ . Let

c:=v_{k,j_{{\boldsymbol{v}}}(k)}=w_{k,j_{{\boldsymbol{w}}}(k)}.

Then it follows from Lemma 3.5/(1) that $c\boldsymbol{\eta}(D_{{\boldsymbol{v}}}(k))=c\boldsymbol{\eta}(D_{{\boldsymbol{w}}}(k))=c{\boldsymbol{e}}_{k}$ . Thus, if we let

\boldsymbol{u}:={\boldsymbol{w}}+cD_{{\boldsymbol{v}}}(k)-cD_{{\boldsymbol{w}}}(k),

then $\boldsymbol{\eta}(\boldsymbol{u})=\boldsymbol{\eta}({\boldsymbol{w}})={\boldsymbol{a}}.$ Also, by Lemma 3.5/(2), the entries of ${\boldsymbol{w}}-cD_{{\boldsymbol{w}}}(k)$ are non-negative which implies that the entries of $\boldsymbol{u}=\left({\boldsymbol{w}}-cD_{{\boldsymbol{w}}}(k)\right)+cD_{{\boldsymbol{v}}}(k)$ are non-negative as well. Therefore, we conclude that $\boldsymbol{u}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ . It is left to show that $\boldsymbol{u}={\boldsymbol{v}},$ which by Lemma 2.12 can be reduced to showing $\operatorname{supp}(\boldsymbol{u})\leq\operatorname{supp}({\boldsymbol{v}})$ . Since $D_{{\boldsymbol{v}}}(k)$ and ${\boldsymbol{w}}-cD_{{\boldsymbol{w}}}(k)$ have non-negative entries, one sees that showing $\operatorname{supp}(\boldsymbol{u})\leq\operatorname{supp}({\boldsymbol{v}})$ is equivalent to showing the following two statements:

(i)

$\operatorname{supp}(cD_{{\boldsymbol{v}}}(k))\leq\operatorname{supp}({\boldsymbol{v}})$ , and
(ii)

$\operatorname{supp}({\boldsymbol{w}}-cD_{\boldsymbol{w}}(k))\leq\operatorname{supp}({\boldsymbol{v}}).$

We see that (i) follows directly from the definition of $D_{{\boldsymbol{v}}}(k)$ .

By Lemma 3.6/(1) and the definition of $D_{\boldsymbol{w}}(k)$ , one sees that the first $k-1$ rows of ${\boldsymbol{w}}-cD_{{\boldsymbol{w}}}(k)$ are the same as that of ${\boldsymbol{v}},$ and the $k$ -th row of ${\boldsymbol{w}}-cD_{\boldsymbol{w}}(k)$ is a zero row. One sees that in order to finish proving (ii), it is sufficient to show that for any $k<i\leq j\leq n,$ if $w_{i,j}\neq 0,$ then either $v_{i,j}\neq 0$ or the $(i,j)$ -th entry of ${\boldsymbol{w}}-cD_{\boldsymbol{w}}(k)$ is $0.$ However, if $w_{i,j}\neq 0$ and $v_{i,j}=0,$ it follows from Lemma 3.6/(3) that $w_{i,j}=c$ , and thus the $(i,j)$ -th entry of ${\boldsymbol{w}}-cD_{\boldsymbol{w}}(k)$ is $0,$ completing the proof. ∎

We need one more lemma before proving the result of this section.

Lemma 3.7.

Let ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ and ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ . Then for any ${\boldsymbol{v}}\in\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ , there exists a unique ${\boldsymbol{v}}^{\prime}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ such that $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{v}})$ . Furthermore, this unique ${\boldsymbol{v}}^{\prime}$ is a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}}).$

Proof.

Because ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ , by Theorem 2.11, each row of $\operatorname{supp}({\boldsymbol{v}})$ has exactly one $1$ . Let $S:=\{(i,j_{i})\ |\ 1\leq i\leq n\}$ be the set of indices of the entries in $\operatorname{supp}({\boldsymbol{v}})$ that are $1.$ It is easy to see that there exists a unique solution ${\boldsymbol{v}}^{\prime}=(v^{\prime}_{i,j})\in\mathbb{U}(n)$ satisfying

\boldsymbol{\eta}({\boldsymbol{v}}^{\prime})={\boldsymbol{a}}\quad\text{ and }\quad v^{\prime}_{i,j}=0\ \text{for every }(i,j)\not\in S.

Note that the condition $v^{\prime}_{i,j}=0$ for every $(i,j)\not\in S$ is equivalent to the condition $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{v}}).$ Hence, the first assertion of the lemma follows.

Since $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{v}})$ implies that there is at most one non-zero entry in each row of ${\boldsymbol{v}}^{\prime}$ , by Theorem 2.11, ${\boldsymbol{v}}^{\prime}$ has to be a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ . ∎

Now, we are ready to prove our main result of this section.

Proof of Theorem 3.1.

We prove the theorem using Lemma 2.4. For any vertex ${\boldsymbol{v}}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ , we let $\phi({\boldsymbol{v}})$ be the unique point/vertex ${\boldsymbol{v}}^{\prime}$ in $\operatorname{Tes}_{n}({\boldsymbol{a}})$ satisfying $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{v}})$ asserted by Lemma 3.7. Hence, $\phi$ is a well-defined map from $\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ to $\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}))$ .

For any vertex ${\boldsymbol{v}}^{\prime}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}})$ , it follows from Theorem 2.11 that there exists a $\{0,1\}$ -matrix $\boldsymbol{m}\in\mathbb{U}(n)$ such that each row of $\boldsymbol{m}$ has exactly one $1$ and $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\boldsymbol{m}.$ Applying Theorem 2.11 again, there exists a vertex ${\boldsymbol{v}}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ such that $\operatorname{supp}({\boldsymbol{v}})=\boldsymbol{m}.$ Therefore, the surjectivity of $\phi$ follows.

Assume that ${\boldsymbol{v}}$ and ${\boldsymbol{w}}$ are adjacent vertices of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ where their support only differ in the $k$ -th row. Let ${\boldsymbol{v}}^{\prime}=\phi({\boldsymbol{v}})$ and ${\boldsymbol{w}}^{\prime}=\phi({\boldsymbol{w}})$ . In order to apply Lemma 2.4, we need to show that there exists $r_{{\boldsymbol{v}},{\boldsymbol{w}}}\in\mathbb{R}_{\geq 0}$ such that

{\boldsymbol{w}}^{\prime}-{\boldsymbol{v}}^{\prime}=r_{{\boldsymbol{w}},{\boldsymbol{v}}}({\boldsymbol{w}}-{\boldsymbol{v}}).

We consider two cases below.

Case 1

Suppose the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}}^{\prime})$ or that of $\operatorname{supp}({\boldsymbol{w}}^{\prime})$ is a zero row. Without loss of generality, assume that the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}}^{\prime})$ is a zero row. Then since $\operatorname{supp}({\boldsymbol{v}})$ and $\operatorname{supp}({\boldsymbol{w}})$ only differs in the $k$ -th row, $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{w}})$ . Thus, it follows from Lemma 3.7 and the constrution of $\phi$ that ${\boldsymbol{v}}^{\prime}={\boldsymbol{w}}^{\prime}$ . Therefore, we can choose $r_{{\boldsymbol{v}},{\boldsymbol{w}}}=0$ .

Case 2

Suppose neither the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}}^{\prime})$ nor that of $\operatorname{supp}({\boldsymbol{w}}^{\prime})$ is a zero row.

Let ${\boldsymbol{v}}^{\prime}=(v^{\prime}_{i,j})$ , and $v^{\prime}_{k,l}$ be the (unique) non-zero entry in the $k$ -th row of $\operatorname{supp}({\boldsymbol{v}}^{\prime}).$ Because $\operatorname{supp}({\boldsymbol{v}}^{\prime})\leq\operatorname{supp}({\boldsymbol{v}})$ , clearly we have $j_{{\boldsymbol{v}}}(k)=l=j_{{\boldsymbol{v}}^{\prime}}(k)$ . Next, because $v^{\prime}_{k,l}\neq 0,$ it follows from Lemma 2.14 that the $l$ -th row of ${\boldsymbol{v}}^{\prime}$ is a non-zero row. Using the same argument as above, we get $j_{{\boldsymbol{v}}}(l)=j_{{\boldsymbol{v}}^{\prime}}(l),$ or equivalently, $j_{{\boldsymbol{v}}^{\prime}}^{2}(k)=j_{{\boldsymbol{v}}}^{2}(k)$ . By iterating this process, we obtain $j_{{\boldsymbol{v}}^{\prime}}^{s}(k)=j_{{\boldsymbol{v}}}^{s}(k)$ for any integer $s\geq 0$ . Therefore, $\operatorname{Dep}_{{\boldsymbol{v}}^{\prime}}(k)=\operatorname{Dep}_{{\boldsymbol{v}}}(k)$ or equivalently, $D_{{\boldsymbol{v}}^{\prime}}(k)=D_{{\boldsymbol{v}}}(k)$ .

Similarly, we obtain $D_{{\boldsymbol{w}}^{\prime}}(k)=D_{{\boldsymbol{w}}}(k)$ . By Proposition 3.3,

{\boldsymbol{w}}-{\boldsymbol{v}}=c(D_{{\boldsymbol{w}}}(k)-D_{{\boldsymbol{v}}}(k))\text{ and }{\boldsymbol{w}}^{\prime}-{\boldsymbol{v}}^{\prime}=d(D_{{\boldsymbol{w}}^{\prime}}(k)-D_{{\boldsymbol{v}}^{\prime}}(k))

where $c$ and $d$ are the unique non-zero (positive) entries of ${\boldsymbol{v}}$ and ${\boldsymbol{v}}^{\prime}$ respectively. Therefore, we can take $r_{{\boldsymbol{w}},{\boldsymbol{v}}}=\dfrac{d}{c}$ .

In particular, when ${\boldsymbol{a}}\in\mathbb{R}_{>0}^{n-1}\times\mathbb{R}_{\geq 0}$ , $r_{{\boldsymbol{w}},{\boldsymbol{v}}}$ is always positive because Case 1 does not happen. However, when some of $a_{i}$ where $1\leq i\leq n-1$ are zero, one can easily see that Case 1 does happen which means the corresponding $r_{{\boldsymbol{w}},{\boldsymbol{v}}}$ ’s are zero. This completes our proof. ∎

We have proved Theorem 3.1 using the alternative definition of deformations given in Lemma 2.4. Below we will make a connection to the language used in Definition 2.1, i.e., the original definition of deformations we introduced. Recall that for ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n},$ the matrix description (2.6) is a minimal linear description for $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}).$ Therefore, it is natural to ask for ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , what the deforming vector for $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is.

Lemma 3.8.

Suppose ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ and ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ . Then the system of linear inequalities

(3.3)

L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-P_{n}\boldsymbol{m}\leq\boldsymbol{0}

is a tight linear inequality description for the non-empty Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{a}}).$ Hence, $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ with deforming vector $({\boldsymbol{a}},{\boldsymbol{0}})$ with respect to $(L_{n},-P_{n})$ .

Proof.

We already know that the system of linear equalities (3.3) defines the non-empty polytope $\operatorname{Tes}_{n}({\boldsymbol{a}}).$ Hence, we only need to show the tightness part of the first assertion of the lemma. Note that $-P_{n}\boldsymbol{m}\leq{\boldsymbol{0}}$ is the same as

m_{i,j}\geq 0\text{ for }1\leq i\leq j\leq n\text{ where }(i,j)\neq(n,n).

So we need to show that for every $1\leq i\leq j\leq n$ with $(i,j)\neq(n,n)$ , there exists a point $\boldsymbol{m}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ such that $m_{i,j}=0.$ We construct two points ${\boldsymbol{m}}^{1}=(m_{i,j}^{1})$ and ${\boldsymbol{m}}^{2}=(m_{i,j}^{2})$ where

m^{1}_{i,j}=\begin{cases}a_{i},&\text{if $i=j$},\\ 0,&\text{otherwise};\end{cases}\quad\text{ and }\quad m^{2}_{i,j}=\begin{cases}\sum_{l=1}^{i}a_{l},&\text{if $j=i+1$,}\\ \sum_{l=1}^{n}a_{l},&\text{if $(i,j)=(n,n)$},\\ 0&\text{otherwise}.\end{cases}

It is straightforward to verify that $\boldsymbol{m}^{1},\boldsymbol{m}^{2}\in\operatorname{Tes}_{n}({\boldsymbol{a}})$ . By definition, $m^{1}_{i,j}=0$ for all $1\leq i<j\leq n$ and $m^{2}_{i,i}=0$ for all $1\leq i\leq n-1.$ Therefore, the first assertion follows.

Finally, by Theorem 3.1, we already know that $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}).$ Thus, the second assertion follows from the first assertion and Remark 2.2. ∎

We finish this section by stating a generalization of Theorem 3.1, in response to a question asked by an anonymous referee. For each ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , we define $\mathcal{I}({\boldsymbol{a}})=\{i\in[n-1]\ |\ a_{i}>0\}$ to be the set of indices in $[n-1]$ such that $a_{i}$ is nonzero. Note that we do not care about whether $a_{n}$ is zero or not.

Theorem 3.9.

Let ${\boldsymbol{a}},{\boldsymbol{b}}\in\mathbb{R}_{\geq 0}^{n}$ . Then $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{b}})$ if $\mathcal{I}({\boldsymbol{a}})\subseteq\mathcal{I}({\boldsymbol{b}})$ . Moreover, $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is normally equivalent to $\operatorname{Tes}_{n}({\boldsymbol{b}})$ if $\mathcal{I}({\boldsymbol{a}})=\mathcal{I}({\boldsymbol{b}})$ .

One sees that Theorem 3.1 is a special case of Theorem 3.9 when taking ${\boldsymbol{b}}\in\mathbb{R}_{>0}^{n}$ . It is possible to revise our proof for Theorem 3.1 to give a proof for Theorem 3.9. However, the arguments will be much more complicated. Instead, we will prove Theorem 3.9 in the next section as a consequence of Theorem 1.1 and Corollary 2.8.

4. The deformation cone of Tesler polytopes

In this section, we give a proof for Theorem 1.1, which describes the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ for ${\boldsymbol{a}}_{0}\in\mathbb{R}^{n}_{>0}$ , and then prove Theorem 3.9 by applying Corollary 2.8. In order to prove Theorem 1.1, we need the following preliminary lemma. Recall that $\widetilde{\mathbb{U}}(n)$ is the image of $\mathbb{U}(n)$ under the projection which deletes the $(n,n)$ -th entry. For convenience, for any $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n)$ , where ${\boldsymbol{a}}=(a_{1},\dots,a_{n})$ and $\tilde{{\boldsymbol{b}}}=(\tilde{b}_{i,j})$ , let

(4.1)

Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}}):=\{\boldsymbol{m}\in\mathbb{U}(n)~{}~{}|~{}~{}L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-P_{n}\boldsymbol{m}\leq\tilde{{\boldsymbol{b}}}\}.

Note that for arbitrary choices of $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ , the above linear inequality description might not be tight.

Lemma 4.1.

Let ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}$ . Suppose $Q$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ with deforming vector $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ . (Thus, $Q=Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ and $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ .) Then the following statements are true:

(1)

For any ${\boldsymbol{v}}\in\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ , there exists a unique ${\boldsymbol{v}}^{\prime}=(v^{\prime}_{i,j})\in\operatorname{Vert}(Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}}))$ such that for all $1\leq i\leq j\leq n$ where $(i,j)\neq(n,n)$ if $v_{i,j}=0$ then $v^{\prime}_{i,j}=-\tilde{b}_{i,j}$ .
(2)

Let $\phi$ be a map from $\operatorname{Vert}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ to $\operatorname{Vert}(Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}}))$ defined by $\phi({\boldsymbol{v}})={\boldsymbol{v}}^{\prime}$ where ${\boldsymbol{v}}^{\prime}$ is the unique vertex assumed by part (1) above. Then for any pair of adjacent vertices ${\boldsymbol{v}}_{1}$ and ${\boldsymbol{v}}_{2}$ of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ , there exists a non-negative real number $r$ such that $\phi({\boldsymbol{v}}_{1})-\phi({\boldsymbol{v}}_{2})=r({\boldsymbol{v}}_{1}-{\boldsymbol{v}}_{2})$ , i.e, $\phi$ satisfies the condition described in Lemma 2.4/(2).

Proof.

Let ${\boldsymbol{v}}$ be a vertex of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}).$ Recall that (2.6) is a minimal linear inequality description for $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ which means that each inequality in $-P_{n}\boldsymbol{m}\leq\boldsymbol{0}$ is facet-defining. Hence, the set of facets of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ containing ${\boldsymbol{v}}$ is

\{H_{i,j}^{n}\cap\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})~{}~{}|~{}~{}v_{i,j}=0\}.

By Definition 2.1/(2), the vertex ${\boldsymbol{v}}_{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})}$ of $Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ is the unique point ${\boldsymbol{v}}^{\prime}$ satisfying the desired condition in (1). Then, the second part follows from Lemma 2.5. ∎

We describe a procedure of obtaining ${\boldsymbol{v}}^{\prime}=\phi({\boldsymbol{v}})$ from ${\boldsymbol{v}}$ in the following example.

Example 4.2.

Let ${\boldsymbol{a}}_{0}=(1,1,1,1)$ , ${\boldsymbol{a}}=(8,7,8,1),$ and

\tilde{{\boldsymbol{b}}}:=\begin{bmatrix}-1&2&-3&-4\\ &-5&6&7\\ &&-8&9\end{bmatrix}.

By using Theorem 1.1, one can check that $Q=Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{1}})$ with deforming vector $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ . Let

{\boldsymbol{v}}:=\begin{bmatrix}0&1&0&0\\ &0&2&0\\ &&3&0\\ &&&1\\ \end{bmatrix}

which is a vertex of $\operatorname{Tes}_{n}(\boldsymbol{1})$ . By the proof of Lemma 4.1, we know that ${\boldsymbol{v}}^{\prime}=\phi({\boldsymbol{v}})$ is defined to be ${\boldsymbol{v}}_{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})}$ . Hence, we can find ${\boldsymbol{v}}^{\prime}$ in the following way: We first change zero entries in ${\boldsymbol{v}}$ to corresponding $-\tilde{b}_{i,j}$ ’s and change the four non-zero entries to undetermined variables $w,x,y,z$ :

{\boldsymbol{v}}=\begin{bmatrix}0&1&0&0\\ &0&2&0\\ &&3&0\\ &&&1\end{bmatrix}\quad\rightarrow\quad{\boldsymbol{v}}^{\prime}:=\begin{bmatrix}1&w&3&4\\ &5&x&-7\\ &&y&-9\\ &&&z\end{bmatrix}.

We then use the hook sum conditions for $Q$ to determine $w,x,y,z$ :

\begin{cases}\eta_{1}({\boldsymbol{v}}^{\prime})=1+w+3+4=8\\ \eta_{2}({\boldsymbol{v}}^{\prime})=5+x+(-7)-w=7\\ \eta_{3}({\boldsymbol{v}}^{\prime})=y+(-9)-(x+3)=8\\ \eta_{4}({\boldsymbol{v}}^{\prime})=z-((-9)+(-7)+4)=1\end{cases}\ \ \implies\ \ \begin{cases}w=0\\ x=9\\ y=29\\ z=-11\\ \end{cases}\ \ \implies\ \ {\boldsymbol{v}}^{\prime}=\begin{bmatrix}1&0&3&4\\ &5&9&-7\\ &&29&-9\\ &&&-11\end{bmatrix}.

Proof of Theorem 1.1.

Thanks to Theorem 3.1, without loss of generality, we can assume that ${\boldsymbol{a}}_{0}=\boldsymbol{1}$ . Let

A:=\{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n))~{}~{}|~{}~{}\eta_{i}(\tilde{{\boldsymbol{b}}})\geq-a_{i}\text{ for all }1\leq i\leq n-1\}.

We will show that $\operatorname{Def}(\operatorname{Tes}_{n}(\boldsymbol{1}))=A$ by showing two-sided inclusion.

We first show that $\operatorname{Def}(\operatorname{Tes}_{n}(\boldsymbol{1}))\subseteq A$ . Suppose $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\operatorname{Def}(\operatorname{Tes}_{n}(\boldsymbol{1}))$ . Let $I$ be the $n\times n$ identity matrix and $\phi$ be the map described in Lemma 4.1. It is clear that $I$ is a vertex of $\operatorname{Tes}_{n}(\boldsymbol{1})$ by Theorem 2.11. Let ${\boldsymbol{w}}=\phi(I)$ be the vertex of $Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ corresponding to $I$ . Then, by Lemma 4.1, we have that

w_{i,j}=-\tilde{b}_{i,j},\quad\text{for all $1\leq i<j\leq n$},

and $w_{i,i}$ ’s can be determined using hook sum conditions:

w_{1,1}-\tilde{b}_{1,2}-\cdots-\tilde{b}_{1,n}=a_{1},

(w_{i,i}-\tilde{b}_{i,i+1}-\cdots-\tilde{b}_{i,n})-(-\tilde{b}_{1,i}-\cdots-\tilde{b}_{i-1,i})=a_{i},\quad 2\leq i\leq n.

From the above equations, we obtain

w_{i,i}=\eta_{i}(\tilde{{\boldsymbol{b}}})-\tilde{b}_{i,i}+a_{i}\quad\text{for all $1\leq i\leq n$.}

Since ${\boldsymbol{w}}\in Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ , we have inequalities $w_{i,i}\geq-\tilde{b}_{i,i}$ for all $1\leq i\leq n-1$ which implies that $\eta_{i}(\tilde{{\boldsymbol{b}}})\geq-a_{i}$ for all $1\leq i\leq n-1$ . Therefore, $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in A$ .

Next we show that $A\subseteq\operatorname{Def}(\operatorname{Tes}_{n}(\boldsymbol{1}))$ . Assume that $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in A$ and let $Q:=Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ . We will show that $Q$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{1}})$ with deforming vector $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ . Since $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in A$ , we have $(\eta_{1}(\tilde{{\boldsymbol{b}}})+a_{1},\dots,\eta_{n-1}(\tilde{{\boldsymbol{b}}})+a_{n-1},0)\in\mathbb{R}_{\geq 0}^{n}$ . Therefore, it follows from Lemma 3.8 that

(4.2)

T:=\biggl{\{}\boldsymbol{m}\in\mathbb{U}(n)~{}~{}\biggl{|}\begin{array}[]{c}L_{n}\boldsymbol{m}=(\eta_{1}(\tilde{{\boldsymbol{b}}})+a_{1},\dots,\eta_{n-1}(\tilde{{\boldsymbol{b}}})+a_{n-1},0)\\[5.69054pt] -P_{n}\boldsymbol{m}\leq{\boldsymbol{0}}\end{array}\biggl{\}}

is a non-empty Tesler polytope and the linear inequality description above is tight. Let ${\boldsymbol{b}}\in\mathbb{U}(n)$ be the upper triangular matrix obtained from $\tilde{{\boldsymbol{b}}}$ by appending $\displaystyle\sum_{i=1}^{n-1}\tilde{b}_{i,n}-a_{n}$ as its $(n,n)$ th-entry. Then

L_{n}{\boldsymbol{b}}=\boldsymbol{\eta}({\boldsymbol{b}})=(\eta_{1}(\tilde{{\boldsymbol{b}}}),\dots,\eta_{n-1}(\tilde{{\boldsymbol{b}}}),-a_{n})\text{ and }-P_{n}{\boldsymbol{b}}=-\tilde{{\boldsymbol{b}}}.

It immediately follows that $Q=T-{\boldsymbol{b}}$ , is a translation of the Tesler polytope $T$ . By Theorem 3.1, the polytope $T$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{1}})$ , thus so is $Q$ by Remark 2.3. Moreover, one sees that the linear inequality description (4.1) for $Q$ is precisely obtained from the linear inequality description (4.2) for $T$ by translating $\boldsymbol{m}$ to $\boldsymbol{m}-{\boldsymbol{b}}$ . Therefore, the tightness of (4.1) follows from the tightness of (4.2). Hence, we conclude that $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\operatorname{Def}(\operatorname{Tes}_{n}(\boldsymbol{1}))$ , completing the proof of the first assertion of the theorem.

Finally, as we have shown above, for any $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in A$ , the polytope $Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ is a translation of a Tesler polytope. Hence, the second statement of the theorem follows. ∎

We now proceed to prove Theorem 3.9. For all the discussion in the rest of this section, we assume ${\boldsymbol{a}}_{0}\in\mathbb{R}_{>0}^{n}.$ As we mentioned in the introduction each inequality in the description (1.1) for $\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ defines a facet, but we have more than that:

Lemma 4.3.

For each $I\subseteq[n-1]$ , let

F_{I}:=\left\{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n)~{}~{}\left|~{}~{}\begin{array}[]{c}\eta_{i}(\tilde{{\boldsymbol{b}}})\geq-a_{i}\text{ for all $i\in I$}\\ \eta_{i}(\tilde{{\boldsymbol{b}}})=-a_{i}\text{ for all $i\in[n-1]\setminus I$}\end{array}\right.\right\}

be a face of $\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ . Then $I\mapsto F_{I}$ is an inclusion-preserving bijection from subsets $I$ of $[n-1]$ and faces of $\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ .

Furthermore, for any ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , we have that $\mathcal{I}({\boldsymbol{a}})=I$ if and only if $({\boldsymbol{a}},{\boldsymbol{0}})$ is in the relative interior of $F_{I}$ .

Proof.

It follows from the definition of $F_{I}$ that $I\subseteq J$ if and only if $F_{I}\subseteq F_{J}$ . It is also clearly, every face of $\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ arises as an $F_{I}$ for some $I$ . So in order to prove the first conclusion, it is left to show that if $I\subsetneq J$ , then $F_{I}\neq F_{J}$ . However, notice that if $\mathcal{I}({\boldsymbol{a}})=I$ , then $({\boldsymbol{a}},{\boldsymbol{0}})$ belongs to the set

(4.3)

\left\{({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})\in\mathbb{R}^{n}\times\widetilde{\mathbb{U}}(n)~{}~{}\left|~{}~{}\begin{array}[]{c}\eta_{i}(\tilde{{\boldsymbol{b}}})>-a_{i}\text{ for all $i\in I$}\\ \eta_{i}(\tilde{{\boldsymbol{b}}})=-a_{i}\text{ for all $i\in[n-1]\setminus I$}\end{array}\right.\right\},

which is a subset of $F_{I}$ but clearly has no intersection with $F_{J}$ if $I\subsetneq J$ . Therefore, we conclude that $I\mapsto F_{I}$ is indeed an inclusion-preserving bijection from subsets $I$ of $[n-1]$ and faces of $\operatorname{Def}(\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}))$ .

Next, we observe that the above discussion implies that (4.3) actually is the relataive interior of $F_{I}$ . Then the second conslusion follows. ∎

Proof of Theorem 3.9.

By Lemma 3.8, the Tesler polytope $\operatorname{Tes}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ with deforming vector $({\boldsymbol{a}},{\boldsymbol{0}})$ . Hence, the conclusion follows from Lemma 4.3 and Corollary 2.8. ∎

5. Flow polytopes that are deformations of Tesler polytopes

The goal of this subsection is to prove Theorem 1.2 which is a result about flow polytopes. We start by giving a formal definition of flow polytopes on the directed complete graph $\vec{K}_{n+1}$ . Recall that $\vec{K}_{n+1}$ is the directed complete graph on the set of vertices $[n+1]$ with edge set $E_{n+1}$ . A flow on $\vec{K}_{n+1}$ is a function $f:E_{n+1}\rightarrow\mathbb{R}_{\geq 0}$ that assigns a non-negative real number to each edge of $\vec{K}_{n+1}$ . Given a flow $f$ , the net flow of $f$ on vertex $i$ is defined to be

f^{i}:=\displaystyle\sum_{j>i}f(i,j)-\sum_{j<i}f(j,i),\qquad\text{ for all }1\leq i\leq n+1.

Note that $f^{n+1}=-\sum_{1\leq i\leq n}f^{i}$ . Therefore, we often neglect the net flow on the vertex $n+1$ , and only discuss net flows on other vertices.

Definition 5.1.

For ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in\mathbb{R}^{n}$ , the flow polytope on $\vec{K}_{n+1}$ with net flow ${\boldsymbol{a}}$ is defined to be

\operatorname{Flow}_{n}({\boldsymbol{a}})=\{f:E_{n+1}\rightarrow\mathbb{R}_{\geq 0}~{}~{}|~{}~{}f^{i}=a_{i}\text{ for all }1\leq i\leq n\}.

Since $\mathbb{U}(n)=\mathbb{R}^{E_{n+1}}$ , any flow $f$ on $\vec{K}_{n+1}$ can be considered as an element in $\mathbb{U}(n)$ . Therefore, we have a natural correspondence between elements in $\mathbb{U}(n)$ and flows on $\vec{K}_{n+1}.$

Example 5.2.

Let $\boldsymbol{m}\in\mathbb{U}(3)$ be the same upper triangular matrix as in Example 2.9. The picture below shows $\boldsymbol{m}$ together with its corresponding flow $f$ on $\vec{K}_{4}$ . Note that on the right, the number on each edge $e$ is the number $f(e)$ assigned to $e,$ and the number below each vertex $i$ is the net flow $f^{i}$ of $f$ on $i.$

$\boldsymbol{m}=\begin{bmatrix}1&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&3\\ &{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}\\ &&10\\ \end{bmatrix}\quad\longleftrightarrow\quad\raisebox{-30.00005pt}{ \leavevmode\hbox to146.86pt{\vbox to67.01pt{\pgfpicture\makeatletter\hbox{\hskip 9.01958pt\lower-22.6086pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} \par\par\par{{}}{{}} {{{}{}{{}}{}}}{{{}}}{{{{}}{{}}}}{{}}{{{ }}}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{1.69717pt}{0.0pt}\pgfsys@curveto{1.69717pt}{0.93733pt}{0.93733pt}{1.69717pt}{0.0pt}{1.69717pt}\pgfsys@curveto{-0.93733pt}{1.69717pt}{-1.69717pt}{0.93733pt}{-1.69717pt}{0.0pt}\pgfsys@curveto{-1.69717pt}{-0.93733pt}{-0.93733pt}{-1.69717pt}{0.0pt}{-1.69717pt}\pgfsys@curveto{0.93733pt}{-1.69717pt}{1.69717pt}{-0.93733pt}{1.69717pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.68657pt}{-16.72333pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-11.37314pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-5.68657pt}\pgfsys@curveto{5.48657pt}{-2.65639pt}{3.03018pt}{-0.2pt}{0.0pt}{-0.2pt}\pgfsys@curveto{-3.03018pt}{-0.2pt}{-5.48657pt}{-2.65639pt}{-5.48657pt}{-5.68657pt}\pgfsys@curveto{-5.48657pt}{-8.71675pt}{-3.03018pt}{-11.17314pt}{0.0pt}{-11.17314pt}\pgfsys@curveto{3.03018pt}{-11.17314pt}{5.48657pt}{-8.71675pt}{5.48657pt}{-5.68657pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-5.68657pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-8.90878pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{{}} {{{}{}{{}}{}}}{{{}}}{{{{}}{{}}}}{{}}{{{ }}}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{44.37631pt}{0.0pt}\pgfsys@curveto{44.37631pt}{0.93733pt}{43.61647pt}{1.69717pt}{42.67914pt}{1.69717pt}\pgfsys@curveto{41.7418pt}{1.69717pt}{40.98196pt}{0.93733pt}{40.98196pt}{0.0pt}\pgfsys@curveto{40.98196pt}{-0.93733pt}{41.7418pt}{-1.69717pt}{42.67914pt}{-1.69717pt}\pgfsys@curveto{43.61647pt}{-1.69717pt}{44.37631pt}{-0.93733pt}{44.37631pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{42.67914pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{36.99289pt}{-16.72333pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-11.37314pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-5.68657pt}\pgfsys@curveto{5.48657pt}{-2.65639pt}{3.03018pt}{-0.2pt}{0.0pt}{-0.2pt}\pgfsys@curveto{-3.03018pt}{-0.2pt}{-5.48657pt}{-2.65639pt}{-5.48657pt}{-5.68657pt}\pgfsys@curveto{-5.48657pt}{-8.71675pt}{-3.03018pt}{-11.17314pt}{0.0pt}{-11.17314pt}\pgfsys@curveto{3.03018pt}{-11.17314pt}{5.48657pt}{-8.71675pt}{5.48657pt}{-5.68657pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-5.68657pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-8.90878pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{{}} {{{}{}{{}}{}}}{{{}}}{{{{}}{{}}}}{{}}{{{ }}}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{87.05545pt}{0.0pt}\pgfsys@curveto{87.05545pt}{0.93733pt}{86.29561pt}{1.69717pt}{85.35828pt}{1.69717pt}\pgfsys@curveto{84.42094pt}{1.69717pt}{83.6611pt}{0.93733pt}{83.6611pt}{0.0pt}\pgfsys@curveto{83.6611pt}{-0.93733pt}{84.42094pt}{-1.69717pt}{85.35828pt}{-1.69717pt}\pgfsys@curveto{86.29561pt}{-1.69717pt}{87.05545pt}{-0.93733pt}{87.05545pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{85.35828pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{85.35828pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{79.67235pt}{-16.72333pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-11.37314pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-5.68657pt}\pgfsys@curveto{5.48657pt}{-2.65639pt}{3.03018pt}{-0.2pt}{0.0pt}{-0.2pt}\pgfsys@curveto{-3.03018pt}{-0.2pt}{-5.48657pt}{-2.65639pt}{-5.48657pt}{-5.68657pt}\pgfsys@curveto{-5.48657pt}{-8.71675pt}{-3.03018pt}{-11.17314pt}{0.0pt}{-11.17314pt}\pgfsys@curveto{3.03018pt}{-11.17314pt}{5.48657pt}{-8.71675pt}{5.48657pt}{-5.68657pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-5.68657pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-8.90878pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{129.73459pt}{0.0pt}\pgfsys@curveto{129.73459pt}{0.93733pt}{128.97475pt}{1.69717pt}{128.03741pt}{1.69717pt}\pgfsys@curveto{127.10008pt}{1.69717pt}{126.34024pt}{0.93733pt}{126.34024pt}{0.0pt}\pgfsys@curveto{126.34024pt}{-0.93733pt}{127.10008pt}{-1.69717pt}{128.03741pt}{-1.69717pt}\pgfsys@curveto{128.97475pt}{-1.69717pt}{129.73459pt}{-0.93733pt}{129.73459pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{128.03741pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.6}{0.0}{0.0}{0.6}{128.03741pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.8}{0.0}{0.0}{0.8}{120.89908pt}{-19.94218pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\leavevmode\hbox to17.85pt{\vbox to17.85pt{\pgfpicture\makeatletter\hbox{\hskip 8.9229pt\lower-8.9229pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{8.7229pt}{0.0pt}\pgfsys@curveto{8.7229pt}{4.81758pt}{4.81758pt}{8.7229pt}{0.0pt}{8.7229pt}\pgfsys@curveto{-4.81758pt}{8.7229pt}{-8.7229pt}{4.81758pt}{-8.7229pt}{0.0pt}\pgfsys@curveto{-8.7229pt}{-4.81758pt}{-4.81758pt}{-8.7229pt}{0.0pt}{-8.7229pt}\pgfsys@curveto{4.81758pt}{-8.7229pt}{8.7229pt}{-4.81758pt}{8.7229pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-6.66667pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{-15}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{18.83957pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{61.5187pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}5}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{101.69783pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{10}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{40.17914pt}{18.11736pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{82.85828pt}{18.11736pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{61.5187pt}{30.9212pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{{ {\pgfsys@beginscope\pgfsys@setlinewidth{0.32pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{} {}{}{} {}{}{} \pgfsys@moveto{-1.19998pt}{1.59998pt}\pgfsys@curveto{-1.09998pt}{0.99998pt}{0.0pt}{0.09999pt}{0.29999pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.09999pt}{-1.09998pt}{-0.99998pt}{-1.19998pt}{-1.59998pt}\pgfsys@stroke\pgfsys@endscope}} }{}{}{{}}\pgfsys@moveto{1.81718pt}{0.0pt}\pgfsys@lineto{40.40225pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{40.40225pt}{0.0pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{44.49664pt}{0.0pt}\pgfsys@lineto{83.08171pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{83.08171pt}{0.0pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}} {{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{{}}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{0.90857pt}{1.57372pt}\pgfsys@curveto{17.198pt}{29.78792pt}{68.16092pt}{29.78792pt}{84.22035pt}{1.97208pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.5}{-0.86603}{0.86603}{0.5}{84.22035pt}{1.97208pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{42.67943pt}{26.26733pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{{}}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{0.90857pt}{1.57372pt}\pgfsys@curveto{25.51988pt}{44.2019pt}{102.51851pt}{44.2019pt}{126.89983pt}{1.97208pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.5}{-0.86603}{0.86603}{0.5}{126.89983pt}{1.97208pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{64.01917pt}{37.07784pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{{}}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{43.58804pt}{1.57367pt}\pgfsys@curveto{59.87747pt}{29.78787pt}{110.8404pt}{29.78792pt}{126.89983pt}{1.97208pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{0.5}{-0.86603}{0.86603}{0.5}{126.89983pt}{1.97208pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{85.35889pt}{26.2673pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}{}{}{}{}{{}}\pgfsys@moveto{87.17612pt}{0.0pt}\pgfsys@lineto{125.7612pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{125.7612pt}{0.0pt}\pgfsys@invoke{ }\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{106.69864pt}{3.533pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} The numbers below the vertices indicate the net flows on the corresponding vertices and the numbers above the edges indicate the weight on the corresponding edges. \par \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$

As discussed in Example 2.9, we have $\eta(\boldsymbol{m})=(6,7,2)$ . Thus, we have $f^{i}=\eta_{i}(\boldsymbol{m})$ for $i=1,2,3$ .

It is not hard to see that in general if $\boldsymbol{m}\in\mathbb{U}(n)$ is corresponding to the flow $f$ on $\vec{K}_{n+1}$ , then $f^{i}=\eta_{i}(\boldsymbol{m})$ for $1\leq i\leq n$ . Therefore, in the matrix notation, we can write the flow polytope with net flow ${\boldsymbol{a}}$ as:

(5.1)

\operatorname{Flow}_{n}({\boldsymbol{a}})=\{\boldsymbol{m}\in\mathbb{U}(n)~{}~{}|~{}~{}L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-\boldsymbol{m}\leq\boldsymbol{0}\}.

In order to be consistent with the bold fonts we have been using for elements in $\mathbb{U}(n),$ below we will use $\boldsymbol{f}$ instead of $f$ to denote a flow in $\operatorname{Flow}_{n}({\boldsymbol{a}}).$

One sees that if ${\boldsymbol{a}}\in\mathbb{R}_{\geq 0}^{n}$ , then $\operatorname{Tes}_{n}({\boldsymbol{a}})=\operatorname{Flow}_{n}({\boldsymbol{a}}).$ However, since for flow polytopes, we are allowed to use ${\boldsymbol{a}}$ with negative entries, the family of flow polytopes contains more polytopes than the family of Tesler polytopes. For convenience, for the rest of the paper, we fix ${\boldsymbol{a}}_{0}$ as an arbitrary element in $\mathbb{R}_{>0}^{n}$ . By Theorem 1.1, any deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ is a Tesler polytope up to a translation. Therefore, it is meaningful to ask when a flow polytope is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . Theorem 1.2 provides an answer to this question.

Remark 5.3.

Description (5.1) is different from

(5.2)

\{\boldsymbol{m}\in\mathbb{U}(n)~{}~{}|~{}~{}L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-P_{n}\boldsymbol{m}\leq\boldsymbol{0}\}.,

because (5.1) has one additional inequality $m_{n,n}\geq 0$ . Only when this inequality is redundant in the description (5.1) for $\operatorname{Flow}_{n}({\boldsymbol{a}})$ , we can describe $\operatorname{Flow}_{n}({\boldsymbol{a}})$ by (5.2), and then it is possible for $\operatorname{Flow}_{n}({\boldsymbol{a}})$ to be a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0}).$ If $m_{n,n}\geq 0$ is not a redundant inequality in (5.1), then $\operatorname{Flow}_{n}({\boldsymbol{a}})$ cannot be described by (5.2), and thus cannot be a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ .

Before we can prove Theorem 1.2, we need to clarify and define conditions given in the statement of the theorem. First, one observes that

\operatorname{Flow}_{n}({\boldsymbol{a}})\text{ is non-empty if and only if }\sum_{i=1}^{k}a_{i}\geq 0\text{ for all }1\leq k\leq n.

For convenience, we let $A_{n}$ be the set of all ${\boldsymbol{a}}\in\mathbb{R}^{n}$ that satisfies the above condition.

Definition 5.4.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in A_{n}$ . For each $1\leq i\leq n-1$ , if $a_{i}>0$ and $a_{i}+a_{i+1}=0$ , we say the positive entry $a_{i}$ is voided.

We say $l$ ( $1\leq l\leq n-1$ ) is the critical position of ${\boldsymbol{a}}$ if $a_{l}$ is the first positive entry in ${\boldsymbol{a}}$ that is not voided. If such a positive entry does not exist, we say $l=n$ is the critical position of ${\boldsymbol{a}}$ .

The following lemma gives a characterization for the entries that appear before the critical position of a point ${\boldsymbol{a}}\in A_{n}$ .

Lemma 5.5.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in A_{n}$ . Suppose $l$ is the critical position of ${\boldsymbol{a}}.$ Then for each $1\leq i<l$ , exactly one of the following three situations happens:

(1)

$a_{i}=0$ .
(2)

$a_{i}$ is a voided positive entry.
(3)

$a_{i}<0$ and $a_{i-1}$ is a voided positive entry.

Moreover, if $1\leq l\leq n-1$ , then $\displaystyle\sum_{i=1}^{l-1}a_{i}=0,$ and hence $a_{l}+a_{l+1}>0$ .

Proof.

The first part (which charaterizes entries $a_{i}$ for $i<l$ ) follows directly from the definition of the critical position, and the second conclusion follows immediately from the first part. ∎

Lemma 5.6.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in A_{n}$ where $l$ is the critical position of ${\boldsymbol{a}}$ and let $a_{i_{1}},a_{i_{2}},\dots,a_{i_{m}}$ be all the voided positive entries before the critical position where $1\leq i_{1}<i_{2}<\dots<i_{m}<l$ . Then all flows $\boldsymbol{f}=(f_{i,j})\in\operatorname{Flow}_{n}({\boldsymbol{a}})$ have fixed entries in their first $l-1$ rows as described below:

(1)

For each $1\leq p\leq m$ , the $({i_{p},i_{p}+1})$ -th entry $f_{i_{p},i_{p}+1}$ of $\boldsymbol{f}$ is always $a_{i_{p}}$ .
(2)

The remaining entries in the first $l-1$ rows of $\boldsymbol{f}$ are zeros.

Proof.

Using Lemma 5.5 together with the hypothesis of this lemma, we obtain that

a_{i}=\begin{cases}-a_{i+1},\quad&\text{if $i=i_{p}$ for some $1\leq p\leq m$;}\\ 0,\quad&\text{if $1\leq i<l$ and $i\neq i_{p}$ or $i_{p}+1$ for all $1\leq p\leq m$.}\end{cases}

Since the first $i_{1}-1$ entries of ${\boldsymbol{a}}$ are zeros and all the entries in $\boldsymbol{f}$ are non-negative, we conclude that the first $i_{1}-1$ rows of $\boldsymbol{f}$ have to be zero rows. In particular,

f_{i,i_{1}}=0,\quad\text{for all $1\leq i\leq i_{1}-1$}.

Hence, the $i_{1}$ -th and the $(i_{1}+1)$ -st hook sums of $\boldsymbol{f}$ are

(5.3)		$\displaystyle\eta_{i_{1}}(\boldsymbol{f})=$	$\displaystyle\ f_{i_{1},i_{1}}+\dots+f_{i_{1},n}-(f_{1,i_{1}}+\cdots+f_{i_{1}-1,i_{1}})=f_{i_{1},i_{1}}+\dots+f_{i_{1},n}=a_{i_{1}},$
(5.4)		$\displaystyle\eta_{i_{1}+1}(\boldsymbol{f})=$	$\displaystyle\ f_{i_{1}+1,i_{1}+1}+\dots+f_{i_{1}+1,n}-(f_{1,i_{1}+1}+\cdots+f_{i_{1},i_{1}+1})$
	$\displaystyle=$	$\displaystyle\ f_{i_{1}+1,i_{1}+1}+\dots+f_{i_{1}+1,n}-f_{i_{1},i_{1}+1}=a_{i_{1}+1}=-a_{i_{1}}.$

Using the fact that $\boldsymbol{f}$ has non-negative entries again, one sees that (5.3) implies $f_{i_{1},i_{1}+1}\leq a_{i_{1}}$ and (5.4) implies $f_{i_{1},i_{1}+1}\geq a_{i_{1}}$ . Thus, $f_{i_{1},i_{1}+1}=a_{i_{1}}$ . This forces the remaining entries in the $i_{1}$ -th and $(i_{1}+1)$ -st rows are zeros. We have shown that the first $i_{1}+1$ rows of $\boldsymbol{f}$ are given as described by the lemma. By iterating similar arguments, one can deduce that all the first $l-1$ rows are as described. ∎

The following two propositions are the key results that will be used in our proof for Theorem 1.2.

Proposition 5.7.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in A_{n}$ and suppose $l$ is the critical position of ${\boldsymbol{a}}$ .

(1)

If $1\leq l<n,$ then there exists $\hat{{\boldsymbol{a}}}=(\hat{a}_{1},\dots,\hat{a}_{n})\in A_{n}$ satisfying

\hat{a}_{1}=\hat{a}_{2}=\cdots=\hat{a}_{l-1}=0,\ \hat{a}_{l}>0,\ \hat{a}_{l+1}\geq 0,\text{ and $\hat{a}_{i}=a_{i}$ for $l+2\leq i\leq n$.}

such that $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is a translation of $\operatorname{Flow}_{n}(\hat{{\boldsymbol{a}}})$ .

(2)

If $l=n,$ then $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is a point.

Proposition 5.8.

Let $n\geq 3$ and ${\boldsymbol{a}}=(a_{1},a_{2},\cdots,a_{n})\in A_{n}$ . Suppose for some integer $1\leq l\leq n-1$ , we have $a_{1}=a_{2}=\cdots=a_{l-1}=0$ , $a_{l}>0$ , and $a_{l+1}\geq 0$ . (Note that this implies that $l$ is the critical position of ${\boldsymbol{a}}.$ ) Assume further that $a_{m}$ is the first negative entry of ${\boldsymbol{a}}$ , where $l+2\leq m\leq n.$ Then $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is not a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ .

Before we prove each of these two propositions, we need a preliminary lemma. Recall that ${\boldsymbol{e}}_{k}$ is the $k$ -th standard basis vector of $\mathbb{R}^{n}$ . For convenience, for every $1\leq i\leq j\leq n,$ we denote by ${\boldsymbol{e}}_{i,j}$ to be the unique upper triangular matrix in $\mathbb{U}(n)$ whose $(i,j)$ -th entry is its only nonzero entry and has value $1$ . So $\{{\boldsymbol{e}}_{i,j}\}$ is the standard basis for $\mathbb{U}(n)$ .

Lemma 5.9.

Let ${\boldsymbol{a}}=(a_{1},\dots,a_{n})\in A_{n}$ and $c>0$ . Suppose for a fixed pair of indices $1\leq i\leq j\leq n,$ we have that every flow $\boldsymbol{f}=(f_{i,j})\in\operatorname{Flow}_{n}({\boldsymbol{a}})$ satisfies $f_{i,j}\geq c.$ Then

\operatorname{Flow}_{n}({\boldsymbol{a}})-c{\boldsymbol{e}}_{i,j}=\begin{cases}\operatorname{Flow}_{n}({\boldsymbol{a}}-c{\boldsymbol{e}}_{i}+c{\boldsymbol{e}}_{j}),&\quad\text{if $i<j$},\\ \operatorname{Flow}_{n}({\boldsymbol{a}}-c{\boldsymbol{e}}_{i}),&\quad\text{if $i=j$}.\end{cases}

Proof.

We only prove the case when $i<j$ , as the case when $i=j$ can be proved similarly. Let $\boldsymbol{f}\in\mathbb{U}(n)$ and ${\boldsymbol{g}}=\boldsymbol{f}-c{\boldsymbol{e}}_{i,j}.$ First, since $\boldsymbol{\eta}({\boldsymbol{e}}_{i,j})={\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}$ , we have that $\boldsymbol{\eta}(\boldsymbol{f})={\boldsymbol{a}}$ if and only only if $\boldsymbol{\eta}({\boldsymbol{g}})={\boldsymbol{a}}-c{\boldsymbol{e}}_{i}+c{\boldsymbol{e}}_{j}.$ Next, if $\boldsymbol{f}\in\operatorname{Flow}_{n}({\boldsymbol{a}})$ , because $f_{i,j}\geq c,$ we see that all entries of ${\boldsymbol{g}}$ are non-negative. Conversely, if ${\boldsymbol{g}}\in\operatorname{Flow}_{n}({\boldsymbol{a}}-c{\boldsymbol{e}}_{i}+c{\boldsymbol{e}}_{j})$ , since $c>0,$ we must have that all entries of $\boldsymbol{f}={\boldsymbol{g}}+c{\boldsymbol{e}}_{i,j}$ are non-negative. Therefore, we conclude that $\boldsymbol{f}\in\operatorname{Flow}_{n}({\boldsymbol{a}})$ if and only if ${\boldsymbol{g}}\in\operatorname{Flow}_{n}({\boldsymbol{a}}-c{\boldsymbol{e}}_{i}+c{\boldsymbol{e}}_{j}).$ Then the conclusion of the lemma follows. ∎

Proof of Proposition 5.7.

Suppose $l=n$ . Then by Lemma 5.6, the first $n-1$ rows of all the flows in $\operatorname{Flow}_{n}({\boldsymbol{a}})$ are fixed. However, the $n$ -th hook sum condition makes the only entry in the $n$ -th row to be fixed as well. Hence, (2) follows.

Suppose $1\leq l\leq n-1$ and assume $a_{i_{1}},a_{i_{2}},\dots,a_{i_{m}}$ are all the voided positive entries before the critical position where $1\leq i_{1}<i_{2}<\dots<i_{m}<l$ . It follows from Lemma 5.6 and Lemma 5.9 that

\operatorname{Flow}_{n}({\boldsymbol{a}})-\sum_{p=1}^{m}a_{i_{p}}{\boldsymbol{e}}_{i_{p},i_{p}+1}=\operatorname{Flow}_{n}(0,\dots,0,a_{l},a_{l+1},\dots,a_{n}).

If $a_{l+1}\geq 0$ , then we see that ${\boldsymbol{a}}^{\prime}:=(0,\dots,0,a_{l},a_{l+1},\dots,a_{n})$ is a desired choice for $\hat{a}$ .

Suppose $a_{l+1}<0$ . We now consider the flow polytope $\operatorname{Flow}_{n}({\boldsymbol{a}}^{\prime})$ . Clearly, $l$ is still the critical position of the vector ${\boldsymbol{a}}^{\prime}$ . Let ${\boldsymbol{g}}\in\operatorname{Flow}_{n}({\boldsymbol{a}}^{\prime}).$ It is clear (or follows from Lemma 5.6) that the first $l-1$ rows of ${\boldsymbol{g}}$ are zero rows. Thus, the $(l+1)$ -th hook sum of ${\boldsymbol{g}}=(g_{i,j})$ is:

\eta_{l+1}({\boldsymbol{g}})=g_{l+1,l+1}+\cdots+g_{l+1,n}-g_{l,l+1}=a_{l+1}

Since $g_{l+1,l+1},\cdots,g_{l+1,n}$ are all non-negative, we get that $g_{l,l+1}\geq-a_{l+1}>0$ . Now applying Lemma 5.9 with $c=-a_{l+1}$ , we get

\operatorname{Flow}_{n}({\boldsymbol{a}}^{\prime})-c{\boldsymbol{e}}_{l,l+1}=\operatorname{Flow}_{n}({\boldsymbol{a}}^{\prime}-c{\boldsymbol{e}}_{l}+c{\boldsymbol{e}}_{l+1}).

where

{\boldsymbol{a}}^{\prime}-c{\boldsymbol{e}}_{l}+c{\boldsymbol{e}}_{l+1}=(0,\dots,0,a_{l}+a_{l+1},0,a_{l+2},\dots,a_{n}).

However, by the last conclusion of Lemma 5.5, we have $a_{l}+a_{l+1}>0.$ Hence, ${\boldsymbol{a}}^{\prime}-c{\boldsymbol{e}}_{l}+c{\boldsymbol{e}}_{l+1}$ is a desired choice for $\hat{{\boldsymbol{a}}}$ for this case. Therefore, (1) holds. ∎

The next lemma shows the existence of a certain flow which will be used in the proof of Proposition 5.8.

Lemma 5.10.

Assume the hypothesis of Proposition 5.8. If $m\neq n$ , i.e., $l+2\leq m<n$ , then there exists a flow $\boldsymbol{f}=(f_{i,j})$ in $\operatorname{Flow}_{n}({\boldsymbol{a}})$ satisfying the following conditions:

(i)

$f_{l,m}>0$ .
(ii)

$f_{l,m}+f_{l+1,m}+\cdots+f_{m-1,m}=-a_{m}.$
(iii)

The $m$ th row of $\boldsymbol{f}$ is a zero row.
(iv)

The first $l-1$ rows of $\boldsymbol{f}$ are zero rows.

Proof.

We prove the lemma by constructing such a flow $\boldsymbol{f}$ . Because the first $l-1$ entries of ${\boldsymbol{a}}$ are all zero and $a_{m}$ is the first negative entry, we have that

\sum_{p=1}^{l-1}a_{p}=0,\ \sum_{p=1}^{l}a_{p},\ \sum_{p=1}^{l+1}a_{p},\dots,\sum_{p=1}^{m-1}a_{p}

is a weakly increasing sequence. Since ${\boldsymbol{a}}\in A_{n}$ , one sees that the last entry in the above sequence is at least $-a_{m}$ , which is strictly greater than the first entry in the sequence. Therefore, there exists (a unique) $k\in\{l,l+1,\dots,m-1\}$ such that

\sum_{p=1}^{k-1}a_{p}<-a_{m}\leq\sum_{p=1}^{k}a_{p}.

Let

c_{i}=\begin{cases}a_{i},&\text{if $l\leq i\leq k-1$}\\ -a_{m}-\sum_{p=1}^{k-1}a_{p},&\text{if $i=k$}\\ 0,&\text{if $k+1\leq i\leq m-1$}.\end{cases},

and then let

d_{i}=a_{i}-c_{i},\text{ for $l\leq i\leq m-1$}.

One can verify that all $c_{i}$ ’s and $d_{i}$ ’s are non-negative, and moreover,

(5.5)

c_{l}>0\quad\text{and}\quad c_{l}+c_{l+1}+\cdots c_{m-1}=-a_{m}.

Now we are ready to construct a desired flow $\boldsymbol{f}$ . We define $\boldsymbol{f}=(f_{i,j})\in\mathbb{U}(n)$ as

f_{i,j}=\begin{cases}c_{i},&\text{if $l\leq i\leq m-1$ and $j=m$}\\ d_{i},&\text{if $l\leq i\leq m-1$ and $j=m+1$}\\ \sum_{p=1}^{i}a_{p},&\text{if $m+1\leq i\leq n-1$ and $j=i+1$}\\ \sum_{p=1}^{n}a_{p},&\text{if $i=j=n$}\\ 0,&\text{otherwise}.\end{cases}

It is straightforward to check that $\boldsymbol{f}\in\operatorname{Flow}_{n}({\boldsymbol{a}})$ and the desired properties of $\boldsymbol{f}$ follow from the definition of $\boldsymbol{f}$ and (5.5). ∎

Proof of Proposition 5.8.

Suppose $m=n.$ Then $a_{1},a_{2},\dots,a_{n-1}\geq 0$ and $a_{n}<0.$ Consider ${\boldsymbol{g}}=(g_{i,j})\in\mathbb{U}(n)$ defined by $g_{i,i}=a_{i}$ for each $i$ and $g_{i,j}=0$ for each $1\leq i<j\leq n.$ Clearly ${\boldsymbol{g}}\notin\operatorname{Flow}_{n}({\boldsymbol{a}})$ as $g_{n,n}=a_{n}<0.$ However, ${\boldsymbol{g}}$ is a point in the polytope defined by (5.2). This means if we remove the inequality $m_{n,n}\geq 0$ from the inequality description (5.1) for $\operatorname{Flow}_{n}({\boldsymbol{a}})$ , we obtain a different polytope. Hence, the inequality $m_{n,n}\geq 0$ is not redundant in (5.1). Hence, by Remark 5.3, we conclude that $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is not a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ .

Suppose $m\neq n.$ By Remark 5.3, we only need to consider the situation when (5.2) is a linear inequality description for $\operatorname{Flow}_{n}({\boldsymbol{a}})$ . Note that the description is not necessarily tight. However, it is clear that there exists $\tilde{{\boldsymbol{b}}}=(\tilde{b}_{i,j})\in\widetilde{\mathbb{U}}(n)$ such that

(5.6)

\operatorname{Flow}_{n}({\boldsymbol{a}})=Q({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})=\{\boldsymbol{m}\in\mathbb{U}(n)~{}~{}|~{}~{}L_{n}\boldsymbol{m}={\boldsymbol{a}}\text{ and }-P_{n}\boldsymbol{m}\leq\tilde{{\boldsymbol{b}}}\}.

is a tight linear inequality description for $\operatorname{Flow}_{n}({\boldsymbol{a}}).$ By Remark 2.2, one sees that it is enough to show that $({\boldsymbol{a}},\tilde{{\boldsymbol{b}}})$ is not in the deformation cone of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ , which by Theorem 1.1 is equivalent to that $\eta_{i}(\tilde{{\boldsymbol{b}}})<-a_{i}$ for some $1\leq i\leq n-1.$ We will show that $\eta_{m}(\tilde{{\boldsymbol{b}}})<-a_{m}$ . Note that by the definition of tightness and the assumption that $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is defined by (5.2), the entries in $\tilde{{\boldsymbol{b}}}$ satisfy:

(5.7)

0\leq-\tilde{b}_{i,j}=\min_{\boldsymbol{m}\in\operatorname{Flow}_{n}({\boldsymbol{a}})}m_{i,j}.

Let $\boldsymbol{f}=(f_{i,j})$ be the flow in $\operatorname{Flow}_{n}({\boldsymbol{a}})$ assumed by Lemma 5.10. Then condition (5.7) implies that

-\tilde{b}_{i,m}\leq f_{i,m}\text{ for $l\leq i\leq m-1$}.

Using condition (5.7) together with Lemma 5.10/(iii)(iv), we conclude that

\tilde{b}_{m,m}=\tilde{b}_{m,m+1}=\cdots=\tilde{b}_{m,n}=0\text{ and }\tilde{b}_{1,m}=\tilde{b}_{2,m}=\cdots=\tilde{b}_{l-1,m}=0.

Next, by Lemma 5.10/(i), we may choose a number $\epsilon$ such that $0<\epsilon<f_{l,m}$ . Then we construct ${\boldsymbol{g}}=(g_{i,j})\in\mathbb{U}(n)$ from $\boldsymbol{f}$ by letting

g_{l,m}=f_{l,m}-\epsilon,\ g_{l+1,m}=f_{l+1,m}+\epsilon,\ g_{l,l+1}=f_{l,l+1}+\epsilon,

and keeping all the other entries. One can check that ${\boldsymbol{g}}$ is another flow in $\operatorname{Flow}_{n}({\boldsymbol{a}})$ . Applying (5.7) again for $(i,j)=(l,m)$ , we get

-\tilde{b}_{l,m}\leq g_{l,m}=f_{l,m}-\epsilon.

Therefore,

	$\displaystyle\eta_{m}(\tilde{{\boldsymbol{b}}})=$	$\displaystyle\sum_{j=m}^{n}\tilde{b}_{m,j}-\sum_{i=1}^{m-1}\tilde{b}_{i,m}=\sum_{j=m}^{n}\tilde{b}_{m,j}-\sum_{i=1}^{l-1}\tilde{b}_{i,m}-\sum_{i=l}^{m-1}\tilde{b}_{i,m}=0-0-\sum_{i=l}^{m-1}\tilde{b}_{i,m}$
	$\displaystyle\leq$	$\displaystyle(f_{l,m}-\epsilon)+f_{l+1,m}+\cdots+f_{m-1,m}<f_{1,m}+f_{2,m}+\cdots+f_{m-1,m}=-a_{m},$

where the last equality follows from Lemma 5.10/(ii). This completes our proof. ∎

Proof of Theorem 1.2.

By Proposition 5.7/(2), if $l=n,$ then $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is a point, which clearly is a deformation of $\operatorname{Tes}_{n}({\boldsymbol{a}}_{0})$ . Therefore, it is left to prove that if $1\leq l\leq n-1,$ then

(5.8)

\text{ $\operatorname{Flow}_{n}({\boldsymbol{a}})$ is a deformation of $\operatorname{Tes}_{n}(\boldsymbol{1})$}\quad\Longleftrightarrow\quad a_{l+2},a_{l+3},\dots,a_{n}\geq 0.

However, by Proposition 5.7 and Remark 2.3, one sees that it is enough to prove (5.8) with the assumption that ${\boldsymbol{a}}=(a_{1},\dots,a_{n})$ satisfies

a_{1}=a_{2}=\cdots=a_{l-1}=0,\ a_{l}>0,\ \text{ and }a_{l+1}\geq 0.

Then the forward direction of (5.8) immediately follows Proposition 5.8. If $a_{l+2},a_{l+3},\dots,a_{n}\geq 0,$ then ${\boldsymbol{a}}\in\mathbb{R}^{n}_{\geq 0}$ and $\operatorname{Flow}_{n}({\boldsymbol{a}})=\operatorname{Tes}_{n}({\boldsymbol{a}})$ , which by Theorem 3.1 is a deformation of $\operatorname{Tes}_{n}(\boldsymbol{1})$ . Hence, the backward direction of (5.8) holds. ∎

References

[1] D. Armstrong, A. Garsia, J. Haglund, B. Rhoades, and B. Sagan. Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics. Journal of Combinatorics, 3(3):451–494, 2012.
[2] W. Baldoni and M. Vergne. Kostant partitions functions and flow polytopes. Transformation Groups, 13:447–469, 2008.
[3] A. Barvinok. Integer points in polyhedra, volume 452. European Mathematical Society, 2008.
[4] C. Benedetti, R. González D’León, C. Hanusa, P. Harris, A. Khare, A. Morales, and M. Yip. A combinatorial model for computing volumes of flow polytopes. Transactions of the American Mathematical Society, 2019.
[5] E. R. Canfield and B. D. McKay. The asymptotic volume of the Birkhoff polytope. arXiv preprint arXiv:0705.2422, 2007.
[6] F. Castillo and F. Liu. Deformation cones of nested braid fans. Int. Math. Res. Not. IMRN, (3):1973–2026, 2022.
[7] C. S. Chan, D. P. Robbins, and D. S. Yuen. On the volume of a certain polytope. Experimental Mathematics, 9(1):91–99, 2000.
[8] S. Corteel, J. S. Kim, and K. Mészáros. Volumes of generalized Chan–Robbins–Yuen polytopes. Discrete & Computational Geometry, pages 1–21, 2017.
[9] D. A. Cox, J. B. Little, and H. K. Schenck. Toric varieties, volume 124 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2011.
[10] J. A. De Loera, F. Liu, and R. Yoshida. A generating function for all semi-magic squares and the volume of the Birkhoff polytope. Journal of Algebraic Combinatorics, 30(1):113–139, 2009.
[11] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 69–87. Gordon and Breach, New York-London-Paris, 1970.
[12] A. Garsia, J. Haglund, and G. Xin. Constant term methods in the theory of Tesler matrices and Macdonald polynomial operators. Annals of Combinatorics, 18(1):83–109, 2014.
[13] E. Gorsky and A. Neguţ. Refined knot invariants and Hilbert schemes. Journal de mathématiques pures et appliquées, 104(3):403–435, 2015.
[14] J. Haglund. A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants. Advances in Mathematics, 227(5):2092–2106, 2011.
[15] J. Haglund, J. Remmel, and A. Wilson. The delta conjecture. Transactions of the American Mathematical Society, 370(6):4029–4057, 2018.
[16] Y. Lee and F. Liu. Ehrhart positivity of Tesler polytopes and Berline-Vergne’s valuation. Discrete Comput. Geom., 69(3):896–918, 2023.
[17] P. McMullen. Representations of polytopes and polyhedral sets. Geometriae Dedicata, 2:83–99, 1973.
[18] K. Mészáros, A. H. Morales, and B. Rhoades. The polytope of Tesler matrices. Selecta Mathematica, New Series, 23(1):425–454, 2017.
[19] A. H. Morales. Ehrhart polynomials of examples of flow polytopes. https://sites.google.com/site/flowpolytopes/ehrhart.
[20] A. Padrol, V. Pilaud, and G. Poullot. Deformation cones of graph associahedra and nestohedra. European J. Combin., 107:Paper No. 103594, 27, 2023.
[21] I. Pak. Four questions on Birkhoff polytope. Annals of Combinatorics, 4(1):83–90, 2000.
[22] A. Postnikov. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN, (6):1026–1106, 2009.
[23] A. Postnikov, V. Reiner, and L. Williams. Faces of generalized permutohedra. Doc. Math., 13:207–273, 2008.
[24] A. Postnikov, V. Reiner, and L. Williams. Faces of generalized permutohedra. Doc. Math, 13(207-273):51, 2008.
[25] A. T. Wilson. A weighted sum over generalized Tesler matrices. Journal of Algebraic Combinatorics, 45(3):825–855, 2017.
[26] D. Zeilberger. Proof of a conjecture of Chan, Robbins, and Yuen. Electron. Trans. Numer. Anal, 9(147-148):1–2, 1999.
[27] G. M. Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.

Deformation cones of Tesler polytopes

Abstract.

1. Introduction

Theorem 1.1.

Theorem 1.2.

Organization of the paper

Acknowledgements

2. Preliminaries

2.1. Polytopes

2.2. Deformations

Definition 2.1.

Remark 2.2.

Remark 2.3.

Lemma 2.4.

Lemma 2.5.

Connection to type cones

Definition 2.6.

Lemma 2.7.

Corollary 2.8.

2.3. Tesler polytopes

Example 2.9.

2.3.1. Notations for Theorem 1.1

2.4. Prior work on Tesler polytopes

Definition 2.10.

Theorem 2.11.

Lemma 2.12.

Lemma 2.13.

Lemma 2.14.

Example 2.15.

3. All Tesler polytopes are deformations of Tesn⁡(𝟏)\operatorname{Tes}_{n}({\boldsymbol{1}})

Theorem 3.1.

Definition 3.2.

Proposition 3.3.

Example 3.4.

Lemma 3.5.

Proof.

Lemma 3.6.

Proof.

Proof of Proposition 3.3.

Lemma 3.7.

Proof.

Proof of Theorem 3.1.

Lemma 3.8.

Proof.

Theorem 3.9.

4. The deformation cone of Tesler polytopes

Lemma 4.1.

Proof.

Example 4.2.

Proof of Theorem 1.1.

Lemma 4.3.

Proof.

Proof of Theorem 3.9.

5. Flow polytopes that are deformations of Tesler polytopes

Definition 5.1.

Example 5.2.

Remark 5.3.

Definition 5.4.

Lemma 5.5.

Proof.

Lemma 5.6.

Proof.

Proposition 5.7.

Proposition 5.8.

Lemma 5.9.

Proof.

Proof of Proposition 5.7.

Lemma 5.10.

Proof.

Proof of Proposition 5.8.

Proof of Theorem 1.2.

References

3. All Tesler polytopes are deformations of $\operatorname{Tes}_{n}({\boldsymbol{1}})$