Richard Ehrenborg’s problem on spanning trees in bipartite graphs

Richard Ehrenborg with a polyhedron

In the Problem session last Thursday in Oberwolfach, Steve Klee presented a beautiful problem of Richard Ehrenborg regarding the number of spanning trees in bipartite graphs.

Let be a bipartite graph with vertices on one side and vertices on the other side, and with vertex-degrees and .

Ehrenborg’s problem: Is it the case that the number of spanning trees of is at most

.

In words, the number of spanning trees is at most the product of the vertex degrees divided by the sizes of the two sides.

For example for the complete bipartite graph the number of the spanning trees is so equality hold.  More genarally,  equality holds for Ferrer’s graphs. Those are graphs where the vertices on the two sides are ordered and if is an edge so are and for and . See this paper of Richard Ehrenborg and Stephanie van Willigenburg.

Steve Klee and Matthiew Stamps  found a new point of view for both the weighted and unweighted settings. (See this paper by Klee and Stamps and this paper.)

There is an analogous problem for general graphs where threshold graphs replace Ferrer’s graphs. This is related to a conjecture by Grone and Merris. (There are importat related works by Kelmans.) See this paper by Duval and Reiner and this paper by Martin and Reiner for related results and conjectures on spectrum of Laplacians for general simplicial complexes and shifted simplicial complexes.

I have learned that the Crone-Merris conjecture itself was settled by Hua Bai in 2012. The book Spectra of Graphs By Andries E. Brouwer and Willem H. Haemer has a chapter about the proof. The Duval-Reiner’s high dimensional conjecture is still open. (I thank Vic Reiner for some helpful information.)  We also note an interesting 2012 paper Upper bounds for the number of spanning trees of graphs by Bozkurt, Ş. Burcu.