Spanning tree congestion of the hypercube (Q1045206)

The main purpose of the paper is to estimate the spanning tree congestion (introduced by the reviewer in [\textit{M. I. Ostrovskii}, ``Minimal congestion trees'', Discrete Math. 285, No. 1--3, 219--226 (2004; Zbl 1051.05032)]) for hypercubes \(Q_d\) which are defined as graphs whose vertex sets are sequences of \(0\) and \(1\) of length \(d\) and two vertices are adjacent if and only if the corresponding sequences differ at exactly one position. The spanning tree congestion of a graph \(G\) can be defined as \(s(G):=\min_T\max_{e\in E(T)}\# e_G(A_e,B_e)\), where the minimum is over all spanning trees, the maximum is over all edges of \(T\), and \(\# e_G(A_e,B_e)\) is the number of edges in \(G\) between the vertex sets of the components of \(T\) obtained after the removal of an edge \(e\). The most important and interesting result of the paper is an upper bound for \(s(Q_d)\) of the form \(O(2^d \log_2 d/d)\). This bound disproves the conjecture of \textit{Stephen W. Hruska} [``On tree congestion of graphs'', Discrete Math. 308, No. 10, 1801--1809 (2008; Zbl 1151.05014)] on the value of the spanning tree congestion of hypercubes. The author also found a lower bound of the spanning tree congestion for hypercubes which is close to his upper bound. The lower bound uses the isoperimetric technique suggested by the reviewer [op. cit] and the isoperimetric inequality of \textit{F. R. K. Chung}, \textit{Z. Füredi}, \textit{R. L. Graham} and \textit{P. Seymour} [``On induced subgraphs of the cube'', J. Comb. Theory, Ser. A 49, No. 1, 180--187 (1988; Zbl 0653.05037)]. Independently a similar lower bound was obtained by \textit{K. Kozawa}, \textit{Y Otachi} and \textit{K. Yamazaki} [``On spanning tree congestion of graphs'', Discrete Math. 309, No. 13, 4215--4224 (2009; Zbl 1232.05116)].