**Date & Time:** Thursday, August 22, 2013, 14:00- 15:00.

**Venue:** Ramanujan Hall

**Title:** A bijective proof problem on the spanning trees of the Grassmann graphs

**Speaker:** Murali K. Srinivasan, IIT Bombay

**Abstract:** Grassmann graphs (and their q=1 case, Johnson graphs) have been well
studied in algebraic graph theory. The adjacency eigenvalues of the Grassmann
graphs (and hence the Laplacian eigenvalues, since these graphs are regular)
were determined in the classical paper of
Delsarte (1976). Recently, it was noticed by the speaker that the expression
for the Laplacian eigenvalues admits an elegant simplification leading to an
interesting bijective proof problem on the spanning trees. The simplest case
of this problem is Joyal's celebrated bijection for the
Cayley tree counting formula. All other cases are open.
Once one has guessed the simple expression for the Laplacian eigenvalues it is
dead easy to verify it, either by hand or using Maple. Actually,we did not
guess the expression but stumbled on it while solving a related and more
difficult problem, that of finding a formula for the number of
spanning trees in the q-analog of the n-cube. Here the Laplacian eigenvalues
are unknown but we explicitly block diagonalize the Laplacian, using the
GL(n,F_q) action on the vertices (in whose commutant the Laplacian lies), and
give a positive combinatorial formula
for the determinants of the blocks. The simple expression for the Laplacian
eigenvalues of the Grassmann graphs appear as parameters in this formula.