{"id":"0b340fc7-6c69-43ae-92af-a53caa078720","arxiv_id":"2608.11734","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Average hitting times on Cartesian products of cycle powers and regular graphs decompose into a cycle component plus correction terms expressible as ratios of second-order linear recurrence sequences.","lead":"This paper derives exact formulas for the average time a random walk takes to reach a chosen vertex on a family of product graphs built from cycle graphs and regular graphs. The formulas show a Fibonacci-like recurrence pattern and also give formulas for the number of spanning trees and two-component forests.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the root-simplicity condition in Theorem 4.10 is in fact automatically satisfied, so the conditional statement is correct and even stronger than stated.","rationale":"The reader's acceptance is well founded. I independently traced Proposition 2.2 through Corollary 3.4, Proposition 4.6, Proposition 4.9, and Theorem 4.10; the constant-component reduction and the correction-term algebra are consistent, and the final product representation V_l V_{N-l}/V_N follows from the stated partial-fraction expansion. The only assumption that could threaten the central claim is the simplicity of the roots of D_{k,nu}, and the reader correctly identified it as the weakest point. However, on inspection this assumption is automatically satisfied: the derivative of D_{k,nu} has all its zeros in (-2,2), while D_{k,nu} is strictly positive on that interval. Thus Theorem 4.10 holds unconditionally for every connected regular graph G and every positive Laplacian eigenvalue nu. The paper's Remark 4.1 about higher-order partial fractions is therefore unnecessary in this setting, though not incorrect. Because the central claim survives scrutiny and is in fact stronger than stated, the verdict should remain unchanged.","tokens_in":18372,"tokens_out":25143,"duration_ms":253495,"concrete_test":"Insert a short lemma: derive D_{k,nu} in terms of U_k and U_{k-1}, locate the k simple zeros of U_k + U_{k-1} in (-1,1) via the trigonometric identity, apply Rolle to conclude all zeros of D'_{k,nu} lie in (-2,2), and invoke Lemma 4.2 to rule them out as roots of D_{k,nu}. If this lemma is added, remove the simplicity hypothesis from Theorem 4.10, Corollary 4.15, and the example propositions; no numerical counterexample should exist.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The only candidate weak point is the simplicity of the roots of the Chebyshev-type polynomial D_{k,nu}, exactly as the reader flagged. This condition is not actually load-bearing because it holds automatically for every nu > 0. Writing y = x/2 and using the identity sum_{s=1}^k T_s(y) = (U_k(y) + U_{k-1}(y) - 1)/2, we have 2 D_{k,nu}(x) = 2k + 1 + nu - U_k(y) - U_{k-1}(y). The polynomial U_k + U_{k-1} has k simple zeros in (-1,1), since U_k(cos theta) + U_{k-1}(cos theta) = 2 sin((2k+1)theta/2) cos(theta/2)/sin(theta). By Rolle's theorem its derivative has all k-1 zeros in (-1,1), so all critical points of D_{k,nu} lie in (-2,2). Lemma 4.2 shows D_{k,nu} > 0 on [-2,2], so no critical point is a root. Hence every root of D_{k,nu} is simple, and Theorem 4.10 is in fact unconditional. No other gap surfaced in the spectral decomposition, partial-fraction transformation, or recurrence algebra.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18692,"tokens_out":17540,"duration_ms":170780,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 4.1, Remark 4.1 and Theorem 4.10"},{"comment":"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.","section":"Corollary 5.5"},{"comment":"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":"Lemma 2.1 and Proposition 2.2"},{"comment":"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.","section":"Section 6, examples"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a carefully written, essentially correct extension of the authors' companion work. The one concern raised in the referee process, the root-simplicity condition in Theorem 4.10, does not land: the condition is automatically satisfied for every positive Laplacian eigenvalue, so the theorem is actually unconditional. The requested changes are local (a short proof, a typesetting fix, and clarification of the complex-conjugate convention). No concerns about attribution or scope; the self-citation to [9] is appropriate because the base result is independently re-proved here."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nI 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.\n\nOne 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":19148,"tokens_out":3307,"would_cite":true,"duration_ms":33109,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C81","05C50","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["average hitting time","simple random walk","Cartesian product graph","cycle power graph","Chebyshev polynomial","second-order linear recurrence","Laplacian spectrum","walk-regular graph"],"falsifier":"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.","tokens_in":18206,"feed_emoji":"🔁","tokens_out":8532,"duration_ms":84287,"temperature":0.7,"pith_summary":"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.","feed_headline":"Cycle-power hitting-time recurrence survives graph products","feed_subtitle":"For regular G, the same-coordinate formula is determined by Laplacian eigenvalues and multiplicities.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Establishes the Fibonacci-type product representation for $C_N^k$ that Theorem 4.10 generalizes to products with regular graphs.","marker":"[9]"},{"why":"Supplies the spectral formula for average hitting times on regular graphs used as Lemma 2.1.","marker":"[8]"},{"why":"Provides the general Green-function framework for Cartesian products of regular graphs on which the decomposition is built.","marker":"[4]"},{"why":"Gives the walk-regularity criterion $E_\\alpha(a,a)=m_\\alpha/m$ used to make the formula spectral.","marker":"[6]"},{"why":"Commute-time identity connecting hitting times and effective resistance, used for two-component forest counts.","marker":"[10]"},{"why":"Matrix-Tree theorem used to derive the spanning-tree product formula.","marker":"[7]"},{"why":"Matrix-forest theorem relating two-component spanning forests to effective resistance.","marker":"[2]"}],"fun_headline_variants":["Hitting time recurrence extends to cycle-power times regular graph","Product hitting times: cycle part plus Laplacian corrections","Walk-regular graphs: hitting time depends only on spectrum","Recurrence structure in hitting times on Cartesian products","Spanning tree and forest counts from hitting time decomposition"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Hitting time recurrence extends to cycle-power times regular graph","Product hitting times: cycle part plus Laplacian corrections","Walk-regular graphs: hitting time depends only on spectrum","Recurrence structure in hitting times on Cartesian products","Spanning tree and forest counts from hitting time decomposition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000847,"raw_usage":{"total_tokens":3799,"prompt_tokens":1169,"completion_tokens":2630,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":2551}},"tokens_in":785,"tokens_out":2630,"duration_ms":21235,"temperature":1.0,"reasoning_tokens":2551,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:29:16.945429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Lov´ asz, Random walks on graphs: a survey, in:Combinatorics, Paul Erd˝ os is Eighty, Vol","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral formula for average hitting times on regular graphs used as Lemma 2.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the walk-regularity criterion $E_\\alpha(a,a)=m_\\alpha/m$ used to make the formula spectral."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Commute-time identity connecting hitting times and effective resistance, used for two-component forest counts."}],"review_version":1}