MUN Computer Science 1002 - Lab 5

Binary relations

 

Warm-up

To get into thinking about binary relations, first solve the following exercises. You can do it before the lab, or at the beginning of the lab in breakout rooms, as you prefer. Try to do them quickly; preferably, have different people in your room figure out different subquestions and then explain to the rest.

There is no template for this lab, but if you prefer Google Drawings over Bongo whiteboard, you are welcome to start an empty one and share it within the breakout room (on Google Drawings, use circles (copy/paste) to draw vertices of the graphs, and arrows and connectors to draw edges).

  1. For each of the following binary relations on A ={0,1,2,3}, draw a graph of the relation and state if it is reflexive, anti-reflexive, neither, symmetric, anti-symmetric, neither, transitive, order (total or partial) or equivalence.
    1. $R = \{(x,y) \in A \times A \mid x-1 \leq y \}$
    2. $R = \{(x,y) \in A \times A \mid x+y \equiv 2 \mod 4 \}$
    3. $R = \{ (x,y) \in A \times A \mid |x-y|=1 \}$

Main activity

Suppose you have a very important message to share with a group of people. You want to convince them all, but you don't have that much time. Instead, you would like to convince a few select influencers, who would then pass the message to their followers, who would in turn spread it, so that at the end everybody in the group gets it.

To help you figure it out, you turn to Twitter, and build a relation FOLLOW = {x,y ∈ GROUP | y follows x}, where GROUP is people you want to hear your message. Now, make an assumption that if a pair (x,y) is in the relation FOLLOW, then if you can convince x, x will convince y.

To be more concrete, suppose that GROUP = {Amka, Barak, Cora, Deepak, Emily, Fatemeh, Galina, Hamza, Iku, Josh}, and the FOLLOWS relation is {(Amka, Josh),(Cora, Amka), (Deepak, Emily), (Fatemeh, Hamza), (Galina, Josh), (Iku, Deepak), (Iku, Emily),(Josh, Barak)}. The rest of the question will refer to this GROUP and FOLLOWS relations.

  1. Draw a graph of the FOLLOWS relation above. Is it reflexive, anti-reflexive, symmetric, anti-symmetric, transitive, order, equivalence?
  2. Now, you would like to find out who can influence whom (potentially indirectly, through intermediate people). For that, compute a transitive reflexive closure of the FOLLOWS relation. Let's call the resulting relation INFLUENCE.
  3. Draw the graph of INFLUENCE relation.
  4. That graph had a lot of edges! But you might have noticed something: that there was never the case that two different people influenced each other. So you conclude that INFLUENCE must be an order relation.
  5. Now, draw a Hasse diagram of INFLUENCE.
  6. You can finally achieve your goal: finding the people you need to convince of your message so that they spread it to everybody in the group. For that, look at the Hasse diagram of the INFLUENCE relation. How can you tell which people you need to convince? Give the list of names, and explain how you chose them.
  7. Let's do one more thing with the INFLUENCE relation. By looking at it (or even at the original FOLLOWS) relation, you might have noticed that people seem to form "echo chambers", where some people have no connection to others, neither way, direct or indirect. Let's see what echo chambers are there in the GROUP.

    For that, compute a symmetric transitive closure of the INFLUENCE relation (this is the same as computing reflexive symmetric transitive closure of the FOLLOWS relation). First compute a symmetric closure of INFLUENCE; are there edges you need to add to make it transitive? If so, which ones?

  8. Your resulting relation, let's call it CONNECTIONS, should be an equivalence relation (since it is symmetric, reflexive and transitive), and so it partitions GROUP into equivalence classes (which are the "echo chambers" that you suspected to exist in the GROUP).

    State how many equivalences classes are in the GROUP with respect to CONNECTIONS, and for each class, list people who belong to it.