Massachusetts Institute of Technology Handout 14 6.042J/18.062J: Mathematics for Computer Science September 22, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 3

Due: Start of class on September 29, 1988.

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?

(b) Is R symmetric?

(c) Is R transitive?

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.

(b) Every reflexive, symmetric, weakly transitive relation is an equivalence relation.

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.

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 above, 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.

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

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.

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

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

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

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.

(b) Given the initial configuration of the toy indicated above, prove that Theory Pig can never spell his name.