\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}
\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 remaining exercise of the Xmas Sheet
\end{center}

\vspace{20pt}
{\large\bf Problem 3: }\textit{The ``fractional cube slice polytopes'' }\\% \hfill (17(+4) Points)\\
For an odd integer $\ell$, $1\le \ell\le 2d-1$ let 
    \begin{align*}
        \Delta_{d-1}(\tfrac\ell2):= &\ \{x\in[0,1]^d:x_1+\dots+x_d=\tfrac\ell2\}.
    \end{align*}
    \begin{compactenum}[(i)]
    \setcounter{enumi}{3}
        \item Study how the hyperplane $H_{\ell/2}=\{x\in\R^d:x_1+\dots+x_d=\frac\ell2\}$ 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}(\frac\ell2)$ arise from faces of~$[0,1]^d$. \hfill  ((2) Points)
            
\bigskip

The reasoning goes as in the previous problem sheet. Every $k$\nobreakdash-\hspace{0pt}face of the  $d$\nobreakdash-\hspace{0pt}cube is described by the set of coordinate entries which are fixed to 1, which we call $A$, the set of coordinate entries which are fixed to 0, which we call $B$, and the set of entries that varies between 0 and 1, called $C$, and $\vert C \vert = k$. Denote $\vert A \vert$ with $a$. Then the resulting face of the fractional hypersimplex is combinatorially equivalent to $\Delta_{k-1}(\tfrac\ell2 - a)$.\\
Vice versa every $(k-1)$\nobreakdash-\hspace{0pt}face of $\Delta_{d-1}(\tfrac \ell2)$ gives rise to a $k$\nobreakdash-\hspace{0pt}dimensional face of the cube. This face is defined by the fixed 0 and 1 entries of $\Delta_{d-1}(\tfrac \ell2)$.
                        
            
        \item Give a $\VV$-description of $\Delta_{d-1}(\frac\ell2)$.\hfill  ((1) Point)
        
\bigskip
The vertices of $\Delta_{d-1}(\tfrac \ell2)$ are the midpoints certain edges, namely the edges which connect one vertex of the cube whose entries sum to $\tfrac{\ell-1}{2}$ and one whose entries sum to $\tfrac{\ell+1}{2}$.
\[\text{vert}(\Delta_{d-1}(\tfrac \ell2))=\{ x \in \R^d: x \text{ has $\tfrac{\ell-1}2$ ones, one $\tfrac12$ and zeros otherwise}\}
\]
        
        \item Show that $\Delta_{d-1}(\frac\ell2)$ and $\Delta_{d-1}(d-\frac\ell2)$ are congruent. 
          Derive that for odd $d$, $\Delta_{d-1}(\frac d2)$ is {centrally symmetric}. \hfill  ((1) Point)
          
\bigskip
Just as in the last exercise sheet, the map $x \mapsto \mathbb{1} - x$ maps $\Delta_{d-1}(\tfrac\ell2)$ to $\Delta_{d-1}(d-\tfrac\ell2)$. The map is a reflection through the centroid $(\tfrac12, \dots, \tfrac12)$. Therefore the polytopes are congruent. We have $d-\tfrac{d}2 =\tfrac d2$, so for odd $d$ we can build the fractional hypersimplex $\Delta_{d-1}(\tfrac d2)=\Delta_{d-1}(d-\tfrac d2)=-\Delta_{d-1}(\tfrac d2)$.            
          
        \item For $\Delta_{d-1}(\frac12)$ and $\Delta_{d-1}(\frac{2d-1}2)$ are simplices. 
         Show that for $3\le\ell\le2d-3$, $\Delta_{d-1}(\frac\ell2)$ has $2d$ facets. What are their combinatorial types? There are two different combinatorial types, except in the case $\ell=d$, for odd $d$. \hfill ((2) Points)
         
\bigskip         
The cube is simple, so $\Delta_{d-1}(\frac12)$ and $\Delta_{d-1}(\frac{2d-1}2)$ must be simplices. For all other possible polytopes $\Delta_{d-1}(\frac \ell2)$, we look at the facets of the cube. Each facet is characterized by a coordinate $i$ which is fixed to 1 or 0. For all $3\le\ell\le2d-3$, there exist $x_j \in (0,1)$, $j \in [d]\setminus \{i\}$, with one value $x_i$ set to 1 or 0 that satisfy $x_1 + \dots +x_d=\tfrac \ell2$, so every facet as an interior point that lies in $\Delta_{d-1}(\frac \ell2)$. Thus every facet of the cube yields at least one face of the hypersimplex. It cannot be more than one because we intersected with a hyperplane and $\Delta_{d-1}(\frac \ell2)$ does not contain a whole face of the cube.
        \item  State and prove a formula for the $f$-vector of $\Delta_{d-1}(\frac\ell2)$.  \hfill ((4) Points)
        
\bigskip
Again, following the line of reasoning from the previous exercise sheet, we obtain for all $1 \le i\le d$
\begin{align*}
          f_{i-1}(\Delta_{d-1}(\tfrac \ell 2))
          & = \big|\{[d]=A\uplus B\uplus C\,:\, |A|<\tfrac \ell 2, |B|<d-\tfrac \ell 2, |C|=i\}\big| \\
          & = \sum_{\substack{ 0\le s\le \tfrac {\ell-1} 2 \\ \tfrac {\ell+1} 2 \le s+i\le d}} {d \choose s}{d-s \choose i} \\
          & = \sum_{\max\{0,\tfrac {\ell+1}2-i\}\le s \le\min\{ \tfrac {\ell-1}2,d-i\}}\frac{d!}{s!i!(d-s-i)!}.\\
\end{align*}        

         \item Compute and plot the $f$-vectors of
          $\Delta_{42}(\frac{13}2)$, $\Delta_{42}(\frac{23}2)$, $\Delta_{42}(\frac{33}2)$, and $\Delta_{42}(\frac{43}2)$. \\
          \mbox{}\hfill ((2) Points)
          
\bigskip
The $f$-vectors were computed in sage (which is accessible on all math/computer science computers at the FU and can be downloaded (\url{http://www.sagemath.org/}) and used online (\url{http://www.sagenb.org/} or \url{https://cloud.sagemath.com/}).


The necessary syntax: 
\begin{compactenum}[.]
\item \texttt{range (k,l)} gives $[k, k+1, \dots, l-1]$ and \texttt{range (l)} gives $[0, \dots, l-1]$,
\item \texttt{sum f(x) for x in range (k,l)} gives the sum
\item For given n \texttt{[binomial(n,m) for m in range (k,l)]} computes $[\binom{n}{k}, \dots, \binom{n}{l-1}]$ 
\item \texttt{zip(a,b)} creates a list of tuples $(a_i,b_i)$ from lists a,b
\item \texttt{list\_plot(c)} plots a list c of tuples
\end{compactenum}

\bigskip
Now, for the first polytope, we obtain 
\begin{table}[!h]
\texttt{
\begin{tabulary}{\textwidth}{LL}
sage: & d=43\\
sage: & l=13\\
sage: & f=[sum(binomial(d,s)*binomial(d-s,i) for s in range (max(0, (l+1)/2-i),1+min((l-1)/2,d-i))) for i in range (1,d)] \\
\lbrack 225568798,&\\
 4736944758,&\\
\dots & \\
 3612,&\\
 86\rbrack &\\
 sage: & list\_plot(zip(range(1,d),f)) 
 \end{tabulary}     
}
\end{table}

\end{compactenum}
       

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{../../figures/Xmas1.png}
\caption{$f$-vector of $\Delta_{42}(\frac{13}2)$}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{../../figures/Xmas2.png}
\caption{$f$-vector of $\Delta_{42}(\frac{23}2)$}
\end{figure}

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.6]{../../figures/Xmas3.png}
\caption{$f$-vector of $\Delta_{42}(\frac{33}2)$}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{../../figures/Xmas4.png}
\caption{$f$-vector of $\Delta_{42}(\frac{43}2)$}
\end{figure}      
\bigskip
\afterpage{\clearpage}    
Apparently, for increasing $\ell$ the maximum of the curve shifts to the left.
%\includegraphics[scale=0.6\textwidth]{Xmas1.png}
\end{document}


