User:MWinter4/Direct sum (polytope theory)

In polytope theory the direct sum is a binary operation on convex polytopes commonly denoted by $P\oplus Q$ or $P*Q$ . It is dual to the Cartesian product of polytopes. Like the Cartesian product, the direct sum of two polytopes of dimensions $n$ and $m$ is a polytope of dimension $n+m$ . The operation behaves well with respect to combinatorial and geometric properties of polytopes.

Geometric construction

Let $P$ be a polytope of dimension $n$ and let $Q$ be a polytope of dimension $m$ . Their direct sum can be constructed as follows: we first assume that $P$ and $Q$ are embedded into ${\mathbb {R}}^{n+m}$ so that their affine hulls intersect in a single point that lies in the relative interior of both polytopes. The direct sum $P\oplus Q$ is then the convex hull of the union $P\cup Q$ . While the geometry of the resulting polytope will depend on the choice of embedding, the combinatorics is independent of this choice.

Instead of chosing an arbitrary embedding, the following standard construction can be applied. We shall assume that both $P$ and $Q$ contain the origin in their respective relative interior. Suppose further that $P$ has vertices $p_{1},...,p_{r}\in {\mathbb {R}}^{n}$ and $Q$ has vertices $q_{1},...,q_{s}\in {\mathbb {R}}^{m}$ . Then the convex hull of the following $r+s$ points yields a realization of $P\oplus Q$ :

(p_{i},0^{m})\in {\mathbb {R}}^{n+m},i\in \{1,...,r\}

and

(0^{n},q_{j})\in {\mathbb {R}}^{n+m},j\in \{1,...,s\}

,

where $0^{n}$ denotes a list of $n$ zeros. Yet another way to write this is

\operatorname {conv} \!{\big \{}(P\times \{0^{m}\})\cup (\{0^{n}\}\times Q){\big \}}

.

The direct sum is dual to the Cartesian product. More precisely, it holds

(P_{1}\times P_{2})^{\circ }\simeq P_{1}^{\circ }\oplus P_{2}^{\circ },

where $P_{i}^{\circ }$ denotes the polar dual of $P_{i}$ and $\simeq$ means combinatorial equivalence.

The direct sum can be obtained from the join $P\star Q\subset {\mathbb {R}}^{n+m+1}$ via projection along the additional dimension.

Combinatorics

If $F$ is a proper face of $P$ , and $G$ is a proper face of $Q$ , then the convex hull of $F\cup G$ is a proper face of the direct sum (where we assume $P,Q\subseteq P\oplus Q$ ). The combinatorial type of this face is $F\star Q$ , where $\star$ denotes the join of polytopes. For $k\leq n+m-1$ the f-vector of the direct sum is

f_{k}(P\oplus Q)=\!\!\!\sum _{i+j+1=k}\!\!\!f_{i}(P)f_{j}(Q),

where $i\in \{-1,...,n-1\}$ and $j\in \{-1,...,m-1\}$ .

Given abstract polytopes ${\mathcal {P}}$ and ${\mathcal {Q}}$ , the direct sum can also be constructed combinatorially as follows. The faces of ${\mathcal {P}}\oplus {\mathcal {Q}}$ are pairs $(F,G)$ , where $F\in {\mathcal {P}},G\in {\mathcal {Q}}$ . The incidence relation is given as follows: ...

If both $P$ and $Q$ are of dimension at least two, then the edge graph of the direct sum $P\oplus Q$ is the graph join of the edge graphs of $P$ and $Q$ . In particular, $P\oplus Q$ has the same edge graph as the join $P\star Q$ . This can be use to construct polytopes of different dimensions but with the same edge graph.

Volume

The volume $P\oplus Q$ under the standard construction can be expressed in terms of the volume of $P$ and $Q$ as follows:

...

As a consequence, the Mahler volume $M(P):=\operatorname {vol} (P)\operatorname {vol} (P^{\circ })$ of the direct sum can be expressed directly.

Subdirect sum

Given polytopes $P_{1}$ and $P_{2}$ and faces $F_{i}\subseteq P_{i}$ , the subdirect sum

(P_{1},F_{1})\oplus (P_{2},F_{2})

is constructed by embedding $P_{1}$ and $P_{2}$ into affine subspaces $E_{1},E_{2}$ that intersect only in a point $E_{1}\cap E_{2}=\{x\}$ that lies in the relative interior of both $F_{1}$ and $F_{2}$ . While the resulting polytope might depend on the choice of $x$ , its combinatorics does not.

If one choses $F_{i}=P_{i}$ , then the subdirect product is the same as the direct product, that is

(P_{1},P_{1})\oplus (P_{2},P_{2})=P_{1}\oplus P_{2}.

For this reason one also writes

(P_{1},F_{1})\oplus P_{2}:=(P_{1},F_{1})\oplus (P_{2},P_{2}).

If the $F_{i}$ are vertices, then the operation is also called a vertex sum. If one choses $F_{1}$ as a vertex and $P_{2}=F_{2}=[0,1]$ as a line segment, then the operation is also called vertex splitting since one replaces the vertex $F_{1}$ by two vertices, namely, the end vertices of the interval $P_{2}=[0,1]$ .

Relations

Direct and subdirect sums are used to construct high-dimensional polytopes that are projectively unique.

Hanner polytopes are constructed by, starting from line segments, taking repeatedly Cartesian products and direct sums.