# 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}.

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

- Monoid only. The function f(x) = 0x has no inverse.
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^{-1}ax = x gives an inverse function for each f_{a}in the set. We also have that f_{a}f_{b}(x) = abx = bax = f_{b}f_{a}(x) for all x, showing that f_{a}f_{b}= f_{b}f_{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.)- Monoid. It still contains f(x) = 0x.
We always get a group, because given y = f

_{ab}(x) = ax+b, solve for x as a^{-1}(y-b) = a^{-1}y + (-a^{-1}b); 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.

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

## 2.1. Solution

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 ℚ/ℤ.- 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:
- Every element y is of the form nx for some n∈ℤ, i.e. x generates G. In this case G is cyclic.
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.

- 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?

## 3.1. Solution

Consider any path v

_{0}v_{1}...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_{0}≡ v_{k}(mod n), so v_{0}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.G[n] is always acyclic. Suppose v

_{0}v_{1}...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_{0}. Suppose that v_{0}< v_{1}. Then v_{1}=v_{0}+n. We will now prove by induction that v_{i}=v_{0}+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_{0}< v_{1}, then v_{k}≠v_{0}and we don't have a cycle. But the case v_{0}> v_{1}is symmetric, so we don't get a cycle there either.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.

- 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:

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

## 4.1. Solution

The easiest way to find this is to start with some small cases: for K

_{1}there are no edges, so ω_{V}(K_{1}) = 0. For K_{2}, we have one edge, and covering either endpoint gives ω_{V}(K_{2}) = 1. For K_{3}, 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.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).Recall that P

_{n}has vertices v_{0}v_{1}...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⌉.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.