\documentclass[12pt,
               a4paper,
               article,
               oneside,
               oldfontcommands,
               UKenglish]{memoir}


\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[scaled]{beramono}
\usepackage[final]{microtype}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage{babel}
\usepackage{csquotes}
\usepackage[nodayofweek]{datetime}
\usepackage{listings}
\lstset{basicstyle = \ttfamily}
\usepackage{textcomp}
\usepackage{siunitx}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage[colorlinks, allcolors = uiolink]{hyperref}


\usepackage{tikz}
\usetikzlibrary{
  graphs,
  graphs.standard
}
\renewcommand*{\chaptitlefont}{\Large\bfseries\sffamily\raggedright}
\setsecheadstyle{\large\bfseries\sffamily\raggedright}
\setsubsecheadstyle{\large\bfseries\sffamily\raggedright}
\setsubsubsecheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setparaheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setsubparaheadstyle{\normalsize\bfseries\sffamily\raggedright}
\setbeforesubsubsecskip{2ex}
\setaftersubsubsecskip{1ex}


\pretolerance = 2000
\tolerance    = 6000
\hbadness     = 6000


\renewcommand{\sfdefault}{phv}
\definecolor{uiolink}{HTML}{0B5A9D}


\declaretheorem[style = definition]{problem}
\declaretheorem[style = definition, sibling = problem]{exercise}


\begin{document}


\begin{titlingpage}
    \vspace*{-8em}
    \setlength{\parskip}{1.5ex plus 0.5ex minus 0.2ex}
    \setlength{\parindent}{0pt}

    \begin{flushright}
        \small\today
    \end{flushright}

    \begin{center}
        \vspace{2em}
        {
            \bfseries\sffamily\huge
            MAT2250 
             \textthreequartersemdash\ Discrete Math
        }
        \vskip0.2ex
        \Large
        Mandatory assignment 1 of 1
        \vskip1ex
    \end{center}

    \subsubsection*{Submission deadline}
    Thursday 14\textsuperscript{th} March  \the\year, 14:30 in Canvas
    (\href{https://canvas.uio.no}{\underline{canvas.uio.no}}).

    \subsubsection*{Instructions}
    You can choose between scanning handwritten notes or typing the solution directly on a computer (for instance with \LaTeX).
    The assignment must be submitted as a single PDF file.
    Scanned pages must be clearly legible.
    The submission must contain your name, course and assignment number.

    It is expected that you give a clear presentation with all necessary explanations.
    Remember to include all relevant plots and figures.
    Students who fail the assignment, but have made a genuine effort at solving the exercises, are given a second attempt at revising their answers.
    All aids, including collaboration, are allowed, but the submission must be written by you and reflect your understanding of the subject.
    If we doubt that you have understood the content you have handed in, we may request that you give an oral account.

    In exercises where you are asked to write a computer program, you need to hand in the code along with the rest of the assignment.
    It is important that the submitted program contains a trial run, so that it is easy to see the result of the code.

    \subsubsection*{Application for postponed delivery}
    If you need to apply for a postponement of the submission deadline due to illness or other reasons, you have to contact the Student Administration at the Department of Mathematics (e-mail: \href{mailto:studieinfo@math.uio.no}{studieinfo@math.uio.no}) well before the deadline.

    All mandatory assignments in this course must be approved in the same semester, before you are allowed to take the final examination.

    \subsubsection*{Complete guidelines about delivery of mandatory assignments:}
    \unskip
    \begin{center}
        \unskip
        \href{http://www.uio.no/english/studies/admin/compulsory-activities/mn-math-mandatory.html}
        {
            \resizebox{\textwidth}{!}
            {\underline{uio.no/english/studies/admin/compulsory-activities/mn-math-mandatory.html}}
        }
        \vspace{1ex}
        \vfill
        GOOD LUCK!
    \end{center}
\end{titlingpage}


\noindent
{\bf 
You are highly encouraged to collaborate with other students on the problem set.  If you need help connecting with others in the course, let me know by email. 
You must include the names of any students who you collaborated with. Remember: the write up of all solutions must be your own! }


\noindent

\begin{problem}{\bf Counting integer points} 


\noindent For a bounded subset $S \subset \mathbb{R}^d$, let $n \cdot S = \{nv \ | \ v \in S\}$  
and 
$$L_{S}(n) = |  \{ v \in n\cdot S \cap \mathbb{Z}^d\}|.$$ In other words, $L_S(n)$  counts the number of  points in the $n$-th dilate of $S$ with integer coordinates.
\begin{enumerate}
\item Determine the counting function $L_{Q}(n)$ for the  cube $Q$ in $\mathbb{R}^3$ defined by 
$$Q  = \{(v_1, v_2, v_3)   \ | \ 0 \leq v_i \leq 1  \ \forall  \ i \}.$$
Notice that: $L_{Q}(1) = 8$,  $L_{Q}(2) = 27 \dots$. 

Give a closed formula for  the generating function $$F_{Q}(z) = \sum_{n = 1} L_{Q}(n) z^n.$$



\item For $S $ a bounded set in $\mathbb{R}^d$ define the following multi-variable generating function:

$$G_S (z, w_1, w_2, \dots, w_d) = \sum_{n = 1}^{\infty} \sum_{(a_1, \dots, a_d) \in n \cdot S \cap \mathbb{Z}^d} w_1^{a_1} \dots w_d^{a_d} z^n.$$  
Let ${\bf{e}}_1, \dots, {\bf{e}}_d$ be  the standard basis vectors in $\mathbb{R}^d$, and let $T_d$ be the simplex 
in $\mathbb{R}^d$ with the $d+1$ vertices $$(0, \dots, 0), \bf{e}_1 , \dots ,   e_d.$$
Notice that  $T_d = \{ (a_1, \dots, a_d) \ | \ 0  \leq a_i \text{ and }  \sum a_i \leq 1 \}$. 

 

Show that  
$$G_{T_d} (z, w_1, \dots, w_d) = \frac{1}{1-z}  \cdot \prod_{i = 1}^d \frac{1}{1-zw_i}.$$
Conclude that $F_{T_d}(z) = \frac{1}{(1-z)^{d+1}}$ and that $L_{T_d}(n) = \binom {d + n} {n} $ by using known formulas for generating functions.

{\bf Hint:} Use that $n \cdot T_d = \{ (a_1, \dots, a_d) \ | \ 0  \leq a_i \text{ and }  \sum a_i \leq n \}$ and recall how we came up with the generating functions of partitions. 

\item Consider the hexagon $H$ in $\mathbb{R}^2$ with vertices $(1, 0), (2, 0), (2, 1), (1, 2), (0, 2), (0, 1).$


 \begin{center}\newcommand\size{3}

\begin{tikzpicture}

\draw [thick,black] (1,0)-- (0, 1); 
\draw [thick,black] (1,0)-- (2, 0) ;
\draw [thick,black] (0,1)-- (0,2); 
\draw [thick,black] (2,0)-- (2,1) ; 
\draw [thick,black] (0,2)-- (1, 2)  ;
\draw [thick,black] (2,1)-- (1, 2)  ;
\node[circle,fill=black,scale = 0.3] at (1, 0)    {};
\node[circle,fill=black,scale = 0.3] at (0,1)    {};
\node[circle,fill=black,scale = 0.3] at (2, 0)    {};
\node[circle,fill=black,scale = 0.3] at (1, 2)    {};
\node[circle,fill=black,scale = 0.3] at (2, 1)    {};
\node[circle,fill=black,scale = 0.3] at (0, 2)    {};
\node[circle,fill=black,scale = 0.3] at (1, 1)    {};
 \end{tikzpicture}
 \end{center}
 
 Notice that $L_H(1) = 7$ and  $L_H(2) = 19$.
 
 
 Find a 
decomposition of $H$ into triangles of area $1/2$ and use inclusion-exclusion to find the generating function $F_H(z)$ and a closed formula for $L_H(n)$. 

 

Use without proof the fact that any triangle $T$ in $\mathbb{R}^2$ with vertices in $\mathbb{Z}^2$ and $\text{Area}(T) = 1/2$ satisfies  
$L_T(n) = L_{T_2}(n)$ where $T_2$ is the triangle from above. 


\end{enumerate}
 
\end{problem}

\vspace{1cm}

\begin{problem}{\bf Graph labelings}

\noindent Let $G = (V, E) $ be a graph with $|V| = n$. A map $f: V \to \{1, \dots , t\}$ is called an admissible vertex labeling if 
$f(v) \neq f(v')$ whenever $vv'$ is an edge of $G$. 
Let $P_G(t)$ denote the number of admissible vertex labelings of a graph $G$ with the set $\{1, \dots, t\}$. 


\begin{enumerate}
 
\item Let $P_n$ be a path with $n$ vertices. Show that 
$$P_{P_{n }} (t) = t(t-1)^{n-1}.$$

\item 
Let $C_n$ be the circuit graph with $n$ vertices.  
Use a counting argument to show that 
$$ P_{P_{n}}(t) =  P_{C_n}(t) + P_{C_{n-1}}(t),$$
and conclude that 
$$P_{C_n}(t) = (t-1)^n + (-1)^n(t-1).$$

\item 
Show that $G$ is a tree if and only if $P_G(t) = t(t-1)^{n-1}$.  

\end{enumerate}

\end{problem}

\newpage
\begin{problem}
{\bf Greedy algorithms} 

\noindent Consider the graph $G$ with weight function prescribed along its edges:


 \begin{center}\newcommand\size{3}

\begin{tikzpicture}

\draw [thick,black] (0,0)-- (18:\size)  node [above, midway] {3};
\draw [thick,black] (0,0)-- (90:\size)  node [left, midway] {2};
\draw [thick,black] (0,0)-- (162:\size)  node [above, midway] {1};
\draw [thick,black] (0,0)-- (234:\size)  node [above, midway] {1};
\draw [thick,black] (0,0)-- (306:\size)  node [above, midway] {3};


  \draw[thick,black]  (18:\size)--(90:\size) node [above, midway] {4}; 
    \draw[thick,black]  (90:\size)--(162:\size) node [above, midway] {2}; 
    \draw[thick,black]  (162:\size)--(234:\size) node [left, midway] {3}; 
    \draw[thick,black]  (234:\size)--(306:\size) node [above, midway] {2}; 
     \draw[thick,black]  (18:\size)--(306:\size) node [right, midway] {4}; 
     
      \node[black,circle,draw, fill= white, inner sep=2pt] at (18:\size){$u_1$}; 
  \node[black,circle,draw, fill= white, inner sep=2pt] at (90:\size){$u_0$}; 
   \node[black,circle,draw, fill= white, inner sep=2pt]at (162:\size){$u_4$}; 
      \node[black,circle,draw, fill= white, inner sep=2pt] at (234:\size){$u_3$}; 
       \node[black,circle,draw, fill= white, inner sep=2pt] at (306:\size){$u_2$}; 
         \node[black,circle,draw, fill= white, inner sep=2pt] at (0:0){$u_5$}; 
 \end{tikzpicture}
 \end{center}
 
\begin{enumerate}

\item Run Dijkstra's algorithm from starting vertex  $u_0$ to find a tree containing all minimal weight paths from $u_0$ with the prescribed weight function. 
Write down which edge and vertex is selected at each step of the algorithm. 

What is the length of the shortest weighted path in $G$ from $u_0$ to $u_3$?


\item Run Kruskal's algorithm to find a minimal spanning tree of $G$ for the given weight function. 
 
What is the weight of a  minimal spanning tree in $G$?
Is there a unique minimal spanning tree in $G$ with this weight function?

\item Show that if the greedy algorithm for selecting an optimal basis of a matroid can select two distinct bases  $B_1$ and  $B_2$ of minimal weight, then there must exist 
$s_1 \in B_1$ and $s_2 \in B_2$ such that $w(s_1) = w(s_2)$. 
Conclude that if the weight function $w : S \to \mathbb{R}$  is an injective  map then the greedy algorithm selects a unique minimal basis of a matroid.

Find an example of a weighted graph which shows that the converse to the above statement is false. Namely that there is a graph $G$ with weight function  $w : E \to \mathbb{R}$  which is not injective but the greedy algorithm still selects a unique minimal spanning tree. 


\end{enumerate}

\end{problem}



\end{document}