Enumerating spanning trees in bipartite graphsAlgebra & Discrete Mathematics
|Speaker:||Steve Klee, Seattle University|
|Start time:||Fri, Feb 8 2019, 1:10PM|
Ferrers graphs are bipartite graphs that arise naturally from the Ferrers diagram of a partition, with rows and columns corresponding to vertices and boxes corresponding to edges. In 2008, Ehrenborg and Van Willigenburg gave a beautiful formula for the number of spanning trees in a Ferrers graph and conjectured that Ferrers graphs have the maximal number of spanning trees for graphs with a given degree sequence.
This talk will focus on two main themes. First, we will use some linear algebraic techniques to give simple enumerations of spanning trees in some famous families of graphs, including Ferrers graphs. Second, we will use these techniques to give a new approach to Ehrenborg's conjecture. The talk will conclude with some open questions.