Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Enumerating spanning trees in bipartite graphs

Algebra & Discrete Mathematics

Speaker: Steve Klee, Seattle University
Location: 2112 MSB
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.