Homework 8

CS 280 - Spring 2002

Due: Friday, April 19

Part A

1. Consider the set of strings using letters of the alphabet.  For each of the relations below, determine if the relation is reflexive, irreflexive (defined on page 382), symmetric, antisymmetric, and/or transitive.
   1. {(a, b) | a and b have no vowels in common}
   2. {(a, b) | a and b have different lengths}
   3. {(a, b) | a and b end with the same letter}
   4. {(a, b) | every letter in a also appears in b} [Don't worry about number of occurrences of each letter; in other words, the relation includes (xx, x).]
       
2. R = {(a, a), (a, b), (b, c), (c, b), (c, c), (c, d)} is a relation on A = {a, b, c, d}.
   1. What is the symmetric closure of R?
   2. What is the transitive closure of R?
   3. What is the symmetric, transitive closure of R?
   4. What is the reflexive, symmetric closure of R?

Part B

3. Consider the following Hasse diagram.

       a
      / \
     b   c
    / \ / \
   d   e   f
    \ / \ /
     g   h

   1. Which elements are maximal?  
   2. Which are minimal?
   3. Find the upper bounds of {d, e}.  Is there a least upper bound?  What is it?
   4. Find the lower bounds of {b, c}.  Is there a greatest lower bound?  What is it?
       
4. Consider the following Hasse diagram.  It's the same as the preceding diagram except that there is no node e; instead edges (from g to c and from h to b) cross at the position formerly occupied by e.

       a
      / \
     b   c
    / \ / \
   d       f
    \ / \ /
     g   h

   1. Find the lower bounds of {b, c}.  Is there a greatest lower bound?  What is it?
   2. Find the upper bounds of {g, h}.  Is there a least upper bound?  What is it?
   3. Find the lower bounds of {d, c}.  Is there a greatest lower bound?  What is it?
   4. Find the lower bounds of {a, b}.  Is there a greatest lower bound?  What is it?

Part C

5. Consider two relations R and S on some set A.  Define two new relations T and U on A.  
   T = {(a, b) | (a, b) in R and (a, b) in S}
   U = {(a, b) | (a, b) in R or (a, b) in S}
   1. Suppose R and S are equivalence relations.  Is T an equivalence relation?  Is U an equivalence relation? Provide a either a proof or a counterexample for each question.
   2. Suppose R and S are partial orders.  Is T a partial order?  Is U a partial order?  Provide either a proof or a counterexample for each question.
    
6. Suppose we build a simple graph on 10 vertices by flipping an unbiased coin to determine which edges are present.  In other words, each possible edge e appears with probability 1/2. 
   1. What is the expected number of edges for such a graph?
   2. What is the expected degree of a vertex in this graph?

This question is not part of the homework assignment, but it's interesting to think about: What is the probability that the resulting graph in problem 6 has a subgraph which is a triangle?