\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{5: More Flows + Zombie Problems}{Due Friday, Week 4}

Do \textbf{three} of the following \textbf{five} problems!  Also, some problems are undead (i.e. you've seen them before.)  Have fun!

\begin{enumerate}

\item  Prove a version of the max-flow min-cut theorem that has ``minimum'' capacities, defined as follows:
 \begin{thm}
Suppose that $G$ is a directed graph with source and sink nodes $s,t$.  Suppose further that $G$ comes with a capacity function $c: V(G) \times V(G) \to \mathbb{R} \cup \{\infty\}$.  Notice that $c$ can adopt negative values here, which is different from before\footnote{One natural interpretation of a ``negative'' capacity is that this is a way to enforce a mandatory \textbf{minimum} flow!  That is: suppose that we have any edge $\{x,y\}$ such that $c_{yx} = -3$.  What does this mean?  Well: it means that the total flow from $y$ to $x$ must be at most $-3$; in other words, that the total flow from $x$ to $y$ is at \textbf{least} 3!  In particular, if we have any edge $\{x,y\}$ that we want to enforce a minimum flow of $l$ and a maximum flow of $u$ from $x$ to $y$, we can set $c_{xy} = u, c_{yx} = l$.  

Again, this is a natural thing to want to consider; in plumbing, for example, you often want to insure a minimal amount of flow through your pipes to stop them from bursting when it drops below freezing in the winter.  (This motivation works less well at Santa Barbara than it does where I learned it in Chicago.)}.  As before, we say that a flow $f$ is \textbf{feasible} given these two capacity functions if $f_{xy} \leq c_{xy}$ for any pair $x,y$ of vertices in $V(G)$.

Suppose that there is \textbf{any} feasible flow $f_0$ on our graph\footnote{Unlike before, it is no longer obvious that every graph has a feasible flow: indeed, it is easy to create a graph that has no feasible flow!  For instance, suppose that the mandatory minimum flow from our source to some vertex $v$ is something huge, while the maximum flow out of $v$ is tiny; this clearly violates Kirchoff's laws!}.  Then there is a maximal flow with value equal to that of the minimal cut.
\end{thm}

\item Using (1), return to the matrix-rounding problem from last week:

Suppose that you have a $n \times n$ matrix of real numbers $A$.  Let $c_i$ denote the sum of all of the elements in the $i$-th column of $A$, and $r_i$ denote the sum of all of the entries in the $i$-th row of $A$.  A \textbf{rounding} of $A$ is the act of taking each value $a_{ij}, r_i, c_j$ and rounding these numbers either up or down to integer values.  A rounding is called \textbf{successful} if in the resulting rounded matrix $A_R$, the row and column sums are the same things as the values we chose to round the $r_i, c_j$'s to.  We give an example of a successful and an unsuccessful rounding below:
\begin{align*}
 \begin{array}{|c|c|c|c|} 
\hline0.6 &0 .8 & 2.7 & \cellcolor{lightgray}{ 4.1}\\\hline
 0.3 & 1.9 & 2.7 & \cellcolor{lightgray}{ 4.9}\\\hline
 2.3 & 0.4 & 0.4 &  \cellcolor{lightgray}{3.1} \\\hline
 \cellcolor{lightgray}{3.2} & \cellcolor{lightgray}{ 3.1} &  \cellcolor{lightgray}{5.8} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array} ~~\xrightarrow[\textrm{rounding}]{\textrm{unsuccessful}}~~   \begin{array}{|c|c|c|c|} 
\hline1 &1 & 3 & \cellcolor{lightgray}{ 5}\\\hline
 0 & 2 & 3 & \cellcolor{lightgray}{ 5}\\\hline
 2 & 0 & 0 &  \cellcolor{pink}{3} \\\hline
 \cellcolor{lightgray}{3} & \cellcolor{lightgray}{ 3} &  \cellcolor{lightgray}{6} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array},\\
 \begin{array}{|c|c|c|c|} 
\hline0.6 &0 .8 & 2.7 & \cellcolor{lightgray}{ 4.1}\\\hline
 0.3 & 1.9 & 2.7 & \cellcolor{lightgray}{ 4.9}\\\hline
 2.3 & 0.4 & 0.4 &  \cellcolor{lightgray}{3.1} \\\hline
 \cellcolor{lightgray}{3.2} & \cellcolor{lightgray}{ 3.1} &  \cellcolor{lightgray}{5.8} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array} ~~\xrightarrow[\textrm{rounding}]{\textrm{~~successful~~}}~~  \begin{array}{|c|c|c|c|} 
\hline1 &0& 3 & \cellcolor{lightgray}{ 4}\\\hline
 1 & 2 & 2 & \cellcolor{lightgray}{ 5}\\\hline
 2 & 1 & 0 &  \cellcolor{lightgray}{3} \\\hline
 \cellcolor{lightgray}{4} & \cellcolor{lightgray}{ 3} &  \cellcolor{lightgray}{5} & \multicolumn{1}{r}{} \\\cline{1-3}
 \end{array}.\\
\end{align*}
Prove, ideally using the Max-Flow-Min-Cut theorem, that every real-valued $n \times n$ matrix has a successful rounding.

Hint: Make vertices $r_1, \ldots r_n$ for all of the rows and $c_1, \ldots c_n$ for all of the columns.  Also add in a source vertex $s$ and a sink vertex $t$.  Add in edges $\{s,r_i\}, \{r_i,c_j\}, \{c_j, t\}$ for all $i,j$, with appropriate max/min capacities.   Try to find any feasible flow, and then use (1)!


\item (Problem changed on Saturday from the original, somewhat harder, problem.)  Recall that a \textbf{tree} is any graph that is connected and has no cycles.  Given a tree $T$ with a distinguished ``root'' vertex $r \in V(T)$, we defined the $k$-th level of $T$ as the collection of all vertices that are a path of length $k$ away from the root.

Prove or disprove: there is a tree $T$ with the following properties:
\begin{itemize}
\item The $k$-th level of $T$ contains $k^2$ many vertices, for every $k \in \mathbb{N}$.
\item $T$ has no ``leaf'' vertices:\ that is, every vertex in $T$ has degree at least 2.
\item A random walker starting at the root of $T$ returns to the root with probability 1.
\end{itemize}



\item The K\"onig-Egevary theorem is the following result:
\begin{thm}
Let $G$ be a bipartite graph.  Let the size of the largest set of disjoint edges in $G$ -- in other words, the size of the largest matching in $G$ -- be denoted by $\alpha'(G)$.  Let the size of the smallest collection of vertices such that every edge is incident to at least one vertex -- i.e. the size of the smallest vertex cover of $G$ -- be denoted by $\beta(G)$.  Then $\alpha'(G) = \beta(G)$. 
\end{thm}
Prove this result using max-flow min-cut!

\item Consider the following problem:
\begin{itemize}
\item You're going on a hike, and you're trying to decide what items to take with you! 
\item However, some of these items are only useful if they're brought along with others.  For example, a can of soup is only useful if you bring along a bowl, a spoon, and some means of heating the soup; your left shoe is kind of useless without a matching right shoe, and so on/so forth.  
\item As well, each of these items has an associated \textbf{cost}, in terms of their weight; for example, you probably don't want to bring a giant cooler jug of water with you, as its cost probably overwhelms its benefit.  How do you decide what items to bring with you?
\item To formalize this mathematically: suppose you have a set $J = \{j_1, \ldots j_n\}$ of items, where each item $j_i \in J$ has a cost $c_i$.  Moreover, suppose we have a collection $\mathcal{S} = \{ S_1, \ldots S_m\}$ of subsets of $J$, where each subset $S_i$ has an associated benefit $b_i$ that is triggered if and only if we take every element in $S_i$.

What collection of items $K \subset J$ will maximize our cost-benefit ratio (i.e. $\sum_{S_i \subset K} b_i - \sum_{j_i \in K} c_i$ ?)  
\end{itemize}

Given any such sets $J, \mathcal{S}$ along with their cost/benefit pairings, create a network $G$ on which a minimal cut corresponds to a optimal choice of items. 
\end{enumerate}
\end{document}