 |
Abstract: In 1847, Gustav Kirchhoff published a famous paper laying out the foundations for the theory of electric networks. In the course of his investigations, he showed that you can count the number of spanning trees of a given linear graph by taking the determinant of a certain matrix associated to the graph (the `Kirchhoff matrix'). In the case of the complete graph $K_n$, which consists of $n$ vertices wired together in pairs in all $\binom{n}{2}$ possible ways, we can evaluate this determinant by doing a simple series of row and column operations, and we find that $K_n$ has $n^{n-2}$ spanning trees. This formula was published by Cayley in 1897. It can be proven combinatorially by showing how to `code' a tree as a sequence of numbers ($n-2$ numbers, all between 1 and $n$). Various codes for trees are known. The first was Prufer's, published in 1918; one of the cleverest-looking is the `UCSD Code', published by Egecioglu and Remmel in 1986. In her 1999 UCSD doctoral thesis, Sally Picciotto showed how you can find the UCSD code by methodically translating the algebraic steps used to evaluate Kirchhoff's determinant into a code. The key tool is the involution principle of Garsia and Milne.
The UCSD code has many excellent properties. In particular, it yields an ideal way to cheat at clock solitaire.
This talk will be accessible to undergraduates. (No previous knowledge of clock solitaire is necessary.)
This talk will be accessible to undergraduates.
|