\documentclass[a4paper,12pt]{scrartcl}

% \usepackage[english,german]{babel} % [verfuegbare Sprachen, letzgenannte ist aktiv]

\usepackage{graphicx} % include eps graphics
\usepackage{psfrag} % .eps properly aligned, scaled, and rotated
\usepackage{wrapfig} % WRAP FIGURE [text umfliest das Bild]
\usepackage[ngerman,english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{ngerman} % Silbentrennung ect. in neuer-Rechtschreibung-deutsch
\usepackage{eurosym} % Das euro Symbol [nicht mehr]
\usepackage{color} % textcolors [RGB oder auch 68 Standardfarben]
\usepackage{enumerate} % aufzaehlungen
\usepackage{paralist} % kuerzere Aufzaehlungen
\usepackage{url} % bessere Darstellung (hyperref: auch anklickbar)
\usepackage{alltt} % ermoeglicht uninterpretierten Text (sozusagen String)
\usepackage{ae,aecompl} % ecFonts auf cmFonts zurueckfuehren
\usepackage{ifthen}
\usepackage{amsmath} % MATH allignment[Matrix,Brueche,Gleichungen]
\usepackage{amssymb} % Mathe SYMBOLE
\usepackage{amsthm} % Mathe THEOREM [theorem,lemma,proof] Gliederung
\usepackage{verbatim} % multiline comment
\parindent =0pt
\usepackage{geometry}
\geometry{
  body={},
  left=1.2in,
  right = 1.2 in,
  top=1.25in
}
\hypersetup{
  colorlinks = true,
  urlcolor = blue,
  pdfauthor = {},
  pdfkeywords = {albert haase, mathematics, mathematik},
  pdfsubject = {},
  pdfpagemode = UseNone
}

\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\s}{\mathbb{S}}
\newcommand{\su}{\mathcal{S}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ti}{\mathcal{T}}
\newcommand{\cc}{\mathcal{C}}
\newcommand{\dd}{\mathcal{D}}
\newcommand{\E}{\mathbf{E}}
\newcommand{\HRule}{\rule{1.03\textwidth}{0.5mm}}
\renewcommand\O{\mbox{\rm O}}
\renewcommand{\subset}{\subseteq}


\newcommand{\red}{\textcolor{red}} %Farben
\newcommand{\green}{\textcolor{green}}
\newcommand{\ink}{\textcolor[rgb]{0,.2,.8}}
\newcommand{\purp}{\textcolor[rgb]{0.9,0,.5}}
\newcommand{\sky}{\textcolor[rgb]{0,.5,.7}}
\newcommand{\tree}{\textcolor[rgb]{0,.4,.1}}
\newcommand\Emph[1]{\emph{\color{blue}#1}}


\newcommand{\set}[1]{\ensuremath{ \left\{ #1 \right\}}}
\newcommand{\mset}[2]{\ensuremath{\left\{ #1  :  #2 \right\}}}
\renewcommand{\mapsto}{\longmapsto}
\newcommand{\inner}[1]{\left\langle \, #1  \,\right\rangle}
\newcommand{\linspan}[1]{\ensuremath{\text{span}\left\{ #1 \right \} }}
\newcommand{\ma}{\begin{pmatrix}} \newcommand{\trix}{\end{pmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
%\linespread{1.2}

\selectlanguage{german}

\begin{document}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushleft}
\includegraphics[scale=0.09]{bms-logo-eff.pdf}\\[5pt]
{\small Prof.~G\"unter M.~Ziegler} \\
{\small Albert Haase, Marie Litz}
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
\includegraphics[scale=0.4]{fu-logo}\\[5pt]
{\small Institut f"ur Mathematik }\\
{\small Arbeitsgruppe Diskrete Geometrie}\\
\end{flushright}
\end{minipage}

\vspace{20pt}
\centerline{\Large \bf{Discrete Geometry 1 -- Problem Sheet 2}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Wednesday, Oct.~30, 2013} before the lecture begins. Please put your name and student ID (if you have one) on the first page of your solutions and staple the sheets together.

\vspace{20pt}

{\large\bf Problem 1: }\textit{Product and Minkowski Sum} \hfill (2 + 2 + 2 (+2) + 2 Points)\\[5pt]
Let $P_1$ and $P_2$ be two polytopes of dimensions $d_1$ respectively $d_2$.
\begin{enumerate}[\normalfont (a) ]
\item Show that the Cartesian product $P_1 \times P_2$ is a polytope. What is the dimension of $P_1 \times P_2$\,?
\item Prove that for every non-empty face $F$ of $P_1 \times P_2$ there are unique faces $F_1 \subseteq P_1$ and $F_2 \subseteq P_2$ such that $F = F_1 \times F_2$.
\item Assume $P_1$ and $P_2$ are both polytopes in $\R^d$ for some $d \geq 0$. Show that the \Emph{Minkowski sum} 
\[
P_1 + P_2 \coloneqq \mset{p_1 + p_2}{p_1 \in P_1 \text{ and } p_2 \in P_2}
\] of $P_1$ and $P_2$ is a polytope. \emph{Bonus:} Prove that if the Minkowski
sum of two convex sets $K_1,K_2 \subset \R^d$ is a polytope, then both $K_1$ and $K_2$ are polytopes.
\item Show that if $F$ is a non-empty face of $P_1+P_2$, there are faces $F_i \subseteq P_i$ such that $F = F_1 + F_2$ and that the choice of $F_1$ and $F_2$ is unique.
\end{enumerate}

\vspace{20pt}

{\large\bf Problem 2: }\textit{Crosspolytope} \hfill (3 + 3 Points)\\[5pt]
For $d \geq 1$ the $d$-dimensional \Emph{crosspolytope} is given by
\[
C_d^\triangle \coloneqq \conv \{ \pm e_1, \pm e_2,\dots, \pm e_d\}.
\]
Here $e_i$ denotes the $i$-th standard basis vector of $\R^d$.
\begin{enumerate}[\normalfont (a) ]

\item Let $u, v \in \{ \pm e_1, \pm e_2,\dots, \pm e_d\}$ be given such that $u \not=
\pm v$. Show that the interval $[u,v] = \conv \{u,v\}$ is an edge of $C_d^\triangle$.

\item Let $P = \conv(V)$ be a polytope and $V$ its set of vertices. We call $P$ \Emph{centrally symmetric} if $-P =P$. 
Show that a polytope $P$ is centrally symmetric if and only if $P$ is the image under a linear map of 
the $n$-dimensional crosspolytope $C_n^\triangle$ with $n = \frac{1}{2}|V|$.     
\end{enumerate}


{\large\bf Problem 3: }\textit{Adjacent Vertices -- Tetrahedron} \hfill (6 Points)\\[5pt]
Let $P$ be a polytope. Recall that vertices of $P$ are $0$-dimensional faces of $P$ and edges of $P$ are $1$-dimensional faces of $P$. Two distinct vertices $x$ and $y$ of $P$ are   \Emph{adjacent} if there is an edge $e$ of $P$ that has $x$ and $y$ as faces.\\[3pt]
Let $P$ now be $3$-dimensional and  assume that every two distinct vertices of $P$ are adjacent. Show that $P$ is a tetrahedron, that is, a $3$-dimensional simplex.
\\[3pt]
\emph{Hint:} Adroitly apply Radon's Theorem.
\end{document}
