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.

1.1. Solution

Let's do some of this in bulk. First observe that composition is associative, so the worst we can get is a semigroup. Second, the identity function f(x) = x = 1x = 1x+0 fits in all four sets, so we can upgrade to monoids. To get a group, we need inverses, and to get an abelian group, we also need fg = gf for all functions in the set. These we will check individually.

1. Monoid only. The function f(x) = 0x has no inverse.

2. Abelian group. We have from the extended Euclidean algorithm that a has a multiplicative inverse in ℤ_m whenever gcd(a,m) = 1, so in this case f[a^-1]f[a](x) = a^-1ax = x gives an inverse function for each f_a in the set. We also have that f_af_b(x) = abx = bax = f_bf_a(x) for all x, showing that f_af_b = f_bf_a. (If we are being really careful, we might also want to prove closure; i.e., that gcd(ab,m) = 1 when gcd(a,m) = gcd(b,m) = 1, but this is not too hard.)

3. Monoid. It still contains f(x) = 0x.

4. We always get a group, because given y = f_ab(x) = ax+b, solve for x as a^-1(y-b) = a^-1y + (-a^-1b); this gives an inverse for each f_ab. But the group may or may not be abelian depending on m:

   • For m=2, the only a with gcd(a,m)=1 is 1. This gives exactly two functions f:x↦x and g:x↦x+1. Since f is the identity function, fg = gf; we also have f=f^-1 and g=g^-1; thus for m=2, we get an abelian group.

   • For larger m, take f = x+1 and g = ax, where a≠1 and gcd(a,m) = 1. Now fg(0) = a0+1 while gf(0) = a(0+1) = a ≠ 1. So for m>2 we get a group, but it's not abelian.

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

2.1. Solution

1. Proof: For each n in 0..m-1, let f(n) = n/m. This is clearly an injection. Given x and y in ℤ_m, we have f(x)+f(y) = x/m+y/m = (x+y)/m = ((x+y) mod m)/m = f(x+y). So f is an embedding of ℤ_m into ℚ/ℤ.

2. Proof: Let f:G→ℚ/ℤ be an embedding. Let x be such that f(x) is the smallest nonzero element of f(G). There are now two cases:
   1. Every element y is of the form nx for some n∈ℤ, i.e. x generates G. In this case G is cyclic.

   2. There exists some y such that y≠nx for any n. Let m=⌊f(y)/f(x)⌋, i.e. choose m such that mf(x)≤f(y)<(m+1)f(x). Then 0 < f(y)-mf(x) < f(x). But f(y)-mf(x) = f(y-mx) is the image of some element y-mx of G, contradicting the assumption that f(x) is 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?

3.1. Solution

1. Consider any path v₀v₁...v_k in G[n]. We have v_i+1 = v_i±n, so in particular we have v_i+1 ≡ v_i (mod n). A simple induction then shows that v₀ ≡ v_k (mod n), so v₀ is in the same connected component as v_k if and only if they are in the same congruence class (mod n). So the graph is connected only if there is exactly one congruence class mod n, i.e., if n=1.

2. G[n] is always acyclic. Suppose v₀v₁...v_k is a path with no duplicate edges. We'll argue that the sequence of vertices is monotone (always increasing or always decreasing), so in particular we get that v_k≠v₀. Suppose that v₀ < v₁. Then v₁=v₀+n. We will now prove by induction that v_i=v₀+in. The base case of i=1 is already established. Now suppose that v_i-2=(i-2)n and v_i-1=(i-1)n. Now v_i-1 has only two incident edges, and we've already used one of them, so v_i must be reach through the other one: v_i = v_i-1+n = (i-1)n+n = in. So if v₀ < v₁, then v_k≠v₀ and we don't have a cycle. But the case v₀ > v₁ is symmetric, so we don't get a cycle there either.

3. G[n,m] is connected just in case gcd(n,m) = 1. Proof: if gcd(n,m) = g > 1, then we can repeat the same argument as for just n mod g. Otherwise, use extended Euclid to find k and l such that kn+lm = 1. One of k or l is positive; if it's k, construct a path from 0 to 1 by going up n steps k times then down m steps (-l) times, and repeat to get from x to x+1 for each larger x. If l is positive, do the reverse.

4. G[n,m] is never acyclic: it contains the cycle 0,m,2m,...nm,m(n-1),m(n-2),...0.

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.

4.1. Solution

1. The easiest way to find this is to start with some small cases: for K₁ there are no edges, so ω_V(K₁) = 0. For K₂, we have one edge, and covering either endpoint gives ω_V(K₂) = 1. For K₃, we have to cover 2 vertices to get all 3 edges. We might reasonably guess than that ω_V(K_n) = n-1, and that a minimum vertex cover consists of all vertices except one. To prove this, observe first that if we cover all but one vertex, then every edge has a covered endpoint (since only one endpoint can be the missing vertex); this shows n-1 is sufficient. Second, if there are two uncovered vertices, then the edge between them is not covered: this shows n-1 is necessary.

2. Here we notice that if we leave any vertex on the left-hand side uncovered, we must cover every vertex on the right-hand side. Having done so, we've covered all edges. So a minimum cover either covers the entire left-hand side or the entire right-hand side, whichever is smaller: ω_V(K_mn) = min(m,n).

3. Recall that P_n has vertices v₀v₁...v_n. Each vertex is incident to at most 2 edges, so to cover the n edges we need to mark at least n/2 vertices, which means at least ⌈n/2⌉ vertices since we can't mark half a vertex. We can achieve exactly ⌈n/2⌉ by marking all the odd-numbered vertices. So ω_V(P_n) = ⌈n/2⌉.

4. Recall that we can describe each vertex of Q_n by a bit string of length n. Consider all the edges of the form (x0,x1), where x is any (n-1)-bit string. These have no endpoints in common, so we have to mark one endpoint for each one, giving ω_V(Q_n) ≥ 2^n-1. To show equality, consider the set S = { x | ∑ x_i is even }. Since every edge of Q_n changes exactly one bit value between its endpoints, one of its endpoints has an even number of ones. So S is a vertex cover of Q_n, and we have ω_V(Q_n) = n/2.