next up previous
Next: Automorphisms of finite projective Up: Discrete Math, Second Series, Previous: Finite probability spaces.

Graphs

Definition 3.1   The right regular representation of a group $ G$ is the homomorphism $ \rho\colon G\to \Sym(G)$ given by $ g\mapsto \rho_g$, where $ \rho_g$ is the permutation that acts as $ x^{\rho_g}=xg$. The image (which is isomorphic to $ G$) is denoted $ R(G)$.

Corollary 3.2 (Cayley)   Every group is isomorphic to a permutation group.

Definition 3.3   If $ G$ is generated by a set $ S$, then the Cayley Color Diagram $ \Gamma_c(G,S)$ is the colored digraph on the vertex set $ G$ with edges pointing from $ g$ to $ sg$ labeled (colored) by $ s$ for all $ g\in G$ and $ s\in S$. Automorphisms of such a colored digraph preserve the colors by definition.


\begin{exercise}
% latex2html id marker 854
$\mathop{\rm Aut}(\Gamma_c(G,S))=R(G...
...tion commutes with left multiplication, which defines $\Gamma_c$.
\end{exercise}


\begin{exercise}
% latex2html id marker 857
{\bf (Frucht's Theorem)} For any gro...
...op{\rm Aut}(X)\cong G$. ($X$\ is an undirected, uncolored graph.)
\end{exercise}


\begin{exx}
% latex2html id marker 860
{\bf (Babai)} $X$\ can be chosen with $\l...
...vert$\ vertices, unless
$G$\ is the cyclic group of order 3, 4, or 5.
\end{exx}



Subsections

Varsha Dani 2003-08-04