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+y ~ x'+y'. Corrected 2008-11-17.

3. Describe the equivalence class of 0 under ~.

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

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

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

2014-06-17 11:57