Expected meeting time conjecture for random walks on regular graphs

Counterexample to the intended eigenbasis claim and the meeting-time formula

The printed zero-sum conditions have indexing inconsistencies. The following counterexamples do not rely on those inconsistencies: they contradict the substantive normalization and orthogonality requirements themselves, and also disprove the paper's separate expected-meeting-time conjecture.

Suppose a connected regular graph on $n$ vertices has an orthogonal adjacency eigenbasis satisfying

$$\xi_i(v)=1,\qquad \langle\xi_i,\xi_j\rangle=n\delta_{ij}.$$

For every adjacency eigenvalue $\theta$, its spectral projector $E_\theta$ must then satisfy

$$(E_\theta)_{vv} =\sum_{i:\,A\xi_i=\theta\xi_i}\frac{\xi_i(v)^2}{n} =\frac{\operatorname{rank}E_\theta}{n}.$$

Consequently

$$(A^\ell)_{vv}=\frac{\operatorname{tr}(A^\ell)}n \qquad(\ell\ge0). \tag{1}$$

Already on eight vertices, take the connected cubic graph with edges

$$02,03,04,12,13,15,23,46,47,56,57,67.$$

Direct counting gives

$$\operatorname{diag}(A^3)=(2,2,4,4,2,2,4,4), \qquad \frac{\operatorname{tr}(A^3)}8=3.$$

Thus (1) fails at every possible distinguished vertex, disproving the intended eigenbasis conjecture.

Moreover, for the exact prescribed transition matrix $P=(I+A)/4$, let two walkers start independently and uniformly. Their hitting times satisfy

$$T_{uu}=0,\qquad T_{uv}=1+\sum_{a\ne b}P_{ua}P_{vb}T_{ab}\quad(u\ne v).$$

Solving these finite rational equations gives

$$\mathbb E\tau=\frac1{64}\sum_{u\ne v}T_{uv} =\frac{5873}{631}.$$

On the other hand,

$$\det(zI-A)=(z-3)(z-1)(z+1)^4(z^2-5),$$

and hence the conjectured spectral answer is

$$\sum_{\lambda\in\operatorname{Spec}(I-P^2),\,\lambda\ne0} \frac1\lambda =\frac{28}{3}.$$

The exact discrepancy is therefore

$$\mathbb E\tau- \sum_{\lambda\ne0}\frac1\lambda =-\frac{49}{1893}\ne0.$$

In fact both failures occur in every degree $d\ge3$. Put $s=d+1$, take two copies of $K_s$, remove one edge in each copy, and connect their exposed endpoints by a matching. This gives a connected $(s-1)$-regular graph on $2s$ vertices. Its closed three-walk counts are

$$(A^3)_{vv}= \begin{cases} (s-2)(s-3),&v\text{ is an exposed endpoint},\\ s(s-3),&v\text{ is an interior vertex}, \end{cases} \qquad \frac{\operatorname{tr}(A^3)}{2s} =\frac{(s-3)(s^2-4)}s.$$

Neither local value equals the average for $s\ge4$, so the required eigenbasis exists at no vertex.

For completeness, the seven nonmeeting ordered-pair classes have multiplicities

$$w=(4,8(s-2),2(s-2)(s-3),4,4,8(s-2),2(s-2)^2)$$

and transition-count matrix

$$C_s= \begin{pmatrix} 2&2(s-2)&(s-2)(s-3)&0&2&2(s-2)&0\\ 1&3(s-2)&(s-2)(s-3)&1&1&s-2&0\\ 2&4(s-2)&(s-2)(s-3)&0&0&0&0\\ 0&2(s-2)&0&2&0&2(s-2)&(s-2)^2\\ 2&2(s-2)&0&0&2&2(s-2)&(s-2)^2\\ 1&s-2&0&1&1&3(s-2)&(s-2)^2\\ 0&0&0&2&2&4(s-2)&(s-2)^2 \end{pmatrix}.$$

Thus $\mathbb E\tau_s=w^{\mathsf T}(I-C_s/s^2)^{-1}\mathbf1/(4s^2)$. The adjacency characteristic polynomial is

$$(z-(s-1))(z-1)(z+1)^{2s-4} \bigl(z^2-(s-4)z-(3s-7)\bigr).$$

With

$$D_s=s^6+2s^5-4s^4-4s^3+10s^2+12s-24>0,$$

direct rational elimination gives

$$\boxed{\; \mathbb E\tau_s- \sum_{\lambda\in\operatorname{Spec}(I-P_s^2),\,\lambda\ne0} \lambda^{-1} = -\frac{(s-3)^2(s^2+2s-4)(s^3-4s+8)^2} {4(s-2)(s+2)(s^2-2s+2)D_s} <0 \;}$$

for every $s\ge4$, where $P_s=(I+A_s)/s$. Hence both source conjectures fail for an infinite family covering every regular degree at least three.