Due Friday, October 27 at 1:00 pm Pacific
Solutions are available!
This fourth problem set explores graph theory and the pigeonhole principle. It’s designed to take you on a tour of the beauty of finite structures and some of their amazing properties. Plus, you’ll get to see some pretty pictures and learn about why all this matters in the first place. 😃
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:
This problem set does not have a coding component.
Problem One: Disaster Planning
Suppose we have a transportation grid consisting of a collection of cities linked by highways. We want to place emergency supplies in those cities so that they're ready in the event of a natural disaster. Because stockpiling emergency supplies is so expensive, we (ideally) wouldn't put emergency supplies in every city. Instead, we'll stockpile supplies in a collection of cities such that each city either has supplies or is immediately down a highway from a city that does.
We can model this problem through the language of graph theory. Imagine we have a graph $G = (V, E)$ where each node represents a city and edges represent highways. We're looking for a set of nodes $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.\]A set $D$ with this property is called a dominating set.
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.
-
Give two different examples of dominating sets of the graph shown below, each of which has cardinality four or less. No justification is necessary.
As a refresher from lecture, a vertex cover of a graph $G = (V, E)$ is a set $C \subseteq V$ where the following is true:
\[\forall u \in V. \forall v \in V. (\Set{u, v} \in E \to (u \in C \lor v \in C))\text.\]Vertex covers are similar to dominating sets, but the two concepts are not quite the same.
-
Draw the smallest possible graph with the following property: the smallest dominating set of that graph is smaller than the smallest vertex cover of that graph. By "smallest possible graph," we mean "using as few nodes as possible, and of the graphs with that many nodes, using as few edges as possible." No justification is necessary.
-
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 $C$ is a vertex cover of $G$, then $C$ is a dominating set in $G$.
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?
Another refresher from lecture. If $G = (V, E)$ is a graph, an independent set of $G$ is a set $I \subseteq V$ with the following property:
\[\forall u \in I. \forall v \in I. \Set{u, v} \notin E\text.\]Now, a new definition. 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'$).
-
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.
-
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.
Let's return to our original motivation for this problem. We have a set of cities and we want to provide emergency supplies to those cities by ensuring that each city either has emergency supplies or is adjacent to a city with those supplies.
Now let's make this a bit more complex. Suppose that there are two different types of emergency supplies (say, supplies for dealing with fires and supplies for dealing with floods). Furthermore, let's say that no city is allowed to stockpile both types of supplies; each city either stores fire supplies, stores flood supplies, or stores nothing at all. As before, we want to ensure each city has access to both fire supplies and flood supplies, either by stockpiling the supplies in the city itself or by being down the highway from a city that stockpiles them.
Mathematically, we can model this as follows. We are given a graph $G = (V, E)$ and we want to find two different dominating sets $D_1$ and $D_2$ (each representing one type of supplies) where $D_1 \cap D_2 = \emptyset$ (no node belongs to both dominating sets). We can then think of $D_1$ as a dominating set for fire supplies and $D_2$ as being a dominating set for flood supplies.
-
Find two dominating sets $D_1$ and $D_2$ of the graph from part (i) such that $D_1 \cap D_2 = \emptyset\text.$ No justification is necessary.
You might be wondering - is it always possible to find two dominating sets with this property? It might seem like you'd need to put fire supplies in so many cities that the remaining cities couldn't be sufficient to supply flood supplies. But surprisingly, in almost all graphs, it's possible to find two disjoint dominating sets.
-
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 there exist dominating sets $D_1 \subseteq V$ and $D_2 \subseteq V$ such that $D_1 \cap D_2 = \emptyset\text.$
Dominating sets have applications far beyond planning for disasters - they make appearances in in complexity theory and error-correcting codes, too. 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.
-
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.
In lecture, when we proved the Theorem on Friends and Strangers, we started with a high-level "party trick" description of the problem, but then ended up proving a technical result about graphs and graph theory. You're welcome to reframe this problem in terms of graphs if it would make your proof easier.
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: Bipartite Graphs
The bipartite graphs are an important and common family of graphs. They appear in a huge number of settings – error-correcting codes, computational social choice theory, and algorithm design, to name a few.
Let’s begin with a formal definition. An undirected graph $G = (V, E)$ is called bipartite if there exist two sets $V_1$ and $V_2$ such that
- every node $v \in V$ belongs to at least one of $V_1$ and $V_2$;
- no node $v \in V$ belongs to both $V_1$ and $V_2$; and
- every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.
The sets $V_1$ and $V_2$ here are called bipartite classes of $G$.
-
Suppose you have an $8 \times 8$ chessboard. We form a graph from the board as follows: there's a node for each square on the board, and an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right).
Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.
Don’t do this in your head – draw lots of pictures!
Bipartite graphs have many interesting properties. One of the most fundamental is this one:
Theorem: An undirected graph $G$ is bipartite if and only if it contains no closed walks of odd length.
The forward direction of this implication has a nice intuition.
-
Explain, intuitively, why if $G$ is bipartite, then it has no closed walks of odd length. Specifically, give us a brief, informal explanation as to why every closed walk in $G$ has to have even length.
It might help to draw some pictures.
The reverse direction of this implication – that if $G$ has no closed walks of odd length, then $G$ is bipartite – requires a different sort of argument.
Let’s pick some arbitrary graph $G = (V, E)$ that has no closed walks of odd length. For simplicity’s sake, we’ll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as independent graphs. (Do you see why?)
Now, choose any node $x \in V$. Using node $x$ as an “anchor point,” we can define two sets $V_1$ and $V_2$ that we’ll need for the remainder of this argument:
\[V_1 = \Set{v \in V \suchthat \text{there is an odd-length walk from } x \text{ to } v }\] \[V_2 = \Set{v \in V \suchthat \text{there is an even-length walk from } x \text{ to } v }\]This turns out to be a really useful way to group the nodes of $G$.
-
Given the choices of $G$ and $x$ from above, prove that $V_1$ and $V_2$ have no nodes in common.
Remember that there might be multiple different walks of different lengths from $v$ to some other node $x$, so be careful not to talk about “the” walk between $v$ and $x$. Also note that these walks are not necessarily paths.
-
Using your result from part (iii), prove that $G$ is bipartite.
The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. So start off by writing down a list of what you need to prove, then address each part in turn.
Want to learn more about bipartite graphs and their applications? Take CS161 (algorithms), CS224W (deep learning on graphs), or CS250 (error-correcting codes)!
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{).}$