\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage[ngerman]{babel}
\usepackage{fullpage}
\usepackage{graphicx}

\newcommand{\ZETTELNUMMER}{1}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[1]{\vspace{0.3cm}\item[Problem \arabic{AUFGNR}]\stepcounter{AUFGNR} #1}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}

\DeclareMathOperator{\CH}{\text{CH}}
\DeclareMathOperator{\R}{\mathbb{R}}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
1st Problem Set for the MDS Block Course on

\smallskip
\noindent
\large
\textbf{High-Dimensional Computational Geometry} \\[0.5ex]
\normalsize
Helmut Alt, Wolfgang Mulzer\hfill Summer 2013

\medskip\hrule

\smallskip
\noindent
The problems will be discussed in the afternoon session.\\


%\vskip 0.5cm

\begin{description}
\AUFGABE{Examples of Polytopes} 

\begin{enumerate}
  \item Draw the face lattice for the $4$-dimensional simplex, 
    the crosspolytope, and the hypercube. Try to visualize these polytopes,
    and describe your intuition to the group.
  \item Verify the claims that we made in class about the number and structure
    of faces of the $d$-dimensional simplex, the crosspolytope, and 
    the hypercube.
\end{enumerate}

\AUFGABE{The Cyclic Polytope}

\begin{enumerate}
\item
  Use Gale's evenness criterion to prove that the number of facets 
  of the $d$-dimensional cyclic polytope with $n$ vertices is
  \[
     2 \binom{n - \lfloor d/2 \rfloor -1} {\lfloor d/2 \rfloor}
  \]
  for $d$ odd, and 
  \[
     \binom{n - \lfloor d/2 \rfloor} {\lfloor d/2 \rfloor}+
     \binom{n - \lfloor d/2 \rfloor - 1} {\lfloor d/2 \rfloor - 1}
  \]
  for $d$ even. Show that for constant $d$, the number of facets is
  $\Theta(n^{\lfloor d/2 \rfloor})$.
\item Show that the cyclic polytope is \emph{neighborly}: for
  $0 \leq j \leq \lfloor d/2 \rfloor$, every $j$-subset of vertices
  spans a $(j-1)$-face of the polytope.
\end{enumerate}

\AUFGABE{The Dehn-Sommerville Relations}

Let $\mathcal{P}$ be a simple $d$-dimensional polytope with $n$ facets.
Suppose that no two vertices
of $\mathcal{P}$ have the same $x_d$-coordinate. Direct the edges of 
$\mathcal{P}$ according to the $x_d$-direction. For $j = 0, \dots, d$,
let $h_j$ be the number of vertices in $\mathcal{P}$ with outdegree $j$.
We call $(h_0, h_1, \dots, h_d)$ the \emph{$h$-vector} of $\mathcal{P}$.

\begin{enumerate}
  \item For $i = 0, \dots, d$, let $f_i$ be the number of $i$-faces
    in $\mathcal{P}$. Show that
    \[
       f_i = \sum_{j = i}^{d} \binom{j}{i} h_j,
    \]
    for $i = 0, \dots, d$.

    \emph{Hint}: Observe that each $i$-face of $\mathcal{P}$ has a 
      unique vertex with minimum $x_d$-coordinate. Argue that a vertex
      of outdegree $j$ is the lowest point for $\binom{j}{i}$ 
      $i$-faces.
   \item Define $f(t) = \sum_{i = 0}^d f_i t^i$ and
     $h(t) = \sum_{i = 0}^d h_j t^j$.
     Show that $f(t) = h(t+1)$.
     Conclude that $h(t) = f(t-1)$.
     Derive from this an expression for each $h_j$ in terms of the $f_i$.
   \item Conclude from (b) that the $h$-vector is (almost) independent of the
     choice of the $x_d$-axis. From this, derive the 
     \emph{Dehn-Sommerville relations}:
     for $0 \leq i \leq d$, we have $h_i = h_{d-i}$.
     Write the Dehn-Sommerville relations in terms of the $f_i$.
   \item  Argue that $h_i \leq f_i \leq \binom{n}{d-i}$, for $i = 0, \dots, d$.
     Use the Dehn-Sommervile relations to conclude
     \[
       h_i \leq \min \Bigl\{ \binom{n}{i}, \binom{n}{d-i}\Bigr\}.
     \]
     Using the expression for $f_i$ in terms of the $h_j$, conclude 
     that $f_i = O(n^{\lfloor d/2 \rfloor})$, for $i = 0, \dots, d$.
\end{enumerate}

\end{description}
\end{document}
