\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{enumitem}
\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{11: Cayley Graphs / Schreier Diagrams}{Due Friday, Week 6}

Do \textbf{one} of the following \textbf{three} problems!   Have fun!

\begin{enumerate}
\item Let $G = \langle a, b ~|~ a^3 = id, (ba)^2 = id \rangle$, $H = \langle b \rangle$, and $S = \{a,b\}$.  What is the Schreier graph of this group/subgroup/generating set?

\item The Frobenius group of order 20 is the following group:
\begin{align*}
\langle s, t ~|~s^4 = t^5 = 1,  s^{-1}ts= t^2 \rangle
\end{align*}
Alternately, you can consider this as the subgroup of $S_5$ generated by ($2354)$ and $(12345)$.  One set of notes I came across online while researching this HW set claimed that the Cayley graph of this group is the dodecahedron.  This sharply contradicted other sources, which claim the dodecahedron (HW 10 spoilers!) is not the Cayley graph of any group.  Find the Cayley graph of this group.  Is it the dodecahedron?

\item (Zombie problem, by request!)  In Connor's presentation of the matrix-rounding problem, he assumed (as \href{https://books.google.com/books?id=1a6lSRbQ4YsC&pg=PA2011&lpg=PA2011&dq=round+a+matrix+rows+columns&source=bl&ots=ZPeTz4EDpX&sig=aP-bNZN-PujtaCC2KeP6wOLvsv0&hl=en&sa=X&ei=M0Q9VeOuB8jXsAXYh4HwBA&ved=0CC8Q6AEwAg#v=onepage&q=round%20a%20matrix%20rows%20columns&f=false}{many textbooks} do!) the following claim:
\begin{thm}
Suppose that $G$ is a network with a capacity function $c$, such that all of $c$'s values are integers.  Also suppose that there is some feasible flow $f$ on $G$.  Then there is an integer-valued maximum flow with value equal to the capacity of the minimum cut.
\end{thm}
We proved this claim for networks where the capacity function takes on nonnegative integer values.   However, we did \textbf{not} prove this claim for networks where the capacity can take on negative values (i.e. where you can have ``minimum'' capacities on edges.)

Prove this here!

(A stronger hint: By problem 1 on the previous HW, you know that there is some maximum flow $f$ ; you now just want to ``round'' this flow so that it is a maximum integer-valued flow.  Take $G$, and consider the subgraph $H$ given by the collection of all edges in $G$ where $c_{xy} - f_{xy} \notin \mathbb{Z}$.  What do you know about the degree of any vertex in $H$?  Come up with a process to repeatedly ``shrink'' $H$ until it is the empty graph, without changing the overall value of our flow!)

\end{enumerate}


\section{Extra Credit}
This is worth like three free problems on future HW iff you get a correct solution; this problem is driving me crazy after I found out that my one solution didn't work!
\begin{enumerate}
\item 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 $p$, for some value $p < 1$.
\end{itemize}
(This is the flip side of the ``infinite-resistance'' quadratic tree problem from last week.)
\end{enumerate}


\end{document}






