\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{soul}
\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}
\graphicspath{{../../figures/}}
\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}}
\DeclareMathOperator{\im}{im}
\newcommand\Stack{\mathrm{Stack}}


\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}}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\VV}{\mathcal{V}}

\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{smallmatrix} } \newcommand{\trix}{\end{smallmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
\linespread{1.3}

\selectlanguage{german}

\begin{document}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushleft}
\includegraphics[scale=0.09]{bms-logo-eff}\\[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 9}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Wednesday, Dec.~18, 2013} before the lecture begins. 

\vspace{20pt}
{\large\bf Problem 1: }\textit{The ``cube slice polytopes'' }\hfill (17(+4) Points)\\
For $1\le k\le d$ let 
    \begin{align*}
        \Delta_{d-1}(k):= &\ \{x\in[0,1]^d:x_1+\dots+x_d=k\}\\
                        = &\ \conv\{x\in\{0,1\}^d:x_1+\dots+x_d=k\}.
    \end{align*}
    \begin{compactenum}[(i)]
        \item Show that $\Delta_{d-1}(k)$ is affinely equivalent to 
            \begin{align*}
            \Delta'_{d-1}(k):= &\ \{x\in[0,1]^{d-1}:k-1\le x_1+\dots+x_{d-1}\le k\}\\
                             = &\ \conv\{x\in\{0,1\}^{d-1}:k-1 \le x_1+\dots+x_{d-1}\le k\}.
            \end{align*}
            (2 Points)
        \item Describe $\Delta_3(2)$. (1 Point)
        \item Study how the hyperplane $H_k=\{x\in\R^d:x_1+\dots+x_d=k\}$ cuts the faces of 
            the $d$-cube $[0,1]^d$. What do the resulting faces look like? Conversely, describe how the faces of $\Delta_{d-1}(k)$ arise from faces of~$[0,1]^d$. (Hint: Distinguish vertices from higher dimensional faces!) (2 Points)
        \item Let $k \in \set{1,\ldots, d-1}$. Show that the $\HH$-description and the $\VV$-description in the definition of
          $\Delta_{d-1}(k)$ give the same $(d-1)$-polytope. (2 Points)
        \item Show that $\Delta_{d-1}(k)$ and $\Delta_{d-1}(d-k)$ are combinatorially equivalent. (1 Point)
        \item Show that for even $d$, $\Delta_{d-1}(\frac d2)$ is \emph{centrally symmetric}, i.e. there is a center point $c$ such that for all $ x \in \R^d$, $c+x \in \Delta_{d-1}(\frac d2)$ if and only if $c-x \in \Delta_{d-1}(\frac d2)$. (1 Point)
        \item Show that $\Delta_{d-1}(1)$ and $\Delta_{d-1}(d-1)$ are simplices. (1 Point)
        \item Show that for $1<k<d-1$, $\Delta_{d-1}(k)$ has $2d$ facets. What are their combinatorial types? There are two different combinatorial types, except in the case $k=\frac d2$. (2 Points)
        \item A polyope is \emph{$k$-simple} if its dual is $k$-simplicial. Show that $\Delta_{d-1}(k)$ is $2$-simplicial and $(d-2)$-simple. (2 Points)
        \item Describe $\Delta_4(2)$: compute the $f$-vector, describe the facets. (1 Point)
        \item[(xi)] \emph{Bonus:} Show that the $f$-vector of $\Delta_{d-1}(k)$ is given by
          \begin{align*}
          f_{i-1}(\Delta_{d-1}(k))
          & = \big|\{[d]=A\uplus B\uplus C\,:\, |A|<k, |B|<d-k, |C|=i\}\big| \\
          & = \sum_{\substack{ 0\le s<k \\ k<s+i\le d}} {d \choose s}{d-s \choose i} \\
          & = \sum_{\max\{-1,k-i\}<s<\min\{k,d-i+1\}}\frac{d!}{s!i!(d-s-i)!}
          \end{align*}
          for $i>1$. How about $f_0$?\\
          (Hint: Every $i$-face of $[0,1]^d$ can be described in the form 
          \[
          \{x\in \R^d: x_j=1 \text{ for } j\in A,\, x_j=0 \text{ for } j\in B,\, 0 \le x_j \le 1 \text{ for } j\in C\},
          \]
          for suitable sets $A,B,C$ satisfying $A \uplus B \uplus C =[d]$ and $|C|=i$.) ((4) Points)
         \item[(xii)] Compute and plot the $f$-vector of
          $\Delta_{41}(21)$. You may use (xi). (2 Points)
    \end{compactenum}
       
\end{document}
