GRASP Special Seminar - Hoda Bidkhori, North Carolina State University, "The Critical Group of Line Graphs and a Bijective Proof of a Theorem of Knuth"
Friday, September 9, 2011 - 2:00pm to 3:00pm
Abstract: The line graph LG of a directed graph G has a vertex for every edge of
G and an
edge for every path of length 2 in G. In 1967, Knuth used the Matrix-Tree
Theorem to prove a formula for the number of spanning trees of LG, and he
asked for a bijective proof. In this paper, we give a bijective proof of a
generating function identity due to Levine which generalizes Knuths
formula. Finally, we determine the critical groups of two families of graphs widely studied in computer science, the Kautz graphs and de Bruijn
graphs. This is a joint work with S. Kishore.
Hoda Bidkhori received the B.S. degree in Applied Mathematics Department from
Sharif University of Technology, Tehran, Iran, in 2004, and the Ph.D. degree
in Applied Mathematics from the Massachusetts Institute of Technology,
Cambridge, in 2010. Since 2010, she has been a postdoctoral research associate in
Applied Mathematics and Statistics Department at North Carolina State
University. Hoda Bidkhori is the recipient of the Rogers Family prize
at MIT as
well as several Medals in International Math Competitions.