Date & Time: Thursday, August 29, 2013, 14:00- 15:00.
Venue: Ramanujan Hall
Title: A bijective proof problem on the spanning trees of the Grassmann graphs II
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.