Massachusetts Institute of Technology Handout 23 6.042J/18.062J: Mathematics for Computer Science October 1, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 3 Solutions

Problem 1. (5 points) Let R be a binary relation on the set {a, b, c, d, e} defined as follows:

R = { (a, a), (a, b), (a, d), (b, a), (b, b), (b, c), (b, d),
(c, b), (c, c), (c, d), (d, b), (d, c), (d, d), (e, e) }

Answer yes or no to each of the following questions; if you answer no, then defend your answer.

(a) Is R reflexive?

Yes.

(b) Is R symmetric? No. R contains (a, d), but not (d, a).

(c) Is R transitive? No. R contains (d, b) and (b, a), but not (d, a).

Problem 2. (10 points) A relation R on a set A is weakly transitive if for all a, b, c, d ∈ A, the relations aRb, bRc, and cRd imply the relation aRd.

Prove or disprove the following statements.

(a) Every symmetric, weakly transitive relation is transitive. The claim is false. The diagram below shows a counterexample.

(b) Every reflexive, symmetric, weakly transitive relation is an equivalence relation. Proof. The relation R is an equivalence relation if it is reflexive, symmetric, and transitive. The first two properties hold by assumption; all that remains is to show that R is a transitive relation. Suppose that the relations aRb and bRc hold. Because R is reflexive, the relation aRa also holds. Because R is weakly transtive, the relations aRa, aRb, and bRc imply the relation aRc. Therefore, R is transitive.

Problem 3. (10 points) Let G_{n} be a directed graph with vertices numbered 0, 1, …, n−1. There is a directed edge from vertex i to vertex j if and only if j ≡ i^{2} + i + 1 (mod n). (See page 119 of Rosen for a definition of ≡ and (mod n). As a hint, however, no number theory is required to solve this problem.)

(a) Draw the directed graphs G_{1}, G_{2}, and G_{3}.

(b) Prove that if n ≥ 1, then G_{n} is not a directed acyclic graph.

Proof. Consider the following sequence of vertices in graph G_{n}.

v_{1} = 0
v_{2} = v_{1}^{2} + v_{1} + 1 (mod n)
v_{3} = v_{2}^{2} + v_{2} + 1 (mod n)
…  …
v_{n+1} = v_{n}^{2} + v_{n} + 1 (mod n)

Note that there is a directed edge from v_{i} to v_{i+1} for all 1 ≤ i ≤ n. Not all of the vertices v_{1}, …, v_{n+1} can be distinct, since the graph contains only n vertices. Suppose v_{j} is the first vertex in the sequence to appear a second time, and v_{k} was the initial appearance of that vertex. Than the sequence of vertices v_{k}, v_{k+1}, …, v_{j−1} forms a directed cycle. Therefore, G_{n} is not a directed acyclic graph.

Problem 4. (20 points) A linear extension of a poset is a total order consistent with the partial order. That is, if x > y in the partial order, then x > y in the total order also. For example, in the poset defined by the Hasse diagram below, the following relationships hold: a > b, a > c, a > d, a > e, b > c, and b > d.

This poset has eight linear extensions, which are listed in the table below. To clarify the notation, the upper-left entry represents the total order where a is the largest element, b the second largest, and so forth. Note that all of the relationships that hold in the poset also hold for all the total orders listed below.

\begin{matrix}a > b > c > d > e & a > b > d > c > e \\ a > b > c > e > d & a > b > d > e > c \\ a > b > e > c > d & a > b > e > d > c \\ a > e > b > c > d & a > e > b > d > c \end{matrix}

(a) List all the linear extensions of the poset represented by the Hasse diagram below.

a > b > c > e > d  a > c > b > e > d
a > b > c > d > e  a > c > b > d > e
a > b > d > c > e

(b) After considering the above examples, Theory Pig formulated the following claim.

Claim. The number of linear extensions of a partially ordered set with n elements always divides n!.

Either prove that his claim is correct for all posets or else draw the Hasse diagram of a counterexample and list all linear extensions.

The claim is false. The 4-element poset depicted below has 5 linear extensions. This is a counterexample, because 5 does not divide 4!.

a > b > c > d  a > b > d > c
b > a > c > d  b > a > d > c
b > d > a > c

Problem 5. (15 points) An automorphism of a graph is a relabeling of the vertices that preserves adjacency. For example, the graph on the left side of the figure below has the automorphism a → b, b → a, c → c, d → d. (Here the notation x → y means that the vertex labeled x is relabeled y.) The relabeled graph is shown on the right side of the figure. This relabeling is an automorphism because adjacency is preserved; that is, in the relabeled graph, just as in the original, a is adjacent to b and c; b is adjacent to a and c; c is adjacent to a, b, and d; and d is adjacent to c. Every graph has a trivial automorphism that assigns each node its original label.

(a) List all non-trivial automorphisms of the graph below using the x → y notation as in the example.

a → e, b → f, c → c, d → d, e → a, f → b, g → g, h → h
a → e, b → f, c → c, d → d, e → a, f → b, g → h, h → g
a → a, b → b, c → c, d → d, e → e, f → f, g → h, h → g

(b) Draw a graph with at least 2 nodes that has only the trivial automorphism.

Problem 6. (15 points) An n-node graph is said to be tangled if there is an edge leaving every set of ⌈\frac{n}{3}⌉ or fewer vertices. As a special case, the graph consisting of a single node is considered tangled. (Recall that the notation ⌈x⌉ refers to the smallest integer greater than or equal to x.)

(a) Find the error in the proof of the following claim.

Claim. Every non-empty, tangled graph is connected.

Proof. The proof is by strong induction on the number of vertices in the graph. Let P (n) be the propostion that if an n-node graph is tangled, then it is connected. In the base case, P (1) is true because the graph consisting of a single node is defined to be tangled and is trivially connected.

In the inductive step, for n ≥ 1 assume P (1), …, P (n) to prove P (n + 1). That is, we want to prove that if an (n + 1)-node graph is tangled, then it is connected. Let G be a tangled, (n + 1)-node graph. Arbitrarily partition G into two pieces so that the first piece contains exactly ⌈\frac{n}{3}⌉ vertices, and the second piece contains all remaining vertices. Note that since n ≥ 1, the graph G has a least two vertices, and so both pieces contain at least one vertex. By induction, each of these two pieces is connected. Since the graph G is tangled, there is an edge leaving the first piece, joining it to the second piece. Therefore, the entire graph is connected. This shows that P (1), …, P (n) imply P (n + 1), and the claim is proved by strong induction.

The error is in the statement, “By induction, each of these two pieces is connected.” This is not what the induction hypothesis says; the induction hypothesis states that if a graph is tangled, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form “if (this), then (that)”. However, we erroneously use the induction hypothesis as if it were simply of the form “(that)’.

(b) Draw a tangled graph that is not connected.

(c) An n-node graph is said to be mangled if there is an edge leaving every set of ⌈\frac{n}{2}⌉ or fewer vertices. Again, as a special case, the graph consisting of a single node is considered mangled. Prove the following claim.

Claim. Every non-empty, mangled graph is connected. Proof. The proof is by contradiction. Assume for the purpose of contradiction that these exists an n-node graph that is mangled, but not connected. Then the graph must have at least two connected components. However, there can be at most one connected component with more than ⌈\frac{n}{2}⌉ vertices, since the graph has only n vertices in total. Therefore, there exists a connected component with ⌈\frac{n}{2}⌉ or fewer vertices. Since the graph is mangled, there is an edge leaving this component. But this contradicts the definition of a connected component.

Problem 7. (15 points) Let G and H be undirected graphs with no self-loops. The product graph P = G × H is defined as follows. The vertex set of P is the cartesian product of the vertex set of G and the vertex set of H. Thus, each vertex of P is an ordered pair (v, w) where v is a vertex of G and w is a vertex of H. The edges in the product graph P are of two types. First, for every edge (v_{1}, v_{2}) in G and vertex w in H, there is an edge between (v_{1}, w) and (v_{2}, w) in P. Second, for every vertex v in G and edge (w_{1}, w_{2}) in H, there is an edge between (v, w_{1}) and (v, w_{2}) in P. Note that these two sets of edges are disjoint.

(a) Draw the product of the two graphs shown below. Your diagram must be tidy to receive full credit. In particular, label all the vertices, e.g. (b, 3), and use two different colors or line styles (e.g. dashed and solid) to distinguish the two types of edge defined above.

(b) Let G be the graph consisting of two vertices connected by an edge. Let G^{n} be the product of n copies of G. Use induction to prove that G^{n} has 2^{n} vertices and n2^{n−1} edges. (You may assume without proof that the × operation is associative.)

Proof. The proof is by induction on n. Let P (n) be the proposition that G^{n} has 2^{n} vertices and n2^{n−1} edges. In the base case, P (1) is true because G^{1} has 2^{1} = 2 vertices and 1 · 2^{1−1} = 1 edge.

In the inductive step, for n ≥ 1 assume that G^{n} has 2^{n} vertices and n2^{n−1} edges to prove that G^{n+1} has 2^{n+1} vertices and (n + 1)2^{n} edges. The remainder of the argument uses the fact that G^{n+1} = G^{n} × G.

The vertex set of G^{n+1} is the cartesian product of the vertex set of G^{n} and the vertex set of G. There are 2^{n} vertices in G^{n} by induction, and there are 2 vertices in G by the definition of the graph. Therefore, there are 2^{n} · 2 = 2^{n+1} vertices in G^{n+1}.

The edges of G^{n} × G are of two types. First, for each edge (v_{1}, v_{2}) in G^{n} and vertex w in G, there is an edge between (v_{1}, w) and (v_{2}, w) in G^{n+1}. Thus, the number of edges of the first type is equal to the number of edges in G^{n} multiplied by the number of vertices in G, which gives n2^{n−1} · 2 = n2^{n}.

Second, for each vertex v in G^{n} and edge (w_{1}, w_{2}) in G, there is an edge between (v, w_{1}) and (v, w_{2}) in G^{n+1}. Thus, the number of edges of the second type is equal to the number of vertices in G^{n} multiplied by the number of edges in G, which gives 2^{n} · 1 = 2^{n}. Since these two sets of edges are disjoint, the total number of edges in G^{n+1} is equal to n2^{n} + 2^{n} = (n + 1)2^{n}.

This shows that P (n) implies P (n + 1), and the claim is proved by induction.

Problem 8. (10 points) John Dunagan, one of the 6.042 TAs, gave our friend Theory Pig a new toy for his birthday. The toy consists of a 3 × 3 grid of squares, where each square contains one of the letters in THEORY PIG. Each row can be rotated right or left and each column can be rotated up or down. The effects of such rotations are explained in the figure below.

\begin{matrix}H & E & Y \\ P & I & G \\ R & O & T \end{matrix} → \begin{matrix}R & E & Y \\ H & I & G \\ P & O & T \end{matrix} → \begin{matrix}R & E & Y \\ I & G & H \\ P & O & T \end{matrix}

The first picture shows Theory Pig’s new toy configured as he first received it. The leftmost column is then rotated downward to give the middle picture. The H and P move down, and the R rotates back up to the top. Then the middle row is rotated leftward to produce the final picture. The I and G move left, and the H rotates back around to the right.

Naturally, Theory Pig wants to arrange the letters so as to spell his name.

\begin{matrix}T & H & E \\ O & R & Y \\ P & I & G \end{matrix}

Based on prior experience, Theory Pig is afraid that the toy might be specially designed to make this delightful combination utterly impossible, no matter what sequence of row and column rotations he attempts.

(a) Model Theory Pig’s toy as a state machine.

• The set of states Q consists of all arrangements of the letters in THEORY PIG on a 3 × 3 grid.

• The set of start states Q_{0} consists of the single arrangement HEY PIG, ROT!

• The set δ ⊆ Q × Q consists of all pairs of states (q_{1}, q_{2}) such that q_{2} can be obtained from q_{1} by a row or column rotation.

(b) Given the initial configuration of the toy indicated above, prove that Theory Pig can never spell his name. The idea is to keep track of the number of letter pairs that are out of order relative to T HEORY P IG. For example, in the initial configuration, H appears before T; this pair of letters is out of order, because T appears before H in T HEORY P IG. We will refer to an out-of-order letter pair as an inversion. In the initial configuration, there are 17 inversions:

HT ET Y T Y O Y T
P R P O P T IR IO
IT GR GO GT RO
RT OT

The key observation is that a rotation always changes the number of inversions by an even amount. Since the puzzle initially has an odd number of inversions, no sequence of rotations can reduce the number of inversions to 0, an even number. Consequently, there will always be at least one pair of letters out of order, and Theory Pig can never spell out his name. The main challenge is to prove that a rotation always changes the number of inversions by an even amount. We will prove this claim in a sequence of lemmas, and then we will prove the main result as a theorem.

Lemma 0.1 Swapping an adjacent pair of letters changes the number of inversions by an odd amount.

Proof. If the letters were initially in the same order as in T HEORY P IG, then the number of inversions is increased by 1, an odd number. Otherwise, the letters were initially in the wrong order, and the number of inversions is decreased by 1, also an odd number.

Lemma 0.2 Swapping any pair of letters changes the number of inversions by an odd amount.

Proof. We will show how to swap of any pair of letters using an odd number of swaps of adjacent letters. The preceding lemma says that swapping adjacent letters changes the number of inversions by an odd amount. Therefore, swapping any pair of letters changes the number of inversions by an odd amount, because the sum of an odd number of odd numbers is odd.

All that remains is to show how to swap any pair of letters using an odd number of swaps of adjacent letters. Suppose that we are swapping letters x and y, where x is on the left, y is on the right, and there are k stray letters between the two. First, we swap x with its right neighbor k times. This leaves x directly left of y and leaves all the stray letters shifted one place to the left. Then we swap x and y, putting x into y’s original positions. Finally, we swap y with its left neighbor k times. This puts y into x’s original position and shifts the stray letters back to their original position. The total number of swaps of adjacent letters is k + 1 + k = 2k + 1, which is odd for all k ≥ 0.

Lemma 0.3 Rotating any row or column changes the number of inversions by an even amount.

Proof. We show below that any row or column rotation can be obtained by two swaps. The preceding lemma says that every swap changes the number of inversions by an even amount. Since the sum of two odd numbers is even, any row or column rotation changes the number of inversions by an even amount.

Here is how to obtain a rotation from two swaps. Suppose that the letter sequence xyz appears in some row or column. Swapping x with y and then swapping x with z creates the sequence yzx, which corresponds to a leftward or upward rotation. Swapping z with y and then z with x creates the sequence zxy. This corresponds to a rightward or downward rotation.

Theorem 0.4 Theory Pig can never spell his name.

Proof. The proof uses the Invariant Theorem. We prove the following invariant: the number of inversions in the letter sequence relative to T HEORY P IG is always odd.

The invariant holds in the single start state, because the number of inversions is initially 17, which is odd. Furthermore, the invariant is maintained under every transition. The preceding lemma states that every row or column rotation changes the number of inversions by an odd amount. Therefore, if the number of inversions was odd before a transition, then the number of inversions must be odd after a transition. Thus the invariant is established by the Invariant Theorem.

Since the number of inversions relative to T HEORY P IG is always odd, the string can never be formed.