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.

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

Jan Bok says:

September 1, 2019 at 7:26 pm

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.

Joseph Malkevitch says:

September 2, 2019 at 9:16 pm

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

Fedor Petrov says:

September 2, 2019 at 10:54 pm

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)$ .

Tom Copeland says:

October 15, 2019 at 3:31 am

Looks like he’s holding a permutahedron.

	Not Quite Getting Up… on Gil’s Collegial Quantum…
	gentzen on Gil’s Collegial Quantum…
	Craig on Gil’s Collegial Quantum…
	Daniel Bilar on Gil’s Collegial Quantum…
	Gil Kalai on Gil’s Collegial Quantum…
	Romain Alléaume on Gil’s Collegial Quantum…
	Gil Kalai on Amazing! Keith Frankston, Jeff…
	Christoph on Amazing! Keith Frankston, Jeff…
	Gil’s Collegia… on The Prisoner’s Dilemma,…
	Gil’s Collegia… on If Quantum Computers are not P…
	Gil’s Collegia… on Noisy quantum circuits: how do…
	Gil’s Collegia… on Quantum computers: amazing pro…