Act I in one table, three ways a matrix counted, and the bridge to power series. Then the final project, in detail.
Two pauses. When the stamp says Pause the video, do: each one takes about five minutes with paper, and the slide after it has the answers.
Logistics. Problem Set 3 is due Friday at 10 p.m. Friday's reading is Flajolet–Sedgewick §I.1, pages 16–24 of the free PDF.
I said that on the first day and have not said it since. Today we check it against the record: six results, and for each one, two questions.
What was the linear map?
What number did we compute about it?
| question | linear map | what we computed | answer |
|---|---|---|---|
| closed walks in $G$Chapter 1 | $A$, acting on $\mathbb R^V$ | the spectrum; $\operatorname{tr}A^\ell$ | $\sum_i\lambda_i^\ell$; from one vertex of $K_p$: $\tfrac1p\big((p-1)^\ell+(p-1)(-1)^\ell\big)$ |
| walks on the cube $Q_n$Chapter 2 | $A(Q_n)$ on $\mathbb R^{B_n}$, diagonalized by characters | the spectrum | eigenvalue $n-2i$ with multiplicity $\binom ni$ |
| a random walk returning homeChapter 3 | the transition matrix $\tfrac1dA$ | its powers, via the spectrum | $\tfrac1p\sum_i(\lambda_i/d)^\ell$ for vertex-transitive $G$ |
| largest antichain in $B_n$Chapter 4 | $U_i\colon\mathbb R(B_n)_i\to\mathbb R(B_n)_{i+1}$ | a rank: $U_i$ is one-to-one for $i<n/2$ | $\binom n{\lfloor n/2\rfloor}$; Sperner and rank-unimodal |
| largest antichain in $B_n/G$Chapter 5 | $\widehat U_i$: $U_i$ on $G$-invariant vectors | the same rank, inherited | the middle level; graphs on $m$ vertices by edge count are unimodal |
| spanning trees of $G$Chapter 9 | $M_0$, and $L_0=M_0M_0^{\mathsf T}$ | a determinant: a sum of squared minors | $\kappa(G)=\det L_0=\tfrac1p\mu_1\cdots\mu_{p-1}$; $\kappa(K_p)=p^{p-2}$ |
$$D_{i+1}U_i-U_{i-1}D_i=(n-2i)\,I$$
Since $D_i=U_{i-1}^{\mathsf T}$, the operator $U_{i-1}D_i$ is positive semidefinite, so every eigenvalue of $D_{i+1}U_i$ is at least $n-2i>0$. So $D_{i+1}U_i$ is invertible, so $U_i$ is one-to-one.
We proved the eigenvalues were positive. We never learned what they were.
The vertical maps are one-to-one (orbit sums are independent) and the square commutes, so $\widehat U_i$ is the restriction of a one-to-one map. That is the whole proof, and it is why the theorem stops at quotients of $B_n$.
The $(v,v)$ entry of $A^\ell$ counts closed walks of length $\ell$ at $v$. That is a fact about matrix multiplication, and it is where all of the combinatorics lives.
The spectral theorem makes the sum of those entries computable: $\operatorname{tr}A^\ell=\sum_i\lambda_i^\ell$.
$K_3$ has eigenvalues $2,-1,-1$, so $\operatorname{tr}A^4=16+1+1=18$, and by symmetry each vertex has $18/3=6$ closed walks of length 4. At right: all six from vertex 1.
$U_i$ sends a set to the sum of the sets that cover it. It is order-raising by construction: that is the combinatorics.
Linear algebra supplies exactly one thing: $U_i$ is one-to-one for $i<n/2$.
One-to-one and order-raising give an order-matching (Lemma 4.5). Matchings glue into symmetric chains, and symmetric chains give Sperner and unimodality.
The rank says a matching exists. It never says which one. The blue chains at right were found by hand.
(1) Lemma 9.6 (2) Cauchy–Binet (3) transpose (4) Lemma 9.7: each term is $1$ for a spanning tree, $0$ otherwise
$K_3$, oriented $1\to2\to3\to1$, with the row of vertex $3$ deleted:
A determinant is a signed sum over permutations. Cauchy–Binet made it a sum over subsets, the lemma made each term an indicator, and so the determinant counted.
Let $w_n$ be the number of closed walks of length $n$ from a fixed vertex of $K_3$. From Chapter 1,
Check: $(1-z)(1+z+3z^2+5z^3+11z^4+\cdots)$
$=1+0z+2z^2+2z^3+6z^4+\cdots$
Poles at $z=\tfrac12$ and $z=-1$: the reciprocals of the eigenvalues $2$ and $-1$ of $A(K_3)$.
The nearer pole belongs to the bigger eigenvalue, and it controls growth: $w_n\sim\tfrac13\,2^n$.
Every entry is a polynomial divided by $\prod_i(1-\lambda_iz)$. So every walk count, every trace, every entry of every power has a rational generating function, with poles only among the points $1/\lambda_i$.
$\dfrac1{1-\lambda z}=\sum_n\lambda^nz^n$ blows up at $z=1/\lambda$. A big eigenvalue is a near pole, and the nearest pole sets the growth rate.
On Friday you will compute one entry of $(I-zA)^{-1}$ for $K_3$ directly and watch $W(z)$ come out.
Act II (from Friday): where generating functions come from. A specification goes in; a generating function comes out.
Act III: what the right column says. You have just seen the second row's answer on the previous slide, and the rest come in November.
The last row's left side is empty on purpose. Matrices only make rational functions, and rational functions only have poles. Some sequences in this course have generating functions that are not rational, and no matrix will ever produce them.
An 8–12 page paper and a fifteen-minute talk at the symposium in finals week. Individual.
It rehearses the parts of a thesis that are hardest to learn from a problem set:
A project that cannot be stated as one question with one computation attached is too big.
Eight to twelve pages is a ceiling as much as a floor. A small question answered is worth more than a large one surveyed.
The prospectus (Nov 6) describes the computation you will run: what code, what inputs, what you expect to see, and what would surprise you. The bibliography includes the OEIS entries you have found.
Why two dates don't move. A late draft spends your reviewer's time rather than yours, and the final paper has to exist before the symposium.
The proposal: one page, four parts, due Friday, October 16.
The pitch: five minutes, to the class, in class. All five on Friday the 16th.
It is the first time you will hear yourself say the question out loud. Then it incubates over fall break.
Come talk to me. The scoping conversation is the most useful twenty minutes of the project. Use office hours or the booking link on the course page.
Plus two components that are graded as content, not as compliance:
A section on an approach that failed, and why: a method that did not work, a conjecture the data killed, a proof that broke at a step you can name.
A computation log, as an appendix outside the page count: the real record of what you ran, dead ends included.
A finished paper is always a tidied-up story about the work that produced it. These two are where the actual work is allowed to show — and they are the two things nobody can produce for you, since there are no false starts if nothing was tried.
An interactive artifact — a web page that lets someone explore the object of your project — with a four-to-six page note containing the mathematics. Both stay on the course page.
The course page's poset maps are examples of the genre; yours should let a reader see something a static picture cannot.
It is not the lighter option. It still needs a question, a computation, a failed approach, and a log, and it needs to work.
The point is to find out what you can do with a question nobody has prepared you for. If you're not sure whether something is too close, ask: the usual answer is a sideways move, not a no.
You may also propose a question that is not on the menu, if it passes the same test.
A careful student with a computer has a real chance of seeing something new. High ceiling; an honest negative result is a fine outcome.
A literature to lean on and a definite thing to learn and compute. Nothing lesser about them.
Computations first, theory second.
The interactive deliverable.
For the project, this week: