\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
\usepackage{paralist}
\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}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\V}{\mathcal{V}}


\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 4}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Wednesday, Nov.~13, 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{Transportation Polytopes} \hfill (3+3 Points)\\[5pt]
Let $m,n \geq 1$ and $a \in \R^m$ and $b \in \R^n$ be given such that $a_i, b_j > 0$ and $\Delta = \sum_{i=1}^m a_i = \sum_{j=1}^n b_j$. We call
\begin{align*}
P = P(m,n;a,b) \coloneqq \big\{(x_{ij})_{ij} \in \R^{m \times n} \, : &\,x_{ij} \geq 0 \text{ for } 
1 \le i \le m,\,1\le j\le n,\\
&\sum_{i=1}^m x_{ij} = b_j \text{ for } 1 \le j \le n,\\
&\sum_{j=1}^n x_{ij} = a_i \text{ for } 1 \le i \le m \big\}
\end{align*}
a \Emph{transportation polytope}.
\begin{enumerate}[\normalfont (a) ]
\item What is the dimension of $P(m,n;a,b)$?% 
% \item Describe a point that lies in $P(m,n;a,b)$.\\
%    \emph{Hint:} How about $x_{ij}=\frac{a_ib_j}{\Delta^2}$?
\item\label{problem:birkhoff} 
   Let $m=n$ and $a=b=(1, \ldots, 1)$. How many vertices and how many facets does this $P(m,n;a,b)$ have? Give an explanation.
\item Describe a point that lies in $P(m,n;a,b)$.\\
   \emph{Hint:} %How about $x_{ij}=\frac{a_ib_j}{\Delta^2}$?
  Show that $x_{ij}=\frac{1}{n^2}$ yields a point for the special case of part (\ref{problem:birkhoff}). 
   Then generalize to the case where $a_i=\frac1n$ and $b_j=\frac1m$. Then generalize further.
\end{enumerate}


\vspace{20pt}

{\large\bf Problem 2: }\textit{Combinatorial Isomorphisms} \hfill (2+2(+2) Points)\\[5pt]
Two polytopes $P_1, P_2$ are called \emph{combinatorially isomorphic} if their face lattices are isomorphic.
\begin{enumerate}[\normalfont (a) ]
\item  Find two simplicial $3$-polytopes with 6 vertices each that are not combinatorially isomorphic.
\item Find two combinatorially non-isomorphic $3$-polytopes $P_1$ and $P_2$ with the same sets of vertex figures. To be more precise, there must exist a bijection $\iota \colon V_1 \to V_2$ between the vertex sets of $P_1$ and $P_2$ such that the vertex figure of $v$ is combinatorially isomorphic to the vertex figure of $\iota(v)$, for all $v \in V_1$.
\item \emph{Bonus:} Find two combinatorially non-isomorphic $4$-polytopes $P_1$ and $P_2$ with the same sets of vertex figures.
\end{enumerate}                

\vspace{20pt}
{\large\bf Problem 3: }\textit{Minkowski--Weyl Representation Theorem} \hfill (4+3+3 Points)\\[5pt]
For $d \geq 1$ let
\begin{align*}
C_d &= [-1,1]^d \text{ be the } d\text{-dimensional unit cube and}\\
C_d^* &= \conv\set{\pm e_1, \ldots, \pm e_d} \text{ be the } d\text{-dimensional crosspolytope.}
\end{align*}
For $0 \le n \le d$ let $f_n$ and $f_n^*$ denote the number of $n$-dimensional faces of $C_d$ and of $C_d^*$, respectively.
\begin{enumerate}[\normalfont (a) ]
\item Verify the Minkowski--Weyl Representation Theorem for the polytopes $C_3$ and $C_3^*$. In other words, calculate $\V$- and $\H$-representations for both polytopes.
\item Describe the $k$-dimensional faces of $C_d$ and calculate $f_0, \ldots, f_d$.
\item Describe the $k$-dimensional faces of $C_d^*$ and calculate $f_0^*, \ldots, f_d^*$.
\end{enumerate}
\end{document}
