Counting trees and nilpotent endomorphisms

Vic Reiner
Friday, March 27, 2020 - 3:35pm to 4:25pm
Via Virtual - Zoom

A formula of Cayley (1889) says that the number of trees on vertex set [n]:={1,2,...,n} is n^{n-2}. Among its many proofs, my favorite is a gorgeous bijection due to Andre Joyal in 1981. One can also view Cayley's formula as asserting that there are n^{n-1} vertex-rooted trees on [n], or equivalently n^{n-1} eventually constant self-maps on [n].

This talk will review Joyal's proof, and its recent revisitation by Tom Leinster in arXiv:1912.12562. Leinster gives a beautiful q-analogue of the proof, that proves a q-analogous theorem of Fine and Herstein (1958). The latter theorem counts those linear self-maps of an n-dimensional vector space over a finite field F_q which are eventually constant, that is, nilpotent as linear maps.