\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{10: Algebra and Graphs}{Due Friday, Week 6}

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

\begin{enumerate}
\item Recall, from last quarter, the following definitions:
\begin{defn}
Given two graphs $G_1, G_2$ with vertex sets $V_1, V_2$ and edge sets $E_1, E_2$, we say that a function $f: V_1 \to V_2$ is an \textbf{isomorphism} if the following two properties hold:
\begin{itemize}
\item $f$ is a bijection.
\item $(x,y)$ is an edge in $E_1$ if and only if $(f(x), f(y))$ is an edge in $E_2$.
\end{itemize}
An \textbf{automorphism} on a graph $G$ is an isomorphism from that graph to itself.
\end{defn}
Using this definition, we say that a graph $G$ is \textbf{vertex-transitive} if given any two vertices $v_1, v_2$ of $G$, there is an automorphism $f$ on $G$ such that $f(v_1) = v_2$.  In essence, vertex-transitive graphs have a lot of symmetry: up to the labeling, we cannot distinguish any two vertices.

Prove that any Cayley graph is a vertex-transitive graph.
\item Prove or disprove: there is a group $A$ such that the Cayley graph $G_A$ of $A$ is (after interpreting $G_A$ as an undirected\footnote{We do this as follows: take each of the directed graphs above and turn them into undirected graphs $G_1', G_2'$ by ``forgetting'' the orientations:\ that is, create an edge $\{x,y\}$ in $G'$ if and only if either $(x,y), (y,x)$ or both exist in $G$.  Notice that the resulting graph is not a multigraph, as we only connect any $x,y$ at most once.} graph) is the Petersen graph.
\item Prove or disprove: there is a group $A$ such that the Cayley graph $G_A$ of $A$, when interpreted as an undirected graph, is a dodecahedron.
\item For any $n$, find a group $G$ with generating set $S$ such that its Cayley graph (again, interpreted as an undirected graph) is a $K_n$. 
\item Let $Q_n$ denote the graph corresponding to the $n$-dimensional unit cube.  Find a group $G$ with generating set $S$ such that its Cayley graph (again, interpreted as an undirected graph) is $Q_n$. 
\end{enumerate}
\end{document}






