2012/07/04 by Olivier Bernardi, Bernardi, Olivier
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO
paper · pdf · doi:10.48550/arxiv.1207.0896
openalex publication_date 2012/07/04 · arxiv created 2012/07/12 · arxiv updated 2012/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give two combinatorial proofs of an elegant product formula for the number of spanning trees of the n-dimensional hypercube. The first proof is based on the assertion that if one chooses a uniformly random rooted spanning tree of the hypercube and orient each edge from parent to child, then the parallel edges of the hypercube get orientations which are independent of one another. This independence property actually holds in a more general context and has intriguing consequences. The second proof uses some "killing involutions" in order to identify the factors in the product formula. It leads to an enumerative formula for the spanning trees of the n-dimensional hypercube augmented with diagonals edges, counted according to the number of edges of each type. We also discuss more general formulas, obtained using a matrix-tree approach, for the number of spanning trees of the Cartesian product of complete graphs.