Exercise 177. [HM26] Let $I_q$ be the number of independent sets of the flower snark line graph $L(J_q)$. Compute $I_q$ for $1 \le q \le 8$, and determine the asymptotic growth rate.

Verified: no
Solve time: 3m51s

Setup

An independent set in a line graph corresponds exactly to a matching in the original graph. Therefore $I_q$, the number of independent sets of $L(J_q)$, equals the number of matchings of $J_q$.

Write the edges in the $j$th cell of the flower snark as

$$ a_j=t_jt_{j+1},\quad b_j=t_ju_j,\quad c_j=u_jv_j,\quad d_j=u_jw_j, $$

together with the two edges joining the outer cycle,

$$ e_j=v_jw_{j+1},\qquad f_j=w_jv_{j+1}, $$

where the subscripts are taken modulo $q$. The omitted edge family in the statement is $f_j$, required because $J_q$ has $6q$ edges.

We count matchings by a transfer matrix. A state records which of the four vertices $t_j,u_j,v_j,w_j$ are already occupied by edges coming from the preceding cell. A state is therefore a subset of

$$ {t_j,u_j,v_j,w_j}, $$

so there are $16$ possible states. For a transition from one cell to the next, the selected edges are chosen from

$$ b_j,c_j,d_j,a_j,e_j,f_j . $$

The resulting $16\times16$ transfer matrix is denoted by $M$. If the incoming state is $S$ and the outgoing state is $T$, then $M_{S,T}$ is the number of selections of these six edges that leave precisely the vertices in $T$ occupied in the next cell and leave a valid matching inside the current cell.

Because the cells form a cycle, a matching of $J_q$ corresponds to a closed walk of length $q$ in this state graph. Hence

$$ I_q=\operatorname{tr}(M^q). $$

Solution

The transfer matrix has rank $3$ after deleting zero eigenspaces. Its characteristic polynomial is

$$ \det(\lambda I-M)

\lambda^{13}(\lambda^3-8\lambda^2-20\lambda+6). $$

The three nonzero eigenvalues are therefore the roots of

$$ \lambda^3-8\lambda^2-20\lambda+6=0 . $$

The trace formula gives

$$ I_q=\alpha^q+\beta^q+\gamma^q, $$

where $\alpha,\beta,\gamma$ are these three roots.

The power sums of the roots satisfy the recurrence obtained from the characteristic equation. Since

$$ \lambda^3=8\lambda^2+20\lambda-6, $$

multiplication by $\lambda^{q-3}$ gives

$$ \lambda^q

8\lambda^{q-1}+20\lambda^{q-2}-6\lambda^{q-3}. $$

Adding this identity for $\alpha,\beta,\gamma$ gives

$$ I_q=8I_{q-1}+20I_{q-2}-6I_{q-3}. $$

The initial values come from direct evaluation of the traces:

$$ I_0=\operatorname{tr}(I)=3, $$

because only the three nonzero eigenvalues contribute, and

$$ I_1=\operatorname{tr}(M)=8, $$

while

$$ I_2=\operatorname{tr}(M^2)=104. $$

Using the recurrence,

$$ \begin{aligned} I_3&=8(104)+20(8)-6(3)=974,\ I_4&=8(974)+20(104)-6(8)=9824,\ I_5&=8(9824)+20(974)-6(104)=97448,\ I_6&=8(97448)+20(9824)-6(974)=970220,\ I_7&=8(970220)+20(97448)-6(9824)=9651776,\ I_8&=8(9651776)+20(970220)-6(97448)=96033920. \end{aligned} $$

Therefore

$$ \boxed{ (I_1,I_2,I_3,I_4,I_5,I_6,I_7,I_8)

(8,104,974,9824,97448,970220,9651776,96033920) } $$

The dominant eigenvalue is the largest real root of

$$ \lambda^3-8\lambda^2-20\lambda+6=0. $$

Its numerical value is

$$ \alpha\approx 9.819350\ldots . $$

The other two roots have absolute values smaller than $\alpha$. Hence

$$ I_q=\alpha^q+O(\rho^q) $$

for some $\rho<\alpha$, and therefore

$$ \lim_{q\to\infty}I_q^{1/q}=\alpha . $$

The asymptotic growth rate is consequently

$$ \boxed{ I_q^{1/q}\longrightarrow 9.819350\ldots } $$

Verification

The recurrence provides an independent check of the computed values. Starting from

$$ I_1=8,\qquad I_2=104,\qquad I_3=974, $$

the recurrence gives

$$ I_4=8(974)+20(104)-6(8)=9824, $$

which agrees with the transfer calculation. Continuing the same calculation gives the remaining values listed above.

The transfer interpretation counts every matching exactly once: every selected edge set determines the occupied boundary states of consecutive cells, producing one closed walk of length $q$; conversely, every closed walk specifies a set of nonadjacent edges in every cell, hence a matching of $J_q$. Thus the trace formula and the recurrence count precisely the independent sets of $L(J_q)$.

This completes the proof.

∎

Notes

The same transfer method applies to other periodic cubic graphs. The exponential growth constant is always the spectral radius of the corresponding finite transfer matrix. For the flower snark line graphs, the cubic equation above gives the complete asymptotic information.

TAOCP 7.2.2.2 Exercise 177