\documentclass[11pt]{amsart}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}

\textwidth = 6.5 in
%\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
%\topmargin = 0.0 in
%\headheight = 0.0 in
%\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newcommand{\bchoose}[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}

\title{Homework \#4 - Math 4160}
\author{Assigned: Friday November 21, 2019\hskip .2in Due: Thursday, December 5, 2019}
\begin{document}
\maketitle

Write your homework solutions neatly and clearly.  Provide full
explanations and justify all of your answers.

\begin{enumerate}
\item A simple graph consists of a set of vertices $V$ and a set of edges $E$ where an edge $e \in E$ is a subset $e \subseteq V$
of size $2$ (edges must have distinct vertices so you can't have loops of the form $\{i,i\}$).
Two graphs $G_1 = (V_1, E_1)$, $G_2 = (V_2, E_2)$ are said to be isomorphic if $|V_1| = |V_2|$
and there exists a bijection $\phi : V_1 \rightarrow V_2$ such that $\{a,b\} \in E_1$ if and only if $\{ \phi(a), \phi(b)\} \in E_2$.
The complete graph is denoted $K_n$ is the graph $(\{1,2,\ldots,n\}, \{ \{a,b\} : 1\leq a< b\leq n\})$.
Compute the number of non-isomorphic graphs with $1,2,3,4$ and $5$ vertices by counting the number of ways of coloring
the edges of the complete graph $K_r$ for $1 \leq r \leq 5$ with colors black and white
(then a representative graph is one with the edge set consists of the just the black edges of the coloring).\\
Note the for $r=1$ and $2$, you need not set this up as an application of Burnside's Lemma/P\'olya's Theorem, but for $r=3$
you can verify that Burnside's Lemma/P\'olya's Theorem gives the same answer that you compute by hand.

\item Use the principle of inclusion-exclusion to compute the number of connected graphs
with size $1,2,3,4$ and $5$ vertices.

\vskip .3in

\item The  \href{https://en.wikipedia.org/wiki/Pentakis_dodecahedron}{Pentakis Dodecahedron}
(you may want to \href{http://mathworld.wolfram.com/pdf/PentakisDodecahedron.pdf}{build your own})
has 60 triangular faces, 90 edges and 32 vertices.
Allowing for only rotations of the object
(no mirror reflections), how many elements are there in the group of symmetries of this object? 
Explain clearly your count.
List the elements of the group or at least categorize them by their cycle structure
as a permutation of the 32 vertices.

%\item The truncated dodecahedron ({\tt http://mathworld.wolfram.com/TruncatedDodecahedron.html},
%{\tt https://en.wikipedia.org/wiki/Truncated\_{}dodecahedron}) is one of the 13
%Archimedean solids.  It has 12 10-sided faces and 20 triangular faces.  
%\begin{center}
%\includegraphics[width=2in]{TruncatedDodecahedronNet.png}\hskip .5in
%\includegraphics[width=1.5in]{U26_500.png}
%\end{center}
%Allowing for only rotations of the object
%(no mirror reflections), how many elements are there in the group of symmetries of this object? 
%Explain clearly your count.  List the elements of the group as a permutation of the 8 faces.

%Explain clearly how you
%know that the of the motions of the dodecahedron form a group of order $60$.
%\begin{center}
%\includegraphics[width=1in]{dodecahedron.png}
%\end{center}
%\begin{enumerate}
%\item How many motions of the dodecahedron leave precisely two vertices fixed (no edges or faces)? Why?%10*2 = 20
%\item How many motions of the dodecahedron leave precisely two edges fixed (no vertices or faces)? Why? %15*1 = 15
%\item How many motions of the dodecahedron leave precisely two faces fixed (no vertices or edges)? Why? %6*4 = 24
%\item How do you know that there are no other motions of the group except for the identity and those
%motions  mentioned in part (a),(b),(c) ?
%\end{enumerate}

%\item If the motions of the dodecahedron are represented as a permutation of the faces, 
%pick one permutation which fixes exactly two vertices and
%give the permutation represented in cyclic notation.  Pick one permutation which fixes exactly two edges
%and give it in cyclic notation.  Find one permutation which
%fixes exactly two faces and and give it in cyclic notation.

\item  How many different (under motions of the symmetry group of rotations)
ways are there of coloring the 32 vertices of the Pentakis Dodecahedron black and white?
\item
How many ways are there of coloring the 32 vertices of the Pentakis Dodecahedron with
black and white using 16 black vertices and
16 white vertices?
\vskip .3in
\item Consider the partial order on permutations of $\{1,2,3,4\}$.  For $\pi$ a permutation
of $\{1,2,3,4\}$, define $D(\pi) = \{ i : 1\leq i \leq 3 \hbox{ and } \pi(i)>\pi(i+1) \}$.
For two permutations $\pi$, $\tau$ of $\{1,2,3,4\}$, say that $\pi <_* \tau$ if $D(\pi) \subsetneq D(\tau)$.
Draw the Hasse diagram of this order $\leq_*$.
\item Compute the values of the
M\"obius function of the form
$\mu(1234, \pi)$ for this partial order
for all permutations $\pi$ of $\{1,2,3,4\}$.
\end{enumerate}
\end{document}
