Discrete Math, Second series, 2nd Problem Set (July 21)
REU 2003

Instructor: Laszlo Babai
Scribe: Mridul Mehta

Definition 0.1   A group is a set $G$ with a binary operation $G\times G \to G$ denoted by `$\cdot$' or `$+$' depending on context, satisfying:

1. $(\forall \; x, y \in G)(\exists! \; z \in G)(x \cdot y = z)$
2. $(\forall \; x, y, z \in G)((x\cdot y)\cdot z = x\cdot (y\cdot z))$
3. $(\exists \; 1_G)(\forall \; x \in G)(x \cdot 1_G = 1_G \cdot x = 1_G)$
4. $(\forall \; x \in G)(\exists \; x^{-1} \in G)(x\cdot x^{-1} = x^{-1} \cdot x = 1_G)$

Definition 0.2   We say that $H \subseteq G$ is a subgroup of $G$ (written $H \le G$) if

1. $1_G \in H$
2. $(\forall \; x, y \in H)(x\cdot y \in H)$
3. $(\forall \; x \in H)(x^{-1} \in H)$

Definition 0.3   The order of a group is the number of elements it contains, and is denoted $\vert G\vert$.

Theorem 0.4 (Lagrange)   If $G$ is finite and $H \le G$, then $\vert H\vert$ divides $\vert G\vert$.

Remark 0.5   The union of two subgroups is in general, not a subgroup. (Consider $2{\mathbb{Z}}$ and $3{\mathbb{Z}}$ inside $({\mathbb{Z}}, +)$.)

Definition 0.6   Subgroup generated by a subset $S \subseteq G$ (written $\langle S\rangle$). There are two equivalent definitions:

1. $\langle S\rangle \; = \bigcap\limits_{S\subseteq H\le G} H$
2. $\langle S\rangle \; = \left\{\textrm{ all products of generators and their inverses }\right\}$

Remark 0.7   By convention, we have $\langle \emptyset\rangle \; = \{1\}$.

A graph is an object with a given set of vertices (usually denoted $V$), which are connected by edges (denoted $E$). We usually denote the graph by $(V,E)$. A digraph is one in which the edges are directed (so that $E \subseteq V\times V$).

A Cayley graph $\Gamma$ of a group $G$ with respect to a given set of generators $S \subseteq G$ is the digraph $\Gamma(G,S) = (G, E_S)$, where $E_S = \{(g, sg)\colon g\in G, s\in S\}$.

Example 0.8   $G = ({\mathbb{Z}}, +) = \; \langle 1\rangle$. The Cayley graph is:

For example, $(2,3) \in E$ because $2 + 1 = 3$ and $1 \in S$.

Definition 0.9   A group $G$ is said to be cyclic if $\exists \; a\in G$ such that $G = \; \langle a\rangle$.

Definition 0.10   The order of an element $x \in G$ (denoted by $\ord(x)$) isdefined as the order of the cyclic subgroup generated by $x$ i.e. $\ord(x) = \vert\langle x\rangle\vert$. (So $\ord(x) = k \Rightarrow 1, x, \ldots, x^{k-1}$ are distinct and $x^k = 1$. Moreover, $x^i = x^j \Longleftrightarrow i\equiv j$ mod $k$.)

The Dihedral group of order $2n$, denoted $D_n$, is the group of symmetries (rotations and reflections) of the regular $n$-gon in the plane.

Example 0.11   $\vert D_3\vert = 6$ (group of symmetries of an equilateral triangle in the plane). If we denote the reflections by $\tau_1, \tau_2, \tau_3$ and the rotations by $1, \rho, \rho^2$ ( $\rho^3 = 1$), then $D_3 = \langle \rho, \tau_1\rangle$. Consequently its Cayley graph is:

The edges comprising the triangles correspond to multiplication by $\rho$ while the two-way arrows correspond to multiplication by $\tau$ (since $\tau$ has order 2). Following a directed edge in the opposite direction corresponds to multiplication by the inverse of the element. Each path corresponds to multiplying by the generators and/or their inverses in a particular order.

``Relation chasing'' Two different paths between the same pair of vertices give rise to two different expressions for the same group element as products of generators and their inverses. In particular, closed walks specify products of generators which equal the identity. Such products are called relations among the generators. For example, the inner triangle, from the identity to itself, shows the relation $\rho^3 = 1$. The walk of length $2$ from $1$ to $\tau$ to $1$ shows that $\tau^2 = 1$. Traversing the bottom quadrilateral clockwise shows the relation $\tau \rho \tau \rho = 1$. A more complex relation that is immediate from the diagram is $\rho \tau \rho^2 \tau \rho = 1$.

Definition 0.12   A homomorphism from a group $G$ to a group $H$ is a map $f:G \to H$ such that $f(xy) = f(x)f(y)$ for all $x, y \in G$.

Remark 0.13  

1. $f(1_G) = 1_H$.
2. $f(x^{-1}) = f(x)^{-1}$.
3. $f^{-1}(1_H) \le G$. The subgroup $f^{-1}(1_H)$ is called the kernel of $f$, denoted $\ker(f)$.

For any $g \in G$, ``conjugation by $g$'' means a map $G \to G$ given by $x \mapsto g^{-1} x g =: x^g$. Note that $\ker(f)$ is always closed under conjugation.

Definition 0.14   A subgroup $N \le G$ is called a normal subgroup if it is closed under conjugation, i.e., $(\forall \; g\in G)(N^g = N)$. We write $N \triangleleft \;G$. (Here $N^g = \{n^g\colon n\in N\}$.)

Definition 0.15   We say that a map $f:G \to H$ is an isomorphism if $f$ is a homomorphism that is both injective (one-to-one) and surjective (onto). We say $G$ and $H$ are isomorphic (notation: $G \cong H$) if $\exists f :G \to H$ isomorphism.

Definition 0.16   An automorphism of a group $G$ is an isomorphism from $G \to G$.

The automorphisms of $G$ form a group under composition, called Aut$(G)$.

Example 0.17   Aut $({\mathbb{Z}}, +) \cong ({\mathbb{Z}}_2, +)$.

Example 0.18   Aut $({\mathbb{Z}}_n, +) \cong ({\mathbb{Z}}^{\times}_{n}, \cdot\;)$.

Definition 0.19   Direct Product. Given groups $G$, $H$, their Cartesian product $G \times H = \{(g,h)\colon g\in G, h\in H\}$ is a group under componentwise multiplication.

Example 0.20   ${\mathbb{Z}}_2 \times {\mathbb{Z}}_2 = \{1, a, b, c\}$, where $a^2 = b^2 = c^2 = 1$, $ab = c, ac = b, bc = a$, and the group is abelian. This is known as Klein's 4-group and is usually denoted by $V_4$.

Definition 0.21   The center of a group $G$, is defined to be $Z(G) = \{a\in G\colon (\forall g\in G)(ga = ag)\}$.

We consider the map from $G\to \textrm{Aut}(G)$ given by $g\mapsto \{x\mapsto x^g\}$. This is a homomorphism of groups. The kernel of this map is $Z(G)$. The image of this map is the group of inner automorphisms of $G$, denoted by Inn$(G)$.

The quotient $\textrm{Aut}(G)/\textrm{Inn}(G)$ is also denoted by $\textrm{Out}(G)$, and referred to as the outer automorphism group of $G$.

Definition 0.22   Symmetric group of degree $\mathbf{n}$. This is the group of all permutations of a set of $n$ elements under composition. It is usually denoted by $S_n$. Clearly, $\vert S_n\vert = n!$.

Remark 0.23   The group $S_n$ has an important subgroup $A_n$, known as the alternating group of degree $n$ which consists of the even permutations of degree $n$. For $n \ge 2$, $\vert A_n\vert = \frac{n!}{2}$.

Definition 0.24   Bipartite graph. The bipartite graph $K_{p,q}$ is a graph with $p+q$ vertices partitioned into two sets of $p$ and $q$ vertices respectively such that no two vertices in the same set are adjacent, while every pair of vertices not in the same set are adjacent.

Example 0.25   The bipartite graph $K_{2,3}$ is: