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

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

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

  2. The complete bipartite graph Knm.

  3. The path on with n edges Pn.

  4. The n-dimension cube Qn.

2014-06-17 11:57