/Solutions

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.

1. The set of functions f_a(x) = ax for all a in ℤ_m.

2. The set of functions f_a(x) = ax for all a in ℤ^*_m (that is, all a with gcd(a,m) = 1).

3. The set of functions f_ab(x) = ax+b for all a and b in ℤ_m.

4. 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.

1. Prove or disprove: For any m, there is an embedding of ℤ_m into ℚ/ℤ.

2. 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ⁿ 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.

1. For which values of n is G[n] connected?
2. For which values of n is G[n] acyclic?
3. For which values of n and m is G[n,m] connected?
4. 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:

1. The complete graph K_n.

2. The complete bipartite graph K_nm.

3. The path on with n edges P_n.

4. The n-dimension cube Q_n.