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. 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 P_n with n edges and n+1 vertices. Corrected 2008-11-19.

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

3. The complete graph K_n with n vertices.

4. The n-dimensional cube Q_n.

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. P_n 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. C_n 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 P_n. 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 C_n is bipartite.

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

4. Q_n 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.