\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{12: Schreier Graphs}{Due Friday, Week 7}

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

\begin{enumerate}
\item Suppose that $G$ is a graph generated by three elements $a, b, c$, and that the diagram below is a Schreier graph for $G$ with respect to some subgroup $H$ and these three generators.
\begin{center}
\includegraphics[width=3in]{math137b_s2014_schreierHW.pdf}
\end{center}
What is a set of generators for $H$?
\item Let $G$ be the free group on two generators $\langle a, b\rangle$, and $H$ be the subgroup generated by all of the words in $G$ containing an even number of $a$'s.
\begin{enumerate}
\item Create the Schreier graph for $G$ with respect to $H$ and the generating set $\{a, b\}$.
\item Decorate this graph to give a set of generators for $H$.  (Notice that the set of generators you get here is a \textbf{free} set of generators: i.e. there is no nontrivial combination of these generating words that results in the identity!  This is because of the result we stated very briefly in class; that the generators given by the decorations of this graph generate the subgroup, and also that the only relations here can come from the original group itself, which is free!)
\end{enumerate}
\item Let $G$ be the free group on two generators $\langle a, b\rangle$ and let $H$ denote the subgroup consisting of all words of even length.  (i.e. $aba^{-1}b^{-1}$ is in $H$, while $aba$ is not.)  
\begin{enumerate}
\item Show that $H$ is generated by the six words  $w_1 = aa, w_2 = bb, w_3 = ab, w_4 = ba, w_5 = ab^{-1}, w_6 = ba^{-1}$. 
\item  Show that this collection of six generators is \textbf{not free}: i.e.\ that there is some relation on these words $w_{i_1}^{k_1}w_{i_2}^{k_2}\ldots w_{i_n}^{k_n} = id$, for some $n, k_j \in \mathbb{Z}, i_j \in \{1,\ldots 6\}$.
\item Find a free collection of generators for $H$.
\end{enumerate}

\item On our last problem set, you were asked to show that the dodecahedron's graph is not a Cayley graph.  Consider the other platonic solids: i.e.\ the tetrahedron, the cube, the octahedron, and the icosahedron.  Which of these can be written as the Cayley graphs (when interpreted as undirected graphs) of appropriate groups?  (Hint: the group $A4$ is useful!)

\item Take the group $G = S_5$ along with the subgroup $H = S_3 \times S_2 = \{(\pi, \mu)  ~|~ \pi$ is a permutation of $\{1,2,3\}$, $\mu$ is a permutation of $\{4,5\}\}$.  

\begin{enumerate}
\item Explain why the Schreier graph of $G$ with respect to $H$ and any generating set $S$ is a graph on 10 vertices.
\item Prove or disprove: there is a generating set $S$ such that this Schreier graph (when interpreted as an undirected graph) is the Petersen graph.
\end{enumerate}
\end{enumerate}
\end{document}






