7
$\begingroup$

Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking).

Now, the number of reduced paths on cubic graphs of length $n$ (without backtracking) may be written as $p_n(x) =2^{n/2}U_n(\sqrt{2}x)$, where $U_n(x)$ is a Chebyshev Polynomial of the Second Kind.

The linked MathWorld page also says that

The polynomials can also be defined in terms of the sums $$ U_n(x)= \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2x)^{n-2r}\tag{16} $$

My question is:

What is the combinatorial interpretation of this relation?

$$ p_n(A/\sqrt{2})=2^{n/2}\sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2A)^{n-2r} $$

Why do alternating signs, binomial coefficients and powers of $2$ come into play while you're summing powers of $A$, i.e. number of ways with $r$ steps including backtracking, to finally get something without backtracking?

$\endgroup$
  • $\begingroup$ Inspired by Chris' answer. $\endgroup$ – draks ... Nov 27 '13 at 21:36
  • $\begingroup$ Are you sure that $p_n(A/\sqrt{2})$ actually is a Chebyshev polynomial? According to the answer of Chris Godsil that you link to, $p_2(A)$ does not satisfy the same recurrence as $p_r(A)$ with $r\ge3$ does. $\endgroup$ – Will Orrick May 9 '15 at 14:18
  • $\begingroup$ I think the correct relation is $$p_n(x)=\begin{cases}1 & n=0,\\ x & n=1,\\ 2^{n/2}U_n(x/2^{3/2})-2^{(n-2)/2}U_{n-2}(x/2^{3/2}) & n\ge2.\end{cases}$$ The first few terms in the sequence $2^{n/2}U_n(x/2^{3/2})$ are $1$, $x$, $x^2-2$, $x^3-4x$, $x^4-6x^2+4$, $x^5-8x^3+12x$. The first few terms in the sequence $p_n(x)$ are $1$, $x$, $x^2-3$, $x^3-5x$, $x^4-7x^2+6$, $x^5-9x^3+16x$. Both sequences obey the recurrence $f_n(x)=xf_{n-1}(x)-2f_{n-2}(x)$ for $n\ge3$. The difference is that $2^{n/2}U_n(x/2^{3/2})$ also obeys the recurrence when $n=2$, whereas $p_n(x)$ does not. $\endgroup$ – Will Orrick May 9 '15 at 21:15
  • $\begingroup$ The MathWorld expression you quote implies that $$2^{n/2}U_n(x/2^{3/2})=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r},$$ and therefore that $$p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{r=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}.$$ It seems likely that this can be understood in terms of the Principle of Inclusion-Exclusion, but it looks a bit messy. $\endgroup$ – Will Orrick May 9 '15 at 22:04
  • $\begingroup$ @WillOrrick I remember being confused about this chebychev connection till I convinced myself that they are second kin, but it's been a while since I checked it. Maybe one should ask Chris again at the other post for clarification. Would you like to, since you're not convinced...When it's correct I don't care about a mess... $\endgroup$ – draks ... May 10 '15 at 11:41
2
+50
$\begingroup$

First a correction regarding the connection with Chebyshev polynomials. Quoting from Chris Godsil's answer to your earlier question:

Observe that $$ p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta, $$ where $\Delta$ is the diagonal matrix of valencies of $X$. If $n\ge3$ we have the recurrence $$ Ap_n(A) = p_{n+1}(A) +(\Delta-I) p_{n-1}(A). $$

(I have changed $r$ to $n$ in the quoted text.) For cubic graphs, $\Delta=3I$, which results in the recurrence $$ p_{n+1}(t)=tp_n(t)−2p_{n−1}(t). $$ This is related to the recurrence for Chebyshev polynomials by a change of variable, $$ p_{n+1}(2^{3/2}t)=2^{3/2}tp_n(2^{3/2}t)−2p_{n−1}(2^{3/2}t), $$ followed by a rescaling, $$ 2^{−(n+1)/2}p_{n+1}(2^{3/2}t)=2t\cdot2^{−n/2}p_n(2^{3/2}t)−2^{−(n−1)/2}p_{n−1‌}(2^{3/2}t). $$ Hence $q_n(t):=2^{−n/2}p_n(2^{3/2}t)$ satisfies the Chebyshev recurrence, $q_{n+1}(t)=2tq_n(t)-q_{n-1}(t)$. This can be used to obtain $q_n(t)$ for $n\ge3$. For $n<3$, $$ q_0(t)=1,\quad q_1(t)=2t,\quad q_2(t)=4t^2-3/2. $$

The Chebyshev polynomials of the second kind are generated from the same recurrence with the initial conditions $$ U_0(t)=1,\quad U_1(t)=2t, $$ which result in $$ U_2(t)=4t^2-1 $$ rather than $4t^2-3/2$. The appearance of the $3/2$ term $q_2(t)$ can be traced to the occurrence of $\Delta$ rather than $\Delta-I$ in the expression for $p_2(A)$. The recurrence implies that $U_{-1}(t)=0$. As a consequence, $$ q_n(t)=U_n(t)-\frac{1}{2}U_{n-2}(t) $$ holds for $n=1$ and $n=2$. By linearity of the recurrence, this extends to all $n\ge1$. It does not hold for $n=0$, however, since $U_{-2}(t)=-1$.

From $p_n(t)=2^{n/2}q_n(2^{-3/2}t)$ it follows that $$ p_n(t)=2^{n/2}U_n(2^{-3/2}t)-2^{(n-2)/2}U_{n-2}(2^{-3/2}t) $$ for $n\ge1$. The MathWorld expression you quote then implies that $$ 2^{n/2}U_n(2^{-3/2}t)=\sum_{r=0}^{\lfloor n/2\rfloor}(−2)^r\binom{n−r}{r}t^{n−2r}, $$ and therefore that $$ p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{r=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}. $$ Shifting the summation index in the second sum in the expression above and bringing the minus sign inside gives $$ p_n(x)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)(-2)^{r-1}\binom{n-1-r}{r-1}x^{n-2r}, $$ which is a useful form for the purpose of interpretation.

Original answer: This formula can be understood in terms of the process of iteratively carrying out the recurrence in Chris Godsil's answer, which gives rise to sums of products of $A$ and $\Delta$. Define $$ \Delta':=\begin{cases}\Delta & \text{if first factor in the product}\\ \Delta-I & \text{otherwise.}\end{cases}$$ Note that for cubic graphs, $$ \Delta':=\begin{cases}3I& \text{if first factor in the product}\\ 2I & \text{otherwise.}\end{cases}$$ Starting with $p_1(A)=A$, $p_{n+1}(A)$ is obtained from $p_n(A)$ by

  1. appending a factor of $A$ to every term in the sum;
  2. for any term in the resulting sum that ends with two consecutive factors of $A$, subtracting the product that results from replacing these final two factors of $A$ with a single factor of $\Delta'$. Carrying this out in the case $n=1$, Step 1 gives $AA$ and Step 2 gives $AA-\Delta'$, with the result $$p_2(A)=AA-\Delta'.$$ Then for $n=2$, Step 1 gives $AAA-\Delta'A$, and Step 2 gives $-A\Delta'$, with the result $$p_3(A)=AAA-\Delta'A-A\Delta'.$$ One more time: Step 1 gives $AAAA-\Delta'AA-A\Delta'A$ and Step 2 gives $-AA\Delta'+\Delta'\Delta'$, with the result $$p_4(A)=AAAA-\Delta'AA-A\Delta'A-AA\Delta'+\Delta'\Delta'.$$

It should be clear that the result of the recurrence is that $p_n(A)$ is a sum with the following characteristics:

  1. every string of weight $n$ consisting of $A$ and $\Delta'$ occurs exactly once; here weight is computed as $$(\text{number of $A$s})+2\cdot(\text{number of $\Delta'$s})$$ since each $\Delta'$ replaces two $A$s;
  2. the sign equals $$(-1)^\text{number of $\Delta'$s}.$$

The sum may have anywhere between $0$ and $\lfloor n/2\rfloor$ $\Delta'$s. A string containing $r$ $\Delta'$s consists of $n-r$ symbols since each $\Delta'$ has weight $2$. Hence there are $\binom{n-r}{r}$ strings with $r$ $\Delta'$s.

These observations can be related to the expression for $p_n(x)$ given above. We start by incorrectly replacing every occurrence of $\Delta'$ in each string with $2I$. This gives the incorrect formula $$ p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}. $$ The formula is wrong because the first $\Delta'$ in a string should have been replaced with $3I$ instead of $2I$ if that $\Delta'$ were the first letter of the string. We therefore correct our expression by adding $(-1)\cdot(-2)^{r-1}A^{n-2r}$ for each string with $r$ $\Delta'$s in which $\Delta'$ is the first letter. There are $\binom{n-1-r}{r}$ such strings. As a result, the correct expression is $$ p_n(A)=\sum_{r=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}A^{n-2r}+\sum_{r=1}^{\lfloor n/2\rfloor}(-1)\cdot(-2)^{r-1}\binom{n-1-r}{r}A^{n-2r}. $$

New answer (19 May 2015): The powers of $-1$ suggest that the sum arises from the principle of inclusion-exclusion. In general terms, given a finite set $S$ and a set $T$, the size of the complement of $T$ is given by $$ \lvert T'\rvert=\lvert S\rvert-\sum_{i=1}^N S_i+\sum_{1\le i<j\le N}S_i\cap S_j-\sum_{1\le i<j<k\le N}S_i\cap S_j\cap S_k+\ldots, $$ where $S_1$, $S_2$, $\ldots$, $S_N$ are subsets of $S$ whose union is $T$. In your problem, the role of $S$ is played by the set of paths from $a$ to $b$ of length $n$, which we will denote $P(a,b,n,\{\})$; the role of $T$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing at least one reversing step, and the role of $T'$ is played by the subset of $P(a,b,n,\{\})$ consisting of those paths containing no reversing step.

To carry out an inclusion-exclusion calculation, the first step is to choose sets to play the role of $S_i$. A natural choice is to use the sets $$ P(a,b,n,\{j\})=\text{set of paths from $a$ to $b$ of length $n$ in which step $j$ reverses step $j-1$,} $$ where $j$ ranges from $2$ to $n$. It is clear that the union of these sets is the set of paths from $a$ to $b$ of length $n$ containing one or more reversing steps. In performing the inclusion-exclusion sum one needs to compute sizes of intersections of two or more sets—intersections like $P(a,b,n,\{j\})\cap P(a,b,n,\{k\})=:P(a,b,n,\{j,k\})$, for example. In this example, the size of the intersection depends on whether $k=j+1$ or $k>j+1$, and this makes the computation a bit involved. It is carried out in this post.

Since the only requirement on the sets $S_i$ is that their union equal $T$, many choices are possible. In this problem, a better choice for the sets to play the role of $S_i$ are the sets $$ \begin{aligned} R(a,b,n,\{j\})=\,&\text{set of paths from $a$ to $b$ of length $n$ in which step $j$ reverses step $j-1$ and}\\ &\text{step $j-1$ does not reverse step $j-2$,} \end{aligned} $$ where again $j$ ranges from $2$ to $n$. (When $j=2$ we consider the condition that step $1$ not reverse step $0$ to be vacuously true as there is no step $0$.) Again, the union of these sets is the set of all paths from $a$ to $b$ of length $n$ containing one or more reversing steps. This follows from the fact that in any path containing a reversing step, there is a reversing step of least index. Hence if that least index is $j$, then the path is contained in $R(a,b,n,\{j\})$.

Since $R(a,b,n,\{j\})\cap R(a,b,n,\{j+1\})=\emptyset$, we need only consider the case $R(a,b,n,\{j\})\cap R(a,b,n,\{k\})=:R(a,b,n,\{j,k\})$ with $k>j+1$ and, more generally, intersections like $R(a,b,n,\{j_1\})\cap\ldots\cap R(a,b,n,\{j_r\})=:R(a,b,n,\{j_1,\ldots,j_r\})$ in which $\lvert j_k-j_i\rvert\ge2$ for all distinct $i$, $k$ in $\{1,2,\ldots,r\}$. We will assume this condition from now on.

The set $R(a,b,n,\{\})$ of all paths from $a$ to $b$ of length $n$ has size given by the $(a,b)$ element of $A^n$. To handle the case where a reversing step is required at a given position, we need to consider products in which a pair of $A$s has been replaced by $\Delta$ or $\Delta-I$. We use the definition of $\Delta'$ given in the earlier answer. Since a reversal in step $j$ implies that the same vertex is visited after the $(j−2)^\text{nd}$ and $j^\text{th}$ steps, and since if $j>2$ the vertex visited after the $(j-1)^\text{st}$ step cannot be the same as that visited immediately prior to the $(j-2)^\text{nd}$ step, $\lvert R(a,b,n,\{j\})\rvert$ is the $(a,b)$ element of $$ A^{j−2}\Delta'A^{n−j}= \begin{cases}(3I)A^{n-2}=3A^{n-2} & \text{if $j=2$,}\\ A^{j−2}(2I)A^{n−j}=2A^{n−2} & \text{if $j>2$.} \end{cases} $$ In other words, the two factors of $A$ at positions $j-1$ and $j$ in $A^n$ have been replaced with $\Delta'$. By the same argument, $\lvert R(a,b,n,\{j_1,\ldots,j_r\})\rvert$ is the $(a,b)$ element of the product in which the two $A$s at each of the pairs of positions $(j_1-1, j_1)$, $\ldots$, $(j_r-1,j_r)$ in the product $A^n$ get replaced with $\Delta'$. Because of the condition $\lvert j_k-j_i\rvert\ge2$ for distinct $i$, $k$, these replacements never occur in overlapping positions and can therefore be made independently of one another. Denote by $D_r$ the set of subsets of $\{2,3,\ldots,n\}$ of size $r$ in which this "difference-$2$" condition holds.

By the principle of inclusion-exclusion, the number of paths from $a$ to $b$ of length $n$ with no reversing steps is given by $$ \sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}\lvert R(a,b,n,A)\rvert. $$ This is equal to the $(a,b)$ element of $$ \sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{A\in D_r}[2+\mathbf{1}_A(2)]2^{r-1}A^{n-2r}=\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\left[\sum_{A\in D_r}2^rA^{n-2r}+\sum_{A\in D_r,2\in A}2^{r-1}A^{n-2r}\right], $$ where $\mathbf{1}_A(x)$ is the indicator function whose value is $1$ if $x\in A$ and $0$ if $x\notin A$. There is a one-to-one correspondence between elements of $D_r$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s. There is a one-to-one correspondence between elements of $D_r$ containing $s$ and strings containing $n-2r$ $A$s and $r$ $\Delta'$s such that the initial element of the string is a $\Delta'$. This implies that there are $\binom{n-r}{r}$ elements in $D_r$ and $\binom{n-1-r}{r-1}$ elements in $D_r$ that contain $2$. The sum given in my earlier answer results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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