Math 202C: Model Homework Solution

Lectures are informal by design: we meet to discuss algebra and chart our course through the subject. I talk to you, you talk to me. We generate ideas to craft a narrative. We then retire to our respective domiciles to polish that narrative. My job is to identify the key large scale ideas, treating these as girders which I assemble into an overarching structure presented in the lecture notes. I also identify important small-scale ideas which play the role of joists supporting the overarching structure. Your job is to install these joists, which you do in the homework problems. In order for this collaborative endeavor to succeed, there must be committed and earnest effort from both parties.

If I was a telepath, I would read your mind to determine if you are supplying this effort and base your grade on the results of this brain scan. Although I am not a telepath, I can gauge your earnestness to a certain extent based on verbal interactions. However, this measurement is imperfect and moreover I do not interact verbally with every student, though I am willing to do so. Therefore, your written solutions must communicate your commitment to the cause.

Below is an exemplar on which you can model your work in terms of level of detail and tone, should you wish to do so. My process was the following: I discussed the problem with two people for about fifteen minutes after lecture; I thought about it more on my fifteen minute drive home; I thought about it again while falling asleep, probably another fifteen minutes; I woke up and worked out the solution carefully, which took about an hour.

Problem 1.1. Find a formula for the number of walks of given length between two given vertices of the complete graph.

Solution: Let $K_n$ be the complete graph on $\{1,\dots,n\}$ . Given $i,j \in S$ and $r \in \mathbb{N},$ let $W^r(i,j)$ denote the number of $r$ -step walks $i \to j$ in $G.$ Observe that

$W^r(1,1) + W^r(1,2) + \dots + W^r(1,n)=(n-1)^r.$

Indeed, at the each step of the walk we have $n-1$ choices for the next vertex to visit. We claim that

$W^r(1,2)= \dots = W^r(1,n).$

Intuitively, this is because the complete graph is completely homogeneous. Let us translate this intuition into a precise argument.

Let $S_n=\mathrm{Aut}\{1,\dots,n\}$ be the symmetric group on $\{1,\dots,n\},$ and let $\tau = (2\ 3)$ be the transposition which transposes $2$ and $3.$ Let $\tau$ act on the set of walks $1 \to v_1 \to \dots \to v_{r-1} \to 2$ by

$\tau(1 \to v_1 \to \dots \to v_{r-1} \to 2) = \tau(1) \to \tau(v_1) \to \dots \tau(v_{r-1}) \to \tau(2).$

In words, $\tau$ acts on an input walk by replacing all occurrences of $2$ with $3$ , and vice versa. This is a bijective mapping from the set of $r$ -step walks $1 \to 2$ to the set of $r$ -step walks $1 \to 3$ , and in fact this bijection is an involution because $\tau$ is. Consequently, $W^r(1,2)=W^r(1,3).$ The same argument shows that $W^r(1,2)=W^r(1,4)$ , just use $\tau=(2\ 4)$ instead.

We now know that

$W^r(1,1) + (n-1)W^r(1,2) = (n-1)^r.$

If we can find a second linear equation satisfied by these numbers, we can solve the resulting system. We will find a second relation by haruspication, which in the present situation means looking at small values of $r.$