[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. ℝ/ℚ

Recall that ℝ is the set of real numbers and ℚ is the set of rational numbers, those elements of ℝ that can be expressed as p/q where p is an integer and q is a nonzero natural number.

Define the relation ~ on ℝ by the rule x~y if and only if x-y ∈ ℚ.

  1. Show that ~ is an equivalence relation.
  2. Show that ~ is preserved by addition: that is, if x ~ x' and y ~ y', then x+x' ~ y+y'. Corrected 2008-11-17.

  3. Describe the equivalence class of 0 under ~.

1.1. Solution

  1. Reflexive: x-x = 0 ∈ ℚ. Symmetric: If x-y = p/q∈ℚ, then y-x = -(x-y) = -p/q ∈ ℚ. Transitive: Suppose x~y and y~z; then y-x ∈ ℚ and z-x ∈ ℚ. But since ℚ is closed under addition (p/q + p'/q' = (pq'+qp')/(qq')), we have z-x = (y-x)+(z-y) ∈ ℚ.
  2. Let x'-x = a and y'-y = b, where a,b∈ℚ. Then (x+y)-(x'+y') = (x-x')+(y-y') = a+b ∈ ℚ.
  3. A number r is in the equivalence class of 0 if and only if r~0, i.e. if r-0 = r ∈ ℚ. This means that r is in the equivalence class of 0 if and only if r is in ℚ, so the equivalence class of 0 is just ℚ itself.

2. Lattices

Let (L,≤) be a lattice, that is, a partially ordered set such that every pair of elements x and y have a greatest lower bound x∧y and a least upper bound x∨y.1

  1. Prove or disprove: Any minimal element of L is a minimum element.
  2. Prove or disprove: For all x, y, and z, (x∨y)∨z = x∨(y∨z).

2.1. Solution

1. Proof: Let x be a minimal element of L, i.e. an element such that there is no element y with y<x. Let z be any element of L, and consider q = x∧z. We have that q≤z and q≤x. But since it is not the case that q < x, we have q=x, implying x≤z. Since z was arbitrary, it follows that x≤z for all z∈L, i.e., that x is a minimum.

2. Proof: Let q = (x∨y)∨z and r = x∨(y∨z). We want to show that q = r; the easiest way to do this is to show that r ≥ q and q ≥ r.

First observe that r = x∨(y∨z) implies r ≥ x and r ≥ y∨z. Expanding the second inequality gives r ≥ y and r ≥ z. Because x∨y is a least upper bound and r is an upper bound on x and y, we have r ≥ x∨y. We also have r ≥ z, so we have r ≥ (x∨y)∨z = q.

Essentially the same argument shows q ≥ r; decompose q ≥ (x∨y)∨z to get q ≥ x, q ≥ y, and q ≥ z, then work backwards to get q ≥ x∨y and thus q ≥ (x∨y)∨z = r.

Since r ≥ q and q ≥ r, we have q=r by antisymmetry.

3. Bipartite graphs

For which values of n are each of the following graphs bipartite?

  1. The path Pn with n edges and n+1 vertices. Corrected 2008-11-19.

  2. The cycle Cn with n edges and n vertices, where n≥3. Clarification added 2008-11-19.

  3. The complete graph Kn with n vertices.

  4. The n-dimensional cube Qn.

3.1. Solution

Recall that a graph is bipartite if its vertices can be partitioned into disjoint sets L and R such that every edge is of the form uv where u∈L and v∈R.

  1. Pn is always bipartite. Number the vertices 0..n and let L be the set of even-numbered vertices and R the set of odd-numbered vertices. Then for each edge (x,x+1), exactly one of x and x+1 is even.

  2. Cn is bipartite if and only if n is even. For even n, number the vertices 0..n-1 and spit between even- and odd-numbered vertices as in Pn. Then every edge is either (x,x+1) (even to odd or vice-versa) or (n-1,0) (odd to even). For n odd, suppose that the graph is bipartite and consider any partition into L and R. Suppose that vertex 0 is in L; then vertex 1 is in R, and by induction we can easily show that every even-numbered vertex is in L and every odd-numbered vertex is in R. But then (n-1, 0) is an edge from an even-numbered vertex to an even-numbered vertex, contradicting the claim that Cn is bipartite.

  3. Kn is only bipartite for n≤2. Proof: In K1 there are no edges, so no edges go between two vertices in the same partition. In K2, there is one edge: put one endpoint in L and the other in R. For K3 and up, we have C3 as a subgraph; there is already no way to 2-color C3, so adding more vertices and edges won't help; it follows that Kn is not bipartite for n>2.

  4. Qn is always bipartite. Proof: Put x in L if ∑ xi is even, and in R otherwise. Given any edge xy, exactly one coordinate differs between x and y, so we have ∑ xi = 1 + ∑ yi or ∑ yi = 1 + ∑ xi. Exactly one of these quantities is even, so exactly one of the two endpoints is in L.

  1. See Relations or RosenBook pp. 574–576 for a formal definition of a lattice. (1)

2014-06-17 11:57