next up previous
Next: About this document ...

Discrete Math, Second series, First Problem Set (July 18)
REU 2003

Instructor: László Babai

Definition 0.1   A product-free set in a group $ G$ is a subset $ L\subset G$ such that the equation $ xy=z$ has no solution in $ L$.

Definition 0.2   A triangle-free set in a group $ G$ is a subset $ T\subset G$ such that the equation $ xyz=1$, $ x,y,z\in G$ implies $ x=y=z$.


\begin{exercise} % latex2html id marker 651Prove that every abelian group of o... ...n/3$. Prove that this statement remains valid for solvable grops. \end{exercise}


\begin{exercise} % latex2html id marker 653Prove that $G=S_n$\ (the symmetric ... ...degree $n$) has a product-free subgroup of size $\vert G\vert/2$. \end{exercise}


\begin{exercise} % latex2html id marker 655Prove that $A_n$\ (the alternating ... ...f degree $n$) has a product-free subset of size $\vert G\vert/n$. \end{exercise}


\begin{exercise} % latex2html id marker 657Prove that $A_4$\ has a product-free subset of size $\vert G\vert/3$. \end{exercise}


\begin{exx} % latex2html id marker 659 {\bf Open questions}\ (a)\ For $n\ge 5$, ... ... product-free subset of $A_n$, does $a_n/\vert A_n\vert$\ go to zero? \end{exx}


\begin{exx} % latex2html id marker 661Analyse the previous questions regarding... ... sets. See that difficulties arise already for certain abelian groups. \end{exx}


\begin{exercise} % latex2html id marker 663Prove that the automorphism group of the cube is isomorphic to $S_4\times Z_2$. \end{exercise}


\begin{exercise} % latex2html id marker 665Prove that the automorphism group of the dodecahedron is isomorphic to $A_5\times Z_2$. \end{exercise}


\begin{exercise} % latex2html id marker 667Prove that the automorphism group of the Petersen graph is isomorphic to $S_5$. \end{exercise}


Varsha Dani 2003-08-04