- On Spanning Tree Counts for Bipartite Graphs
- Project Year:
2021
- REU Student (s):
Aaditya Raghavan | Georgia Institute of Technology-Main Campus GA
- Student 1 Institution:
Georgia Institute of Technology-Main Campus
- Project Mentor:
Bhargav Narayanan
- Project Mentor Area:
Mathematics
- Project Abstract:
Ehrenborg conjectured that, for a simple bipartite graph G, the number of spanning trees of G, is bounded above. The bound is known to hold with equality for a class of bipartite graphs known as Ferrers graphs, and not necessarily with equality in other, specific classes of bipartite graphs. In this paper, we introduce another inequality motivated by the Cartesian product of bipartite graphs - in particular, an inequality that relates the eigenvalues of the Laplacians of the multiplicand graphs, with products of the vertex degrees and the part sizes of the factor graphs. Furthermore, we introduce an inductive framework through which the conjecture can be approached by means of a determinantal inequality, along with some preliminary results that can be proved using such a technique.
