Introduction to Graph Theory · Problem 5.29

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · spanning-trees-hypercube

Problem

Let nn be a positive integer. Let QnQ_n be the nn-hypercube graph (as defined in Definition 2.14.7). Recall that its vertex set is the set V:={0,1}nV := \{0,1\}^n of length-nn bitstrings, and that two vertices are adjacent if and only if they differ in exactly one bit. Our goal is to compute the #\# of spanning trees of QnQ_n. Let DD be the digraph QnbidirQ_n^{\text{bidir}}. Let LL be the Laplacian of DD. We regard LL as a V×VV \times V-matrix (i.e., as a 2n×2n2^n \times 2^n-matrix whose rows and columns are indexed by bitstrings in VV). We shall use the notation aia_i for the ii-th entry of a bitstring aa. Thus, each bitstring a∈Va \in V has the form a=(a1,a2,…,an)a = (a_1, a_2, \ldots, a_n). For any two bitstrings a,b∈Va, b \in V, we define the number ⟨a,b⟩\langle a, b \rangle to be the integer a1b1+a2b2+⋯+anbna_1 b_1 + a_2 b_2 + \cdots + a_n b_n. (a) Prove that every bitstring a∈Va \in V satisfies ∑b∈V(−1)⟨a,b⟩={2n,if a=0;0,otherwise.\sum_{b \in V} (-1)^{\langle a, b \rangle} = \begin{cases} 2^n, & \text{if } a = \mathbf{0}; \\ 0, & \text{otherwise.} \end{cases} Here, 0\mathbf{0} denotes the bitstring (0,0,…,0)∈V(0, 0, \ldots, 0) \in V. Now, define a further V×VV \times V-matrix GG by requiring that its (a,b)(a,b)-th entry is Ga,b=(−1)⟨a,b⟩for any a,b∈V.G_{a,b} = (-1)^{\langle a, b \rangle} \qquad \text{for any } a, b \in V. Furthermore, define a diagonal V×VV \times V-matrix DD by requiring that its (a,a)(a,a)-th entry is Da,a=2⋅(# of i∈{1,2,…,n} such that ai=1)=2⋅(the number of 1s in a)for any a∈VD_{a,a} = 2 \cdot (\# \text{ of } i \in \{1, 2, \ldots, n\} \text{ such that } a_i = 1) = 2 \cdot (\text{the number of 1s in } a) \qquad \text{for any } a \in V (and its off-diagonal entries are 0). Prove the following: (b) We have G2=2n⋅IG^2 = 2^n \cdot I, where II is the identity V×VV \times V-matrix. (c) We have GLG−1=DGLG^{-1} = D. (d) The eigenvalues of LL are 2k2k for all k∈{0,1,…,n}k \in \{0, 1, \ldots, n\}, and each eigenvalue 2k2k appears with multiplicity (nk)\binom{n}{k}. (e) The #\# of spanning trees of QnQ_n is 12n∏k=1n(2k)(nk).\frac{1}{2^n} \prod_{k=1}^{n} (2k)^{\binom{n}{k}}.

Related theory

Browse the problem library