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.
Hello, just a note. There is typo in “There is an analogous problem for general graphs WHERE threshold graphs replace Ferrer’s graphs.”
GK: Thanks, corrected.
Can anything special be said about the case where the bipartite graph is planar?
Very attractive question indeed. Note that in any graph with degrees
the number of spanning trees does not exceed
(quick proof: mark the vertex of maximal degree and consider any tree as rooted from the marked vertex, then each non-marked vertex must have a unique successor which is chosen from its neighbors), that looks quite close. We may reformulate further the question probabilistically: mark a vertex of degree
and choose fo any non-marked vertex
a random neighbor
uniformly and independently. Then the probability that the function
does not have cycles (equivalently, that the
-orbit of any vertex contains a marked vertex) does not exceed
.
Looks like he’s holding a permutahedron.