Problem Set 4

Due Friday, May 5 at 2:30 pm Pacific

Solutions are available!

🔑 Solutions


As promised, due to it being the week of our midterm, this problem set is extra short–just 3 problems! And they're all about graphs and Pigeonhole Principle, which is an especially fun space to work in.

As a reminder, the Proofwriting Checklist says no first-order logic symbols (i.e., $\exists, \forall, \lor, \land, \leftrightarrow, \to, \lnot$) in your proofs!

Good luck, and have fun!

$\LaTeX$ Template

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS4 $\LaTeX$ Template

This problem set does not have a coding component.

Problem One: Independent and Dominating Sets

As a refresher from lecture, an independent set in a graph $G = (V, E)$ is a set $I \subseteq V$ with the following property:

\[\forall u \in I. \forall v \in I. \Set{u, v} \not\in E \text.\]

Now, a new definition. A dominating set in $G$ is a set $D \subseteq V$ with the following property:

\[\forall v \in V. (v \not\in D \to \exists u \in D. \Set{u, v} \in E)\text.\]

In general, whenever you find a new definition or new mathematical term, it’s good to play around with the definition a bit to get a feel for what it looks like.

  1. Give two different examples of dominating sets of the graph shown below, each of which has cardinality four or less. No justification is necessary.

    A graph with eight nodes: a, b, c, d, e, f, g, and h. Node a is adjacent to nodes b and e. Node b is adjacent to nodes a, c, e, and f. Node c is adjacent to nodes b, d, and g. Node d is adjacent to node c. Node e is adjacent to nodes a and b. Node f is adjacent to nodes b and g. Node g is adjacent to nodes c, f, and h. Node h is adjacent to node f.

  1. Let $G = (V, E)$ be an arbitrary graph with the following property: every node in $G$ is adjacent to at least one other node in $G$. Prove that if $I$ is an independent set in $G$, then $V - I$ is a dominating set in $G$.

    Notice that we're asking you to show that $V - I$ is a dominating set, not that $I$ is a dominating set. Also, we recommend drawing some pictures here to get a sense of how this works.

    Use the formal definitions to guide your proofs. If you proceed via a direct proof or via contrapositive, what, exactly, will you be assuming, and what will you be proving? If you write this as a proof by contradiction, what specifically is it that you’re assuming for the sake of contradiction?

An independent set $I$ in a graph $G$ is a maximal independent set in $G$ if there is no independent set $I'$ in $G$ where $I \subsetneq I'$. (Here, $I \subsetneq I'$ denotes that $I$ is a strict subset of $I'$, meaning that $I \subseteq I'$ and $I \ne I'$).

  1. Find independent sets $I$ and $J$ of the graph from part (i) of this problem such that $I$ is maximal but $\abs{I} \lt \abs{J}$. No justification is necessary.

    Yes, this is possible. The definition of a maximal independent set is meant to be taken literally.

  1. Prove that if $I$ is a maximal independent set in $G = (V, E)$, then $I$ is a dominating set of $G\text.$

    You can build a great intuition for this result by drawing some pictures and thinking about what has to happen for a set of nodes to be an independent set and for a set of nodes to be a dominating set. When it comes time to write out your proof, however, you’ll need to use the formal first-order definitions of independent sets, maximal independent sets, and dominating sets.

Independent and dominating sets have applications in complexity theory, error-correcting codes, and resource allocation. Take CS154 and CS250 to learn more!

Problem Two: Friends, Strangers, Enemies, and Hats

In lecture, we proved the Theorem on Friends and Strangers, which says that if you have a group of six people where, for each pair of people, those people either know one another (they’re friends) or they don’t know each other (they’re strangers), you can always find three mutual friends or three mutual strangers. Here, “three mutual friends” means “three people where each two of them are friends,” and “three mutual strangers” means “three people where each two of them are strangers.”

This is one of many different results about what must happen when you get a sufficiently large number of people together. The rest of this problem explores some other results in that vein.

  1. There’s a party with 36 attendees. Each person is wearing a hat, and there are seven possible hat colors: aureolin, bole, chartreuse, drab, ecru, fulvous, and gamboge. (Yes, those are all colors.) As in the Theorem on Friends and Strangers, for any pair of people at the party, either the pair are friends or the pair are strangers.

    Prove that you can always find three mutual friends all wearing the same color hat or three mutual strangers all wearing the same color hat.

    In the course of solving this problem, you will likely need to make sure of the Theorem on Friends and Strangers from lecture. If you do, you should just cite the result from lecture rather than reproving it from scratch. For example, you could say something like "by the Theorem on Friends and Strangers, we know that 
 ." As usual, though, don't repeat the theorem in the abstract. Instead, apply it to some specific scenario to state some new fact you learn as a result.

  1. There’s a party with 17 attendees. This time, things are a bit more complicated. For each pair of people at the party, either those people are strangers, those people are friends, or those people are enemies. Fortunately, none of them are wearing hats. 😃

    Prove that you can always find three mutual friends, or three mutual strangers, or three mutual enemies.

Find problems like these interesting? Take Math 107 (Graph Theory) or Math 108 (Combinatorics)!

Problem Three: Iterated Injections

Let $f : A \to A$ be an injection from a finite set $A$ to itself. (A finite set is one whose size is a natural number.) Your goal in this problem is to prove the following result:

Theorem: For each $a \in A$, there is an $n \in \naturals$ where $f^{n+1}(a) = a$.

In other words, if you take any element $a \in A$ and repeatedly apply $f$ to $a$, you will eventually get back what you started with.

Here’s how we’re going to prove this. Pick any $a \in A$, and let $k = \abs{A}$. Now, look at the sequence

\[f^0(a), f^1(a), f^2(a), f^3(a), \dots, f^k(a)\text.\]

This is what you get if you start at $a$ and keep applying $f$ over and over again.

  1. Prove that this sequence must contain at least one duplicate value.

Now, take the sequence above and consider the largest value of $n$ such that the sequence

\[f^0(a), f^1(a), \dots, f^n(a)\]

contains no repeated values. Since this is the longest such sequence, we know that the next term in the sequence, $f^{n+1}(a)$, must be equal to some term of the sequence shown above.

  1. Using your result from part (i), prove that $f^{n+1}(a) = a$. (This proves the above theorem.)

This theorem has a bunch of surprising applications.

  1. Let $f : A \to A$ be an injection from a finite set to itself. Using your result from part (ii), prove that $f$ is also a bijection.

One consequence of your result from part (iii) is that if an injective function from a set $A$ to itself is not a bijection, then $A$ must not be finite. And indeed, this is one possible way to define what it means for a set to be infinite!

Optional Fun Problem: Forced Triangles

Let $G = (V, E)$ be a graph where each node has been given one of three different colors (ecru, puce, and zomp - and yes, those are all colors) such that no two nodes of the same color are adjacent to one another. Furthermore, suppose there are exactly $n$ nodes of each color.

Prove that if every node $v \in V$ has degree at least $n+1\text,$ then $G$ contains a triangle (a copy of $K_3\text{).}$