Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds?

[Edit] Note: the walk can repeat vertices.

share|improve this question

3 Answers 3

up vote 19 down vote accepted

Yes (assuming a closed walk can repeat vertices). For any finite graph $G$ with adjacency matrix $A$, the total number of closed walks of length $r$ is given by

$$\text{tr } A^r = \sum_i \lambda_i^r$$

where $\lambda_i$ runs over all the eigenvalues of $A$. So it suffices to compute the eigenvalues of the adjacency matrix of the $n$-cube. But the $n$-cube is just the Cayley graph of $(\mathbb{Z}/2\mathbb{Z})^n$ with the standard generators, and the eigenvalues of a Cayley graph of any finite abelian group can be computed using the discrete Fourier transform (since the characters of the group automatically given eigenvectors of the adjacency matrix). We find that the eigenvalue $n - 2j$ occurs with multiplicity ${n \choose j}$, hence

$$\text{tr } A^r = \sum_{j=0}^n {n \choose j} (n - 2j)^r.$$

For fixed $n$ as $r \to \infty$ the dominant term is given by $n^r + (-n)^r$.

share|improve this answer
    
Thanks! that's what I needed. –  Lev Reyzin Jul 31 '11 at 19:24
    
I'm guessing not, but is there any chance this expression has a closed form? –  Lev Reyzin Aug 2 '11 at 17:12
    
@Lev: you mean without a summation over $n$? I doubt it. Is fixed $n$ as $r \to \infty$ not the regime you're interested in? –  Qiaochu Yuan Aug 2 '11 at 17:36
    
In some sense, I'm more interested in fixed r as n gets large. The summation is certainly quite helpful, but of course if a closed form existed, it would even be nicer :) –  Lev Reyzin Aug 2 '11 at 18:06

The number of such walks is $2^n$ (the number of vertices of the $n$-cube) times the number of walks that start (and end) at the origin. We may encode such a walk as a word in the letters $1, -1, \dots, n, -n$ where $i$ represents a positive step in the $i$th coordinate direction and $-i$ represents a negative step in the $i$th coordinate direction. The words that encode walks that start and end at the origin are encoded as shuffles of words of the form $i\ -i \ \ i \ -i \ \cdots\ i \ -i$, for $i$ from 1 to $n$. Since for each $i$ there is exactly one word of this form for each even length, the number of shuffles of these words of total length $m$ is the coefficient of $x^m/m!$ in $$\biggl(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}\biggr)^{n} = \left(\frac{e^x + e^{-x}}{2}\right)^n. $$ Expanding by the binomial theorem, extracting the coefficient of $x^r/r!$, and multiplying by $2^n$ gives Qiaochu's formula.

Let $W(n,r)$ be the coefficient of $x^r/r!$ in $\cosh^n x$, so that $$W(n,r) = \frac{1}{2^n}\sum_{j=0}^n\binom{n}{j} (n-2j)^r.$$ Then we have the continued fraction, due originally to L. J. Rogers, $$ \sum_{r=0}^\infty W(n,r) x^r = \cfrac{1}{1- \cfrac{1\cdot nx^2}{ 1- \cfrac{2(n-1)x^2}{1- \cfrac{3(n-2)x^2}{\frac{\ddots\strut} {\displaystyle 1-n\cdot 1 x^2} }}}} $$ A combinatorial proof of this formula, using paths that are essentially the same as walks on the $n$-cube, was given by I. P. Goulden and D. M. Jackson, Distributions, continued fractions, and the Ehrenfest urn model, J. Combin. Theory Ser. A 41 (1986), 21–-31.

Incidentally, the formula given above for $W(n,r)$ (equivalent to Qiaochu's formula) is given in Exercise 33b of Chapter 1 of the second edition of Richard Stanley's Enumerative Combinatorics, Volume 1 (not published yet, but available from his web page). Curiously, I had this page sitting on my desk for the past month (because I wanted to look at Exercise 35) but didn't notice until just now that this formula was on it.

share|improve this answer
    
thanks - this is nice. –  Lev Reyzin Aug 2 '11 at 23:08

Assuming a "closed walk" can repeat vertices, we can count closed walks starting at $0$ by counting the $r$-sequences of $[n]$ so that each number appears an even number of times. The bijection is given by labeling edges by the coordinate that is toggled between the vertices. You can probably count these sequences by inclusion/exclusion and then multiply by $2^n/r$ to account for the choice of start position.

share|improve this answer
    
If we assume the path moves in each dimension 0 or 2 times, you can select ${n \choose r/2}$ dimensions and then permute them $r^1/2^r$ ways. This is a lower bound on the number of walks and is likely the right asymptotics. –  Derrick Stolee Jul 31 '11 at 17:03
    
That should be $r!/2^r$. –  Derrick Stolee Jul 31 '11 at 17:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.