# 1. Classify some algebras

Consider the set of functions from ℤ_{m}→ℤ_{m}, where m>1, with composition as a binary operation. For each subset below, classify it as a magma, semigroup, monoid, group, or abelian group (whichever is the strongest). If the classification depends on the value of m, state for which values of m the set has each type.

The set of functions f

_{a}(x) = ax for all a in ℤ_{m}.The set of functions f

_{a}(x) = ax for all a in ℤ^{*}_{m}(that is, all a with gcd(a,m) = 1).The set of functions f

_{ab}(x) = ax+b for all a and b in ℤ_{m}.The set of functions f

_{ab}(x) = ax+b for all a in ℤ^{*}_{m}and all b in ℤ_{m}.

# 2. Group embeddings

An embedding of a group G into another group H is an injection f:G→H that is also a homomorphism; equivalently, it's an isomorphism between G and some subgroup of H.

Let (ℚ/ℤ,+) be the additive group of rationals mod 1; this is obtained by treating any two rational numbers as equivalent if their difference is an integer. Observe that we can represent each element of ℚ/ℤ as a rational in the range 0≤x<1, by rewriting p/q as (p mod q)/q.

Prove or disprove: For any m, there is an embedding of ℤ

_{m}into ℚ/ℤ.Prove or disprove: Let G be any finite group. Then there is an embedding from G into ℚ/ℤ if and only if G is cyclic, i.e. there is a fixed element g of G such that every element of G equals g

^{n}for some n∈ℕ. Hint: Given an embedding f:G→ℚ/ℤ, consider the smallest nonzero element of f(G).

# 3. Some very big graphs

For each n in ℕ-{0}, define G[n] as the graph with vertex set ℕ and with an edge between x and x+n for each x. Similarly define G[n,m] as having an edge between x and both x+n and x+m for each x, where n,m∈ℕ-{0} and n≠m.

- For which values of n is G[n] connected?
- For which values of n is G[n] acyclic?
- For which values of n and m is G[n,m] connected?
- For which values of n and m is G[n,m] acyclic?

*Clarification added 2007-12-05: G[n] and G[n,m] are undirected graphs.*

# 4. Vertex covers

A **vertex cover** of a graph G = (V,E) is a set of vertices S⊆V such that every edge in E has at least one endpoint in S. The **vertex covering number** ω_{V}(G) of a graph G is the minimum size of any vertex cover. In general, the vertex covering number is very difficult to compute, but it is not as hard for some very well-behaved graphs.

Find the vertex covering number for each of the following graphs:

The complete graph K

_{n}.The complete bipartite graph K

_{nm}.The path on with n edges P

_{n}.The n-dimension cube Q

_{n}.