\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/21/16}
\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 Prove that there is an absolute constant $c > 0$ with
the following property. Let $A$ be an $n \times n$ matrix with pairwise distinct
entries. Then there is a permutation of the rows of $A$ so that no column in
the permuted matrix contains an increasing subsequence of length $c \sqrt{n}$.


\item At lunchtime it is crucial for people to get to the food trucks as quickly as
possible. The building is represented by a graph $G = (V, E)$, where each room, landing,
or other location is represented by a vertex and each corridor or stairway is represented by
an edge. Each corridor has an associated capacity $c$, meaning that at most $c$ people can
pass through the corridor at once. Traversing a corridor from one end to the other takes one
timestep and people can decide to stay in a room for the entire timestep.
Suppose all people are initially in a single room $s$, and that the building has
a single exit $t$. Give a polynomial time algorithm to find the fastest way to get
everyone out of the building. 


\end{enumerate}

\end{document}