Problem 1: Iso, You So
An important problem in graph theory is graph isomorphism. An isomorphism in mathematics is a structure-preserving invertible mapping between two objects. It describes how one object can be transformed into another and vice versa. Isomorphism corresponds closely (but is not equivalent!) to our traditional notion of equality. Equal objects are identical objects; isomorphic objects are mutually convertible objects.
Consider the formal definition of graph isomorphism:
Definition (Graph Isomorphism): an isomorphism between graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) is a bijection \(h : V_1 \rightarrow V_2\) with the additional property that for any edge \((x, y) \in E_1\) that \(h(x), h(y) \in E_2\). We say that \(G_1\) and \(G_2\) are isomorphic if there exists an isomorphism between them.
Because of this additional property, we colloquially call a graph isomorphism an edge-preserving mapping between \(G_1\) and \(G_2\).
First, let’s explore this definition. Give a small, artificial example of two graphs and an isomorphism between them.
Next, give a real-world example of two graphs and an isomorphism between them. Choose such an example where the notion of isomorphism might be useful to know. In a sentence, justify your choice of example.
For the remainder of this problem, you will prove properties of graphs involving isomorphisms. Before doing so, let’s make sure we understand the definition of graph isomorphism from a proof context. Suppose that we have graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\). In a few sentences, answer the following:
- Suppose we are trying to prove that \(G_1\) and \(G_2\) are isomorphic. What must we construct in order to prove this fact?
- Suppose we assume that \(G_1\) and \(G_2\) are isomorphic. What do we know exists because of this assumption?
First, let’s crystallize the notion of isomorphism as “closely corresponding” to equality. Define the binary relation \(\mathsf{ISO}(G_1, G_2)\) to mean that \(G_1\) and \(G_2\) are isomorphic. Prove the following claim about \(\mathsf{ISO}\):
Claim: \(\mathsf{ISO}\) is an equivalence relation.
Now, let’s talk about finding isomorphisms in a restricted case: trees. Let \(T_1\) and \(T_2\) be trees. Consider the following recursive definition of an algorithm for determining whether \(T_1\) and \(T_2\) are isomorphic:
If \(T_1\) and \(T_2\) are both empty, then they are (trivially) isomorphic.
If \(T_1\) and \(T_2\) are both non-empty, then they are isomorphic if either:
- Their left children are recursively isomorphic and their right children are recursively isomorphic, or
- The left child of \(T_1\) is isomorphic with the right child of \(T_2\) and the right child of \(T_1\) is isomorphic with the left child of \(T_2\).
If one of \(T_1\) and \(T_2\) is empty and the other is non-empty, then they are not isomorphic.
Call this recursive algorithm \(\mathsf{isIso}\).
Give a small artificial examples of a tree where \(\mathsf{isIso}\) reports that the tree is isomorphic as well as a small, artificial example of a tree where \(\mathsf{isIso}\) reports that the tree is not isomorphic. (Hint: try to pick examples that will test your knowledge of how the algorithm works. This mini-exercise is to prepare you for the next proof!)
Prove the following fact about \(\mathsf{isIso}\):
Claim (\(\mathsf{isIso}\) Soundness): For any trees \(T_1\) and \(T_2\), if \(\mathsf{isIso}(T_1, T_2)\) reports true, then \(T_1\) and \(T_2\) are isomorphic.
To prove this claim, use mutual induction on the structure of \(T_1\) and \(T_2\). In mutual induction, we construct both trees simultaneously. Consequently, our induction hypothesis applies whenever we are considering any of the children of both input trees.
(N.B., we leave as an exercise to the reader the related proof of completeness of the algorithm, i.e., if the trees are isomorphic, then the algorithm reports true.)
Finally, let’s consider finding isomorphisms over general graphs, not just trees. In a few sentences, explain why we cannot simply apply this tree isomorphism algorithm to a general graph?
(Hint: play with example graphs of a variety of shapes and size and observe where the tree isomorphic algorithm breaks down in the general case.)
Problem 2: Sportsball
Consider the problem of filling basketball teams. A single basketball team must have five people. Give combinatorial descriptions for each of the required values.
Basketball teams have five basic positions—center, power forward, small forward, shooting guard, and point guard. If there are \(s\) students to choose from, how many ways can I fill a single basketball team where each student is assigned to one of these positions?
In a pickup game of basketball, the teams typically don’t make a distinction between positions. In this context (where players are simply “on” a team without being assigned a position), how many ways are there to fill a team when there are \(s\) students to choose from?
Now suppose you are a high school P.E. coach and you are filling a team of mixed grades. Such a team has at least 1 player that is in each of 9th, 10th, 11th, and 12th grades. The last slot may be drawn from any of these players. Let the number of students from each grade be:
- 9th graders: \(a\)
- 10th graders: \(b\)
- 11th graders: \(c\)
- 12th graders: \(d\)
How many ways are there to fill a single team?
At the college level, we only differentiate between three positions—center, forward, and guard. A team is normally composed of a center, two forwards, and two guards. Suppose there are \(s\) students to choose from. How many ways can we fill a single team where each student is assigned to one of these positions? (Hint: You want to rule out repetition where, e.g., student \(s_1\) is first chosen to be a guard, then \(s_2\) and the case where \(s_2\) is first chosen, then \(s_1\).)
Suppose you are filling teams based on a rating system where:
- There are \(x\) 2 point players.
- There are \(y\) 3 point players.
- There are \(z\) 5 point players.
As a coach you may spend at most 15 points on forming a team of 5 players (but you may choose to spend less). How many different teams can you form in this system?
(Hint: Systematically explore all the possible valid point combinations, determine how many teams you can form from each, and then combine everything together. Make sure you give an unsimplified formula for this problem so your derivation is clear.)
Finally, suppose the pool of players consist of
- \(v\) point guards,
- \(w\) shooting guards,
- \(x\) small forwards,
- \(y\) power forwards, and
- \(z\) centers.
In a sentence or two, give a description of the quantity described by the following combinatorial description. Be explicit in your description when ordering matters.
\[ \binom{v}{1} \cdot \binom{x}{2} \cdot \binom{y}{1} \cdot \binom{z}{1}. \]
Problem 3: Relationship Counting
Consider the problem of counting binary relations over a domain of set \(S\) and range of set \(T\).
How many many possible functions can we form with domain \(S\) and range \(T\)? Justify your combinatorial description using a few sentences explaining how you constructed your formula.
How many possible injective functions can we form with domain \(S\) and range \(T\)? Justify your combinatorial description using a few sentences explaining how you constructed your formula.
Under what conditions (i.e., constraints on the sizes of \(S\) and \(T\)) can we not form any injective functions between these sets? Prove this claim using the principles of counting.
Similarly, under what conditions (i.e., constraints on the sizes of \(S\) and \(T\)) can we not form any surjective functions between these sets? Prove this claim using the principles of counting.