\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{mathbbol}
\usepackage{verbatim} % multiline comment
\usepackage{longtable,tabulary}
\usepackage{paralist}
\parindent =0pt
\usepackage{afterpage}
\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}
\DeclareMathOperator{\degree}{deg}
\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 }}
\begin{center}
\Large
Solutions for the first exercise of Sheet 11
\end{center}

\vspace{20pt}
{\large\bf Problem 1: }\textit{The Number of Faces: Extremal Properties}\hfill (4(+3) Points)\\
Fix $d$ and let $M_i(n)$ be the maximal and $m_i(n)$ be the minimal number of $i$-faces for a simplicial $d$-polytope with $n$ vertices.
\begin{compactenum}[\normalfont(a)]
\item 
\begin{compactenum}[(i)]
\item Show that $M_i(n)$ and $m_i(n)$ are polynomials in $n$.

\bigskip
The upper and lower bound theorem gives us that the $f$-vector of a simplicial $d$-polytope on $n$ vertices is bounded by the stacked $d$-polytope on $n$ vertices and the cyclic $d$-polytope on $n$ vertices which are themselves simplicial. Thus
\begin{align*}
m_i(n)= &f_i(\text{Stack}_d(n)=)
\begin{cases}
\binom{d+1}{i+1}+(n-d-1) \binom{d}{i} & \text{for } i<d-1\\
(d+1)+(n-d-1)(d-1) & \text{for } i=d-1
\end{cases}\\
M_i(n)= & f_i(C_d(n))= \frac{n-\delta (n-i-2)}{n-i-1} \sum_{j=0}^{\lfloor \tfrac{d}{2} \rfloor} \binom{n-1-j}{i+1-j} \binom{n-(i+1)}{2j-(i+1)+\delta }
\end{align*}

Those functions are obviously polynomials in $n$.\\

\item Compute the degrees of $M_i(n)$ and $m_i(n)$.
\[\degree m_i(n) = 1\]
In order to compute $\degree M_i(n)$, note that $\binom{m}{k}:=0$ if $k<0$ or $k>m$. Using and $\lfloor \tfrac{d}{2} \rfloor \geq j$ and $n \geq d+1$ we deduce $n-(i+1) \geq 2j-(i+1)+ \delta$  and with $n \geq d+1$ and $d \geq i +1$, we get $n-1-j \geq i+1-j$, i.e. $m \geq k$ is satisfied. If we want $k$ to be non-negative we need to choose $j \le i+1$ and $j \geq \tfrac{i+1-\delta}{2}$. In that case the degree of each summand is $i+1-j+2j-(i+1)+\delta=j + \delta $ which maximizes for $j \in \min (i+1, \lfloor \tfrac {d}2 \rfloor)$. Also considering the contribution of the factor $\frac{n-\delta (n-i-2)}{n-i-1} $, we get 
\[\degree M_i(n)= -\delta + \min (i+1, \lfloor \tfrac {d}2 \rfloor) + \delta = \min (i+1, \lfloor \tfrac {d}2 \rfloor).\]
\item Compute the leading coefficients of $M_i(n)$ and $m_i(n)$.

\bigskip
The leading coefficients for $m_i(n)$ are $\binom{d}{i}$ for $i<d-1$ and $d-1$ for $i=d-1$.\\
For $M_i(n)$ the sum contributes with $\tfrac{1}{(i+1-k)!(2k-(i+1)+\delta)!}$  for $k=\min (i+1, \lfloor \tfrac {d}2 \rfloor)$ whereas $\tfrac{n-\delta (n-i-2)}{n-i-1} $ contributes with $(i+2)^{\delta}$. Therefore the leading coefficient is \[\frac{(i+2)^{\delta}}{(i+1-k)!(2k-(i+1)+\delta)!}.\]

For $k=i+1$ (i.e. $i=0, \dots, \lfloor \tfrac {d}{2} \rfloor-1$) this yields \[\frac{(i+2)^{\delta}}{(i+1-(i+1))!(2(i+1)-(i+1)))!(2(i+1)-i)^{\delta}}=\frac{1}{(i+1)!}\]
For $k = \lfloor \tfrac{d}2 \rfloor$ (i.e. $i\geq \lfloor \tfrac{d}2 \rfloor$) we obtain
\begin{align*}
\frac{(i+2)^{\delta}}{(i+1-\lfloor \tfrac{d}2 \rfloor)!(2\lfloor \tfrac{d}2 \rfloor-(i+1)+\delta)!}=&\frac{(i+2)^{\delta}}{(i+1-\lfloor \tfrac{d}2 \rfloor)!(d-(i+1))!}\\=&\frac{(i+2)^{\delta}}{\lfloor \tfrac{d}2 \rfloor!} \binom{\lfloor \tfrac{d}2 \rfloor}{d-(i+1)}
\end{align*}

\end{compactenum}

Another approach to analyze the $f$-vector of the cyclic polytope would be to use the fact that $C_d(n)$ is neighborly. This means we know roughly half of the entries of the face vector already.
\[
f_i(C_d(n)) =  \binom{n}{i+1} \;\; \text{for } i < \lfloor \tfrac {d}2 \rfloor.
\]
Then use Dehn-Sommerville and the formulae to compute the $h$-vector from the $f$-vector and vice versa and argue why the functions are polynomials, deduce the degree and the leading coefficients
\[\begin{cases}
\binom{ \frac{d}{2}}{i+1-\frac{d}{2}} \frac{1}{ \frac{d}2 !} & \text{ for even $d$}\\
\left( \binom{\lceil \frac{d}{2} \rceil}{i+1-\lfloor \frac{d}{2} \rfloor}+ \binom{\lfloor \frac{d}{2} \rfloor}{i+1-\lceil \frac{d}{2} \rceil} \right) \frac{1}{\lfloor \frac{d}2 \rfloor!} & \text{ for odd $d$.}
\end{cases}
\]
Simple calculations show that the two formulae for the leading coefficient of $M_i(n)$ are actually identical.

\bigskip
\item \emph{Bonus:} What can be said if the polytope is not required to be simplicial?

\bigskip
Sketch: In that case $M_i(n)$ is still given by the cyclic polytope but the lower bound theorem doesn't apply anymore. For fixed $d$ the polar of $C_d(n)$ gives an infinite family of counterexamples.
\end{compactenum}
\end{document}


