[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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 fa(x) = ax for all a in ℤm.

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

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

  4. The set of functions fab(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 fa in the set. We also have that fafb(x) = abx = bax = fbfa(x) for all x, showing that fafb = fbfa. (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 = fab(x) = ax+b, solve for x as a-1(y-b) = a-1y + (-a-1b); this gives an inverse for each fab. 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 gn 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 v0v1...vk in G[n]. We have vi+1 = vi±n, so in particular we have vi+1 ≡ vi (mod n). A simple induction then shows that v0 ≡ vk (mod n), so v0 is in the same connected component as vk 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 v0v1...vk 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 vk≠v0. Suppose that v0 < v1. Then v1=v0+n. We will now prove by induction that vi=v0+in. The base case of i=1 is already established. Now suppose that vi-2=(i-2)n and vi-1=(i-1)n. Now vi-1 has only two incident edges, and we've already used one of them, so vi must be reach through the other one: vi = vi-1+n = (i-1)n+n = in. So if v0 < v1, then vk≠v0 and we don't have a cycle. But the case v0 > v1 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 Kn.

  2. The complete bipartite graph Knm.

  3. The path on with n edges Pn.

  4. The n-dimension cube Qn.

4.1. Solution

  1. The easiest way to find this is to start with some small cases: for K1 there are no edges, so ωV(K1) = 0. For K2, we have one edge, and covering either endpoint gives ωV(K2) = 1. For K3, we have to cover 2 vertices to get all 3 edges. We might reasonably guess than that ωV(Kn) = 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(Kmn) = min(m,n).

  3. Recall that Pn has vertices v0v1...vn. 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(Pn) = ⌈n/2⌉.

  4. Recall that we can describe each vertex of Qn 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(Qn) ≥ 2n-1. To show equality, consider the set S = { x | ∑ xi is even }. Since every edge of Qn 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 Qn, and we have ωV(Qn) = n/2.

2014-06-17 11:57