Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs

Shunya Tamura; Tsuyoshi Miezaki

Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs

T0 review · 0 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Cartesian products of cycle powers with regular graphs, average hitting times between same-coordinate vertices are governed by ratio-symmetric products $V_\ell V_{N-\ell}/V_N$ of second-order linear recurrences.

desk verdict A correct, self-contained extension of the authors' cycle-power hitting-time work to Cartesian products with regular graphs; the main formula is actually unconditional because the root-simplicity assumption is automatic. read the letter →

arxiv 2608.11734 v1 pith:RPLYQWRW submitted 2026-08-12 math.CO

Tsuyoshi Miezaki , Shunya Tamura This is my paper · ORCID

classification math.CO MSC 05C8105C5060J10

keywords averagehittingtimesimplerandomwalkCartesianproductgraphcyclepowerChebyshevpolynomialsecond-orderlinearrecurrenceLaplacianspectrumwalk-regular

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that the ratio-style recurrence structure previously found for average hitting times on the $k$-th power of a cycle survives when that graph is combined with any connected regular graph $G$ via the Cartesian product. For two vertices sharing the same $G$-coordinate, the expected hitting time on $C_N^k \square G$ is the cycle hitting time plus a weighted sum of correction terms, each shaped like $V_\ell V_{N-\ell}/V_N$ for a second-order linear recurrence sequence. The terms are indexed by the distinct nonzero Laplacian eigenvalues of $G$, and in the walk-regular case they depend only on those eigenvalues and their multiplicities. The paper also derives matching product formulas for spanning trees and two-component spanning forests, so the recurrence structure propagates from hitting times into combinatorial invariants.

What carries the argument

The central object is the Chebyshev-type polynomial $D_{k,\nu}(x)=k+\nu/2-\sum_{s=1}^k T_s(x/2)$, whose roots $\phi_{\alpha,c}$ appear in a partial-fraction decomposition of $1/D_{k,\nu}$. Each root is paired with a sequence $V_n^{(\alpha,c)}$ solving $V_{n+2}=\gamma_{\alpha,c}V_{n+1}-V_n$, where $\gamma_{\alpha,c}$ satisfies $\gamma_{\alpha,c}^2=\phi_{\alpha,c}+2$; the hitting-time correction is assembled from products $V_\ell V_{N-\ell}/V_N$. The partial-fraction step converts Fourier sums over $N$ frequencies into finite algebraic data coming from the nonzero Laplacian eigenspaces of $G$. A second object, the spectral projection $E_\alpha(a,a)$, controls the weight of each eigenspace, and walk-regularity collapses it to $m_\alpha/m$.

What would settle it

To test the key assumption, fix small $k$ and positive integer $\nu$, form $D_{k,\nu}(x)=k+\nu/2-\sum_{s=1}^k T_s(x/2)$, and compute $\gcd(D_{k,\nu}, D'_{k,\nu})$; a nonconstant gcd would exhibit a repeated root and break the simple partial fraction on which Theorem 4.10 rests. To test the formula itself, evaluate both sides of Theorem 4.10 for a small case such as $N=5$, $k=2$, $G=K_3$ and compare with the finite spectral sum in Proposition 2.2; any disagreement would falsify the claimed identity.

Watch

Extended reading notes

Core claim

The central claim is that for a connected $r$-regular graph $G$ on $m$ vertices, the average hitting time from $(0,a)$ to $(\ell,a)$ in $X=C_N^k\square G$ equals $$\frac{2k+r}{2k}h_{C_N^k}(0,\ell)-\frac{Nm(2k+r)}{2}\sum_{\$\alpha$=1}^t E_\$\alpha$(a,a)\sum_{c=1}^k \frac{1}{\gamma_{\$\alpha$,c}D'_{k,\nu_\$\alpha$}(\phi_{\$\alpha$,c})}\frac{$V^{{(\alpha,c)}}$_\ell $V^{{(\alpha,c)}}$_{N-\ell}}{$V^{{(\alpha,c)}}$_N},$$ provided every root of the Chebyshev-type polynomial $D_{k,\nu}(x)=k+\nu/2-\sum_{s=1}^k T_s(x/2)$ is simple for each nonzero Laplacian eigenvalue $\nu$ of $G$. The proof passes through a finite Green-type sum and then rewrites each term using sequences $V_n^{(\alpha,c)}$ defined by $V_0=0$, $V_1=1$, and $V_{n+2}=\gamma_{\alpha,c}V_{n+1}-V_n$. For walk-regular $G$, the projection $E_\alpha(a,a)$ reduces to $m_\alpha/m$, so the formula becomes purely spectral, involving only Laplacian eigenvalues and their multiplicities. As corollaries, the paper obtains a factorization for the spanning-tree count of $X$ and, through the commute-time identity, a two-component-forest count with the same recurrence shape.

Load-bearing premise

The load-bearing premise is that every Chebyshev-type polynomial $D_{k,\nu}$ has only simple roots for each distinct nonzero Laplacian eigenvalue of $G$; if a double root appears, the clean product form is not established.

Editorial extensions

If this is right

For any connected regular $G$ satisfying the simplicity condition, the same-coordinate average hitting time is a sum of the cycle-power term and a finite number of ratio products $V_\ell V_{N-\ell}/V_N$ from explicitly computable linear recurrences.
When $G$ is walk-regular, the vertex-dependent projection $E_\alpha(a,a)$ collapses to $m_\alpha/m$, so the formula depends only on the Laplacian spectrum and multiplicities of $G$.
The spanning-tree count of $C_N^k\square G$ factors into $\tau(C_N^k)\tau(G)$ times a product over $\kappa_j+\nu_\alpha$, and this factorization does not need the root-simplicity assumption.
The number of two-component spanning forests separating same-coordinate vertices inherits the same $V_\ell V_{N-\ell}/V_N$ recurrence structure.
For complete graphs, complete bipartite graphs, and the Petersen graph, the paper's examples give fully explicit closed forms; in particular, each nonzero Laplacian eigenvalue supplies one recurrence with parameter $\sqrt{\nu+4}$ when $k=1$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The simplicity condition on the roots of $D_{k,\nu}$ looks like a generic property, and computing its discriminant over integer $\nu$ would reveal exactly which pairs $(k,\nu)$ force higher-order partial fractions; the paper leaves this characterization open.
Because $V_{n+2}=\gamma V_{n+1}-V_n$ is the same recurrence that defines Chebyshev polynomials, the correction terms can be re-read as evaluations of Chebyshev polynomials at $\gamma$, which may connect the formula to transfer-matrix or continued-fraction treatments of hitting times.
A parallel decomposition should be possible when $C_N^k$ is replaced by any circulant or Cayley graph whose Fourier spectrum is known, so the principle that one-dimensional recurrence structures transfer to Cartesian products may be general.
For nonregular $G$, the uniform stationary distribution fails, but a normalized-Laplacian version of the same partial-fraction argument seems plausible; the paper itself identifies nonregular factors as a future problem.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

I read this carefully, and my verdict is positive. The paper does what it says: it extends the second-order recurrence structure found for average hitting times on C_N^k to Cartesian products C_N^k □ G for any connected regular G. The main new content is the Chebyshev-type polynomial D_{k,nu}, the partial-fraction step turning spectral sums into Green terms, and the reduction of the same-coordinate case to V_l V_{N-l}/V_N. Those are real, explicit formulas that were not in Ellis's general framework or in the authors' earlier paper. The walk-regular specialization and the spanning-tree/forest corollaries are useful bonuses.

I checked the mathematics. The spectral decomposition in Proposition 2.2 is standard and correctly executed. The partial-fraction and recurrence algebra in Section 4 is sound; I would have liked a few more steps in Proposition 4.9, but the identity checks out. The examples for K_m, K_{s,s}, and the Petersen graph are consistent. The paper is also honest: it re-proves the base case from the previous paper, so there is no circularity, and no parameter is fitted to anything.

One point that surprised me: the root-simplicity assumption in Theorem 4.10 is not actually a restriction. Using the identity sum_{s=1}^k T_s(y) = (U_k(y)+U_{k-1}(y)-1)/2, the zeros of the derivative of D_{k,nu} are exactly the k-1 zeros of (U_k+U_{k-1})' in (-1,1), and Lemma 4.2 already tells us D_{k,nu}>0 on [-2,2]. So every critical point has positive D-value, which means no repeated root can exist. Theorem 4.10 holds unconditionally for every nu>0. The authors could drop the assumption and simplify the presentation.

The soft spots are mostly matters of scope. The paper is incremental rather than groundbreaking; it does not resolve a long-open question or introduce a new technique, though the technique is applied cleanly. The formulas for different G-coordinates remain Green sums, not the neat V_l V_{N-l}/V_N form, which is fine but limits the elegance. The introduction is a bit heavy on notation, and the conclusion is modest. None of this is a real flaw.

Who is this for? Spectral graph theorists and anyone working on random walks on product graphs will find the exact formulas useful and likely citable. The paper deserves a serious referee and, in my view, acceptance after light revision. I would cite it.

Referee Report

0 major / 4 minor

Summary. The manuscript studies average hitting times of the simple random walk on the Cartesian product C_N^k \square G, where C_N^k is the k-th power of an N-cycle and G is a connected r-regular graph on m vertices. The authors use discrete Fourier analysis in the cycle direction and the Laplacian spectral decomposition of G to split the average hitting time into a term proportional to h_{C_N^k}(0,\ell) plus correction terms indexed by the nonzero Laplacian eigenvalues of G. For each such eigenvalue \nu they introduce the Chebyshev-type polynomial D_{k,\nu}(x), and under a simplicity assumption on its roots they convert each correction term into a finite Green-type sum and then, for pairs of vertices with the same G-coordinate, into a product V_\ell V_{N-\ell}/V_N of a second-order linear recurrence sequence. They also derive spanning-tree and two-component-forest formulas, specialize to walk-regular graphs, and work out examples for complete graphs, complete bipartite graphs, and the Petersen graph.

Significance. The result is a genuine and clean extension of the recurrence-structure picture developed for powers of cycles in the authors' companion paper. The main formula in Theorem 4.10 is explicit, falsifiable, and reduces correctly to the base case when G is a single vertex; the spanning-tree and forest formulas are useful by-products. The paper is essentially self-contained: the base result for C_N^k is re-proved, the spectral decomposition is standard and carefully set up, and the examples provide nontrivial checks. The only assumption that the reader flagged, simplicity of the roots of D_{k,\nu}, is in fact automatic for every \nu>0, so the main theorem is stronger than stated. The manuscript is a solid contribution to the spectral theory of random walks on Cartesian products of regular graphs.

minor comments (4)

[Section 4.1, Remark 4.1 and Theorem 4.10] The simplicity assumption on the roots of D_{k,\nu} is not a genuine restriction and should be removed. Writing y=x/2 and using sum_{s=1}^k T_s(y)=(U_k(y)+U_{k-1}(y)-1)/2, one obtains 2D_{k,\nu}(x)=2k+1+\nu-(U_k(x/2)+U_{k-1}(x/2)). The polynomial U_k+U_{k-1} has k simple zeros in (-1,1), so by Rolle's theorem all k-1 critical points of this degree-k polynomial lie in (-1,1); hence all critical points of D_{k,\nu} lie in (-2,2). Lemma 4.2 shows D_{k,\nu}>0 on [-2,2], so no root can be critical. Thus every root of D_{k,\nu} is simple, and Theorem 4.10, Corollary 4.15, and the examples can be stated unconditionally. I recommend adding this short argument and amending the wording of Remark 4.1 accordingly.
[Corollary 5.5] The displayed factor '2N' should be '2^N'. As printed, the expression appears as 2N\prod D_{k,\nu_\alpha}(2\cos\theta_j), whereas the derivation from 2D_{k,\nu}(2\cos\theta_j)=\kappa_j+\nu gives a factor 2^N for each nonzero eigenvalue; please correct the typo.
[Lemma 2.1 and Proposition 2.2] The spectral formula in Lemma 2.1 is written without complex conjugation: the numerator should be |\psi_q(v)|^2 - \psi_q(u)\overline{\psi_q(v)}. The use of e^{-i\ell\theta_j} later in Proposition 2.2 shows that the intended formula is the conjugate version, but stating it explicitly would remove ambiguity for readers following the complex Fourier basis computation.
[Section 6, examples] After the automatic-simplicity observation is added, the hypotheses 'assume that all roots of D_{k,m}(x) are simple' in Propositions 6.5, 6.7, and Corollaries 6.8 and 6.9 can be deleted; keeping them is harmless but suggests a limitation that does not exist.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main formula is derived from standard spectral decomposition and partial fractions; the only self-citation is to the re-proved base case.

full rationale

The paper's central result (Theorem 4.10) is obtained by (i) the spectral formula in Proposition 2.2, whose proof is given; (ii) the base-case formula h_{C_N^k}(0,ell), which is cited to the authors' earlier work [9] but re-proved in Proposition 3.1; (iii) an algebraic partial fraction decomposition of the Chebyshev-type polynomial D_{k,nu}; and (iv) the explicit identities in Lemma 4.4 and Proposition 4.9 that transform Green sums into V_ell V_{N-ell}/V_N. No parameter is fitted to data, and no previously published uniqueness theorem is invoked to force the form of the result. The citation to [9] is not load-bearing because the needed base-case statement is independently derived in this paper. The simplicity-of-roots assumption in Theorem 4.10 is a stated hypothesis, and Remark 4.1 explicitly notes that analogous formulas hold without it; it is therefore a condition, not a circular input. The product representation is derived, not assumed, and the spanning tree and two-component spanning forest formulas use standard Matrix-Tree and Matrix-Forest theorems with the same spectral data. No step in the derivation reduces by definition or by self-citation to its own conclusion.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard spectral and matrix-tree theorems plus the explicitly stated root-simplicity condition. No free parameters are fitted: the quantities phi, rho, eta, gamma, and V_n are all derived algebraically from the Laplacian eigenvalues of G. No new entities are postulated.

assumptions (5)

standard math Spectral theorem for real symmetric matrices and existence of orthonormal eigenbases
Used in Lemma 2.1 and Proposition 2.2 to diagonalize the transition matrix of the product graph and to express spectral projections E_alpha.
standard math Discrete Fourier basis diagonalizes the circulant adjacency matrix of C_N^k
Section 2.3; gives the eigenvalues mu_j = 2 sum_{s=1}^k cos(s theta_j) used throughout.
standard math Matrix-Tree theorem, Matrix-Forest theorem, and commute-time identity
Theorems 5.1, 5.2, 5.3; used to connect spanning tree and forest counts to Laplacian eigenvalues and hitting times.
domain assumption G is a connected r-regular graph on m vertices and N >= 2k+1
Introduction and Section 2.1; ensures C_N^k is 2k-regular and the Cartesian product is regular and connected.
ad hoc to paper All roots of D_{k,nu_alpha}(x) are simple for each nonzero Laplacian eigenvalue nu_alpha of G
Section 4.1, used in Proposition 4.3 and Theorem 4.10; required for the simple partial fraction expansion, not characterized in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs." pith.science (2026). https://pith.science/paper/RPLYQWRW

@misc{pith2026260811734,
  author       = {Pith},
  title        = {Pith review of: Average hitting times and recurrence structures II: Cartesian products of powers of cycles and regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RPLYQWRW}},
  note         = {Machine review of arXiv:2608.11734}
}

abstract

In our previous work \cite{MiezakiTamura2026}, we clarified the second-order linear recurrence structures appearing in the average hitting times on the $k$-th power graph $C_N^k$ of the cycle graph. In this paper, for a connected $r$-regular graph $G$ on $m$ vertices, we investigate the average hitting times of the simple random walk on the Cartesian product graph $C_N^k \square G$. By using discrete Fourier analysis in the $C_N^k$ direction and the Laplacian spectral decomposition of $G$, we decompose the average hitting time into a component proportional to the average hitting time on $C_N^k$ and correction terms arising from the nonzero Laplacian eigenspaces of $G$. For each nonzero Laplacian eigenvalue, we introduce a Chebyshev-type polynomial, and when all of its roots are simple, we express the correction term as a finite Green-type sum. Furthermore, for two vertices having the same $G$-coordinate, we transform this expression into a second-order linear recurrence representation of the form $V_\ell V_{N-\ell}/V_N$. When $G$ is a walk-regular graph, the average hitting time between two vertices having the same $G$-coordinate depends only on the Laplacian eigenvalues of $G$ and their multiplicities. We also derive formulas for the number of spanning trees and the number of two-component spanning forests of $C_N^k \square G$, and give several explicit examples.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 5 canonical work pages

[1]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012
[2]

Chebotarev and E

P. Chebotarev and E. Shamis, The matrix-forest theorem and measuring relations in small social groups,Autom. Remote Control58(1997), 1505–1514

1997
[3]

Y. Doi, N. Konno, T. Nakamigawa, T. Sakuma, E. Segawa, H. Shinohara, S. Tamura, Y. Tanaka, and K. Toyota, On the average hitting times of the squares of cycles, Discrete Appl. Math.313(2022), 18–28

2022
[4]

R. B. Ellis, Discrete Green’s functions for products of regular graphs, arXiv:math/0309080, 2003

arXiv 2003
[5]

On walk-regular graphs and graphs with symmetric hitting times

A. Georgakopoulos, On walk-regular graphs and graphs with symmetric hitting times, arXiv:1211.5689, 2012

work page Pith review arXiv 2012
[6]

C. D. Godsil and B. D. McKay, Feasibility conditions for the existence of walk-regular graphs,Linear Algebra Appl.30(1980), 51–61

work page 1980
[7]

Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann

G. Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann. Phys. Chem. 72(1847), 497–508
[8]

Lov´ asz, Random walks on graphs: a survey, in:Combinatorics, Paul Erd˝ os is Eighty, Vol

L. Lov´ asz, Random walks on graphs: a survey, in:Combinatorics, Paul Erd˝ os is Eighty, Vol. 2, Bolyai Society Mathematical Studies, Vol. 2, J´ anos Bolyai Mathemat- ical Society, Budapest, 1993, pp. 1–46

work page 1993

Show all 12 references

[9]

Miezaki and S

T. Miezaki and S. Tamura, Average hitting times and recurrence structures I: powers of cycle graphs, arXiv:2605.09229v2, 2026

2026 arXiv
[10]

C. St. J. A. Nash-Williams, Random walk and electric currents in networks,Proc. Cambridge Philos. Soc.55(1959), 181–194

1959
[11]

S. Tamura, Effective resistance and spanning trees in complete graphs with distance- class deletions,Journal of Combinatorial Mathematics and Combinatorial Computing 130(2026), 279–300

2026
[12]

F. Y. Wu, Theory of resistor networks: the two-point resistance,J. Phys. A37(2004), 6653–6673. F aculty of Science and Engineering, W aseda University, Tokyo 169–8555, Japan Email address:miezaki@waseda.jp Okegawa City Okegawa West Junior High School, Saitama, 363-0027, Japan ...

2004

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Universitext, Springer, New York, 2012

2012

[2] [2]

Chebotarev and E

P. Chebotarev and E. Shamis, The matrix-forest theorem and measuring relations in small social groups,Autom. Remote Control58(1997), 1505–1514

1997

[3] [3]

Y. Doi, N. Konno, T. Nakamigawa, T. Sakuma, E. Segawa, H. Shinohara, S. Tamura, Y. Tanaka, and K. Toyota, On the average hitting times of the squares of cycles, Discrete Appl. Math.313(2022), 18–28

2022

[4] [4]

R. B. Ellis, Discrete Green’s functions for products of regular graphs, arXiv:math/0309080, 2003

arXiv 2003

[5] [5]

On walk-regular graphs and graphs with symmetric hitting times

A. Georgakopoulos, On walk-regular graphs and graphs with symmetric hitting times, arXiv:1211.5689, 2012

work page Pith review arXiv 2012

[6] [6]

C. D. Godsil and B. D. McKay, Feasibility conditions for the existence of walk-regular graphs,Linear Algebra Appl.30(1980), 51–61

work page 1980

[7] [7]

Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann

G. Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann. Phys. Chem. 72(1847), 497–508

[8] [8]

Lov´ asz, Random walks on graphs: a survey, in:Combinatorics, Paul Erd˝ os is Eighty, Vol

L. Lov´ asz, Random walks on graphs: a survey, in:Combinatorics, Paul Erd˝ os is Eighty, Vol. 2, Bolyai Society Mathematical Studies, Vol. 2, J´ anos Bolyai Mathemat- ical Society, Budapest, 1993, pp. 1–46

work page 1993