1.1. Balanced polyhedra [04QP]

Original official author HTML, exact retained edition. Historical TeX conversion verdicts remain unchanged. Cited-edition alignment and mathematical self-containment are not assessed.

Complete original source context · Original author HTML

1.1. Balanced polyhedra

Definition 1.

A subset $\Pi\subset\mathbb{R}^{n+1}$ is called a proper rational polyhedral complex (or just a polyhedral complex in this paper) if it can be presented as a finite union of closed sets in $\mathbb{R}^{n+1}$ called cells with the following properties.

•

Each cell is a closed convex (possibly semi-infinite) polyhedron. The dimension of the cell is, by definition, the dimension of its affine spun, the smallest affine subspace of $\mathbb{R}^{n+1}$ which contains it. We call a cell of dimension $k$ a $k$ -cell.
•

The slope of the affine spun of each cell is rational. I.e. the linear subspace of $\mathbb{R}^{n+1}$ parallel to the affine spun is defined over $\mathbb{Q}$ .
•

The boundary (i.e. the boundary in the corresponding affine spun) of a $k$ -cell is a union of $(k-1)$ -cells.
•

Different open cells (i.e. the interiors of the cells in the corresponding affine spuns) do not intersect.

Informally speaking, a proper polyhedral complex in $\mathbb{R}^{n+1}$ is a cellular space where each cell is a convex polyhedron with a rational slope and where some cells are allowed to go to infinity.

As usual, the dimension of $\Pi$ is the maximal dimension of its cells.

Definition 2.

A polyhedral $n$ -complex is called weighted if there is a natural number $w(F)$ , called weight, prescribed to each of its $n$ -cell $F$ . (Of course, any polyhedral complex can be considered as a weighted polyhedral complex by prescribing 1 to each $n$ -cell.)

Let $\Pi\subset\mathbb{R}^{n+1}$ be a weighted polyhedral $n$ -complex. Note that its complement $\mathbb{R}^{n+1}\smallsetminus\Pi$ consists of a finite union of connected components. Let $F\subset\Pi$ be an $n$ -cell.

Recall that by Definition 1 the $n$ -cell $F$ has a rational slope in $\mathbb{R}^{n+1}$ . Therefore, it defines an integer covector

\pm c_{F}:\mathbb{Z}^{n+1}\to\mathbb{Z}

up to its sign. Here are the characteristic properties of $c_{F}$ .

•

The kernel of $c_{F}$ is parallel to $F$ .
•

$\frac{1}{w(F)}c_{F}$ is a primitive (i.e. non-divisible) integer covector $\mathbb{Z}^{n+1}\to\mathbb{Z}$ .

Furthermore, even the sign of $c_{F}$ becomes well-defined once we co-orient $F\subset\mathbb{R}^{n+1}$ .

Polyhedral complexes that appear in this paper have the following additional property.

Definition 3.

A weighted polyhedral $n$ -complex $\Pi\subset\mathbb{R}^{n+1}$ is called balanced if for every $(n-1)$ -cell $G\subset\Pi$ the following condition holds. Let $F_{1},\dots,F_{k}$ be the $n$ -cells adjacent to $G$ . A choice of a rotational direction about $G$ defines a coherent co-orientation on these $n$ -cells. The balancing condition is

\sum\limits_{j=1}^{k}c_{F_{j}}=0.

Refer to caption — Figure 1. Balanced graphs in $\mathbb{R}^{2}$ .

Example 1.

Consider the function

H(x_{1},\dots,x_{n+1})=\max\{0,x_{1},\dots,x_{n+1}\}.

This is a convex piecewise-linear function $\mathbb{R}^{n+1}\to\mathbb{R}$ . We define the primitive complex $\Sigma_{n}\subset\mathbb{R}^{n+1}$ as the corner locus of $H$ , i.e. the set of points where $H$ is not smooth is $\Sigma_{n}$ .

Note that $\Sigma_{n}$ is a balanced proper polyhedral complex in $\mathbb{R}^{n+1}$ . Its $k$ -cells are formed by the points where at least $n+2-k$ of the functions $0,x_{1},\dots,x_{n+1}$ achieve the value of $H$ . In fact, it is easy to see that topologically $\Sigma_{n}$ is the cone over the $(n-1)$ -skeleton of the $(n+1)$ -simplex. The fact that $\Sigma$ is balanced follows from Proposition 1.2.

The following example is a generalization of the previous one. As the following propositions show, it is the fundamental example of balanced polyhedra.

Example 2.

Let $A\subset\mathbb{Z}^{n+1}$ be a finite set and let $v:A\to\mathbb{R}$ be any function. Let $\Delta\subset\mathbb{R}^{n+1}$ be the convex hull of $A$ . We associate the following polyhedral complex $\Pi_{v}$ to $v$ .

Take the Legendre transform $L_{v}:\mathbb{R}^{n+1}\to\mathbb{R}$ of $v$

L_{v}(y)=\max\limits_{x\in A}(xy-v(x)).

Here $x,y\in\mathbb{R}^{n+1}$ and $xy$ is their scalar product. Since the maximum is taken over a finite set, the result $L_{v}$ is a convex piecewise-linear function. We define $\Pi_{v}$ as the corner locus of $L_{v}$ (recall that this is the set of points where $L_{v}$ is not smooth).

To present Example 1 as a special case of Example 2 we take the vertices of the standard simplex

(1)

\Delta_{1}\{(x_{1},\dots,x_{n+1})\in\mathbb{R}^{n+1}\ |\ x_{j}\geq 0,x_{1}+\dots+x_{n+1}\leq 1\}

for $A$ and set $v\equiv 0$ .

Recall that a polyhedron in $\mathbb{R}^{n+1}$ is called lattice if all its vertices belong to $\mathbb{Z}^{n+1}$ . A subdivision of a polyhedron into smaller polyhedra is called lattice if all the polyhedra of the subdivision are lattice.

Proposition 1.1.

The set $\Pi_{v}$ from Example 2 is a proper rational polyhedral complex dual to a certain lattice subdivision of $\Delta$ .

Proof.

We start by associating to $v$ a certain lattice subdivision ${\mathcal{D}}_{v}$ of $\Delta$ . Let $O\Gamma(v)$ be the overgraph of $v$ , i.e. the set of vertical rays upwards in $\mathbb{R}^{n+1}\times\mathbb{R}$ starting at the points of the graph of $v$ . The convex hull of $O\Gamma(v)$ is a semi-infinite closed polyhedral domain. The projections of its finite faces to $\mathbb{R}^{n+1}$ form the subdivision ${\mathcal{D}}_{v}$ .

We claim that $\Pi_{v}$ is a polyhedral complex dual to ${\mathcal{D}}_{v}$ . Namely, a $k$ -dimensional polyhedron $\Delta^{\prime}$ in ${\mathcal{D}}_{v}$ , $k>0$ , gives a $(n+1-k)$ -cell of $\Pi_{v}$ . This cell is compact iff $\Delta^{\prime}\subset\Delta$ .

This claim follows from the duality property of the Legendre transform. Consider the function $\tilde{v}$ whose graph is is given by the lower boundary of the convex hull of $O\Gamma(v)$ . If $v$ is convex then the function $\tilde{v}$ extends $v$ and is defined on the whole polyhedron $\Delta$ , not just on its lattice points. It is a convex piecewise-linear function. The Legendre transform of $v$ coincides with the Legendre transform of $\tilde{v}$ . (In fact the function $\tilde{v}$ can be defined by applying the Legendre transform to $v$ twice.) By duality, the graph of $L_{\tilde{v}}$ has the facets en lieu of the vertices of the graph of $\tilde{v}$ and so on. ∎

Note that $\Pi_{v}$ is naturally weighted. Indeed, an $n$ -cell $F\subset\Pi_{v}$ comes as a corner between the graphs of two integer linear functions. The difference between these functions is an integer covector $c_{F}$ . We define $w(F)\in{\mathbb{N}}$ as the maximum integer divisor of $c_{F}$ .

Proposition 1.2.

The weighted polyhedral complex $\Pi_{v}$ is balanced.

Proof.

The proposition easily follows from the definition of the covectors $c_{F_{j}}$ for the $n$ -cells $F_{j}$ adjacent to an $(n-1)$ -cell $G\subset\Pi$ . ∎

Remark 1.3.

Note that several different functions $v$ define the same complex $\Pi_{v}$ by the construction of Example 2. Here is the list of ambiguities.

(1)

Let $v^{\prime}=v+\operatorname{const}:A\to\mathbb{R}$ be a function different with $v$ by a constant. Then $\Pi_{v}=\Pi_{v^{\prime}}$ .
(2)

Let $A^{\prime}=A+c$ , where $c\in\mathbb{Z}^{n+1}$ and $v^{\prime}:A^{\prime}\to\mathbb{R}$ is defined by $v^{\prime}(z+c)=v(z)$ . Then $\Pi_{v}=\Pi_{v^{\prime}}$ .
(3)

Let $A^{\prime}$ be such that its convex hull $\Delta^{\prime}$ coincides with $\Delta$ , the convex hull of $A$ . Let $\underline{v}$ (resp. $\underline{v^{\prime}}$ ) be the maximal convex function such that $\underline{v}\leq v$ (resp. $\underline{v^{\prime}}\leq v^{\prime}$ ). Suppose that $\underline{v}=\underline{v^{\prime}}$ . Then $\Pi_{v}=\Pi_{v^{\prime}}$ .

The following proposition shows that Example 2 is fundamental.

Proposition 1.4.

Suppose that $\Pi\subset\mathbb{R}^{n+1}$ is a weighted balanced proper rational polyhedral complex. Then there exists a finite set $A\subset\mathbb{Z}^{n+1}$ and a function $v:A\to\mathbb{Z}$ such that $\Pi=\Pi_{v}$ (see Example 2). The convex hull $\Delta\subset\mathbb{R}^{n+1}$ of $A$ is unique up to a translation in $\mathbb{Z}^{n+1}$ . The choice of the function $v$ is unique up to the ambiguity of Remark 1.3.

Proof.

First we define a convex piecewise-linear function $H$ whose corner locus is $\Pi$ and then choose a function $v$ such that $H$ is the Legendre transform $L_{v}$ of $v$ . Note that the finiteness condition in Definition 1 implies that there are finitely many connected components in $\mathbb{R}^{n+1}\smallsetminus\Pi$ .

We define the function $H$ inductively. Choose any connected component $D_{0}$ of $\mathbb{R}^{n+1}\smallsetminus\Pi$ as a “reference component”. Define $H|_{D_{0}}\equiv 0$ . Suppose that $D^{\prime}$ is a component of $\mathbb{R}^{n+1}\smallsetminus\Pi$ such that there exists an adjacent component $D$ where $H$ is already defined.

Let $F$ be the $n$ -cell of of $\Pi$ separating $D$ from $D^{\prime}$ . Let $c_{F}$ be the covector associated to $F$ (recall that the weight of $F$ is incorporated into $c_{F}$ ) with the co-orientation directed from $D$ to $D^{\prime}$ . Let $l_{D}:\mathbb{R}^{n+1}\to\mathbb{R}$ be the linear function extending $H|_{D}$ . We define $H|_{D^{\prime}}=l_{D}+c_{F}$ . By the balancing condition the result does not depend on the choice of the adjacent component $D$ where $H$ is already defined.

To define $v$ we take the Legendre transform of $H$ . This amounts to associating each component $D$ a point $z\in\mathbb{Z}^{n+1}$ equal to the gradient of $H|_{D}$ and setting $v(z)=l_{D}(0)$ . Thus, the number of elements of the set $A$ is equal to the number of components of $\mathbb{R}^{n+1}\smallsetminus\Pi$ .

The ambiguity Remark 1.3.3 comes from taking the Legendre transform of non-convex functions $v$ . It coincides with the Legendre transform of the underlying convex function $\underline{v}$ . (In fact, nothing changes if we assume that $v$ is defined on the whole $\mathbb{Z}^{n+1}$ by letting $v(z)=+\infty$ for $z\notin A$ .) The ambiguities Remark 1.3.1 and 1.3.2 come from the ambiguity in assigning a linear function for $H|_{D_{0}}$ . ∎

Corollary 1.5.

To any $n$ -dimensional balanced polyhedral complex $\Pi\subset\mathbb{R}^{n+1}$ one may associate a convex lattice polyhedron $\Delta\subset\mathbb{R}^{n+1}$ (defined up to translation) and a lattice subdivision of $\Delta$ .

This corollary follows from Propositions 1.4 and 1.1.

The next corollary illustrates the strength of the balancing condition that we require just for the $n$ -cells. We do not use this corollary elsewhere in the paper.

Let $B$ be a vertex of $\Pi$ and let $E_{1},\dots,E_{k}$ be the edges adjacent to $B$ . Let $v_{j}\in\mathbb{Z}^{n+1}$ , $j=1,\dots,k$ , be the primitive integer vectors in the direction of $E_{j}$ . Suppose that each $E_{j}$ is adjacent to exactly $n+2$ connected components of $\mathbb{R}^{n+1}\smallsetminus\Pi$ (note that this is a general position situation).

Corollary 1.6.

If $\Pi\subset\mathbb{R}^{n+1}$ is a balanced $n$ -complex then there exists a weight $w_{j}\subset{\mathbb{N}}$ for $E_{j}$ , $j=1,\dots k$ , such that

\sum\limits_{j=1}^{k}w_{j}v_{j}=0.

Proof.

By Proposition 1.4 $\Pi$ comes as a corner locus of a convex piecewise-linear function $F$ on $\mathbb{R}^{n+1}$ . Let $y=a_{j,1}x_{1}+\dots+a_{j,n+1}x_{n+1}$ , $j=1,\dots,n+2$ be the equations of the linear functions on the adjacent components of $\mathbb{R}^{n+1}\smallsetminus\Pi$ . Then $u_{j}=(a_{j,1},\dots,a_{j,n+1},-1)$ are the vectors in $\mathbb{R}^{n+2}=\mathbb{R}^{n+1}\times\mathbb{R}$ normal to the linear portions of the graph of $F$ adjacent to $B$ .

The $\mathbb{R}^{n+2}$ -version of the vector product associates a normal vector to $(n+1)$ other vectors in $\mathbb{R}^{n+2}=\mathbb{R}^{n+1}\times\mathbb{R}$ . We take all possible such products among $u_{j}$ and project them to $\mathbb{R}^{n+1}$ . The result is the vectors which are multiples of $v_{j}$ . By linear algebra the sum of these vectors is zero. ∎