\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Reza Zadeh (rezab@stanford.edu) }
{\\ \bssten HW\#1 --  Due at the beginning of class Thursday 01/26/17}
\vspace{5pt}

\begin{enumerate}
\item 
Prove that at least
one of $G$ and $\overline{G}$ is connected. Here, $\overline{G}$ is a
graph on the vertices of $G$ such that two vertices
are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$.



\item A vertex in $G$ is \textit{central} if its greatest distance from any other vertex is as small as possible.
This distance is the \textit{radius} of $G$. 

\begin{enumerate} 

\item Prove that for every graph $G$

$$ \text{rad } G \leq \text{diam } G \leq 2 \text{ rad } G$$


\item Prove that a graph $G$ of radius at most $k$ and maximum degree at most $d \ge 3$ has fewer than
$\frac{d}{d-2} (d-1)^k$ vertices.

\end{enumerate}


\item  A random permutation $\pi$ of the set $\{1, 2, \ldots, n\}$
can be represented by a directed graph on $n$ vertices with a directed arc $(i, \pi_i)$,
where $\pi_i$ is the $i$'th entry in the permutation. Observe that the resulting graph
is just a collection of distinct cycles.
\begin{enumerate}
\item  What is the expected length of the cycle containing vertex 1?
\item  What is the expected number of cycles?
\end{enumerate}

\item Let $v_1,  v_2, \ldots, v_n$ be unit vectors in $\mathbb{R}^n$. Prove that
there exist $\alpha_1, \alpha_2, \ldots , \alpha_n \in \{-1, 1\}$ such that
$$||\alpha_1 v_1 + \alpha_2 v_2 + \ldots + \alpha_n v_n||_2 \leq \sqrt{n}$$

\item Consider a graph $G$ on $2n$ vertices where every vertex has degree at least
$n$. Prove that $G$ contains a perfect matching.

\item 
Let $G=(V,E)$ be a graph and $w:E\rightarrow R^{+}$ be an assignment of nonnegative weights to its edges. For $u,v \in V$ let $f(u,v)$ denote the weight of a minimum $u-v$ cut in $G$.
\begin{enumerate}
\item Let $u,v,w \in V$, and suppose $f(u,v) \leq f(u,w) \leq f(v,w)$. Show that $f(u, v) = f(u, w)$, i.e., the two smaller numbers are equal.
\item Show that among the ${n \choose 2}$ values $f(u, v)$, for all pairs $u, v \in V$ , there are
at most $n-1$ distinct values. 
\end{enumerate}

\item Let $T$ be a spanning tree of a graph $G$ with an edge cost function $c$. We say
that $T$ has the \emph{cycle property} if for any edge $e' \notin T$, $c(e') \geq c(e)$
for all $e$ in the cycle generated by adding $e'$ to $T$. Also, $T$ has the \emph{cut
property} if for any edge $e \in T$, $c(e) \leq c(e')$ for all $e'$ in the cut defined
by $e$. Show that the following three statements are equivalent:

\begin{enumerate}
\item $T$ has  the cycle property.
\item  $T$ has the cut property.
\item $T$ is a minimum cost spanning tree.
\end{enumerate}

\textbf{Remark 1}:  Note that removing $e \in T$ creates two trees with vertex sets $V_1$
and $V_2$. A \emph{cut} defined by $e \in T$ is the set of edges of $G$ with one endpoint
in $V_1$ and the other in $V_2$ (with the exception of $e$ itself).

 \item Given a graph $G = (V, E)$, a set of vertices $D \subseteq V$ is called a \emph{dominating set} if every vertex in $V \setminus D$ is adjacent to a vertex in $D$. Suppose $|V| = n$ and the minimum degree of $G = \delta > 0$. Show that $G$ contains a dominating set of size at most:
 \begin{equation*}
\frac{n (\log(1+\delta)+1)}{1+\delta}
 \end{equation*}

 \item Consider the following scenario.  Due to large-scale flooding in a
region, paramedics have identified a set of $n$ injured people
distributed across the region who need to be rushed to hospitals.
There are $k$ hospitals in the region, and each of the $n$ people
needs to be brought to a hospital that is within a half-hour's driving
time of their current location (so different people will have
different options for hospitals, depending on where they are right
now).

At the same time, one doesn't want to overload any one of the
hospitals by sending too many patients its way.  The paramedics are in
touch by cell phone, and they want to collectively work out whether
they can choose a hospital for each of the injured people in such a
way that the load on the hospitals is \emph{balanced}: Each hospital
receives at most $\lceil n/k \rceil$ people.

Create a polynomial time algorithm that outputs an assignment of people to hospitals if a valid assignment exists and outputs no otherwise.

\end{enumerate}

\end{document}