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 G be a bipartite graph with m vertices on one side and n vertices on the other side, and with vertex-degrees d_1,d_2,\dots ,d_m and e_1,e_2,\dots e_n.

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

m^{-1}n^{-1} \prod_{i=1}^m d_i \prod_{j=1}^n e_j.

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 n^{m-1}m^{n-1} 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 (a,b) is an edge so are (a',b) and (a,b') for a'<a and b'<b. 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.

This entry was posted in Combinatorics, Open problems and tagged . Bookmark the permalink.

4 Responses to Richard Ehrenborg’s problem on spanning trees in bipartite graphs

  1. Jan Bok says:

    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.

  2. Can anything special be said about the case where the bipartite graph is planar?

  3. Fedor Petrov says:

    Very attractive question indeed. Note that in any graph with degrees d_1\leqslant d_2\leqslant\ldots d_n the number of spanning trees does not exceed d_1\ldots d_{n-1} (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 d and choose fo any non-marked vertex v a random neighbor f(v) uniformly and independently. Then the probability that the function f does not have cycles (equivalently, that the f-orbit of any vertex contains a marked vertex) does not exceed d/(mn).

  4. Tom Copeland says:

    Looks like he’s holding a permutahedron.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s