{"id":"7b977948-d042-460c-afbf-1ce99a8a03f1","arxiv_id":"2502.07496","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new temporal graph model from word-representable graphs is introduced with claimed 2δn and 2dn exploration bounds, but a key lemma (Lemma 7) is false, invalidating the general upper bound.","lead":"The paper defines word-representable temporal graphs, where each timestep is a segment of a word, and proves upper and lower bounds for exploring all vertices with one agent. The main general upper bound relies on a false lemma about occurrence positions, so the proofs do not yet establish the claims.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7 is false on the paper's own n=4 path word, and Theorem 11's upper bound depends on it; the main 2dn exploration claim is unproven.","rationale":"The reader's identified weakest assumption is the one I would also single out. The general upper-bound part of the paper is the central claimed contribution, and its proof is a chain ending in Theorem 11. The key edge-recurrence lemma (Lemma 9) is justified only by Lemma 7, which is demonstrably false on a four-vertex instance built by the paper's own path construction. This is not a matter of disagreement with standard results; it is an internal counterexample. An independent re-derivation of Lemma 9 might exist, but the manuscript does not provide one, so the theorem is unsupported as written. I see no reason to soften the reader's rejection. I also note a secondary gap: the lower-bound words have length O(n^2), below the n(2dn+d) threshold required by Theorem 11 for d near n, so even with a repaired upper bound the claimed asymptotic optimality would need an additional padding or averaging argument. The false Lemma 7 is the more load-bearing issue.","tokens_in":14259,"tokens_out":14834,"duration_ms":134904,"concrete_test":"Run the following exact verification. For the n=4 word w=12132434 from Section 4.1, compute the word-representable graph G(w), the distance matrix, and the occurrence lists of all symbols. For the pair (1,4) this gives Dist=3, χ_1=1, γ_1=6, χ_2=3, γ_2=8, both violating the bound in Lemma 7. Then trace the proof of Lemma 9 on this word and confirm that the contradiction it derives depends on the same-index occurrence alignment of Lemma 7; the counterexample is decisive because it is drawn from the paper's own construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 7 states that if Dist(v_x,v_y)=d, then the i-th occurrence positions satisfy χ_i − d ≤ γ_i ≤ χ_i + d. The paper's path construction (Section 4.1) for n=4 gives w=12132434. The word-representable graph has exactly the path edges (1,2),(2,3),(3,4), so Dist(1,4)=3. The first occurrence of 1 is at χ_1=1 and the first occurrence of 4 is at γ_1=6; 6 > 1+3. The second occurrences are 3 and 8, and 8 > 3+3. Thus Lemma 7 is false, not a matter of a missing constant. Lemma 9's proof uses Lemma 7 explicitly ('by Lemma 7, we have a contradiction'), and Lemma 9 plus Corollary 10 are exactly what Theorem 11 uses to bound the waiting time at each vertex by d. Since the only supplied proof of the waiting bound is invalid, the central 2dn upper bound is not established by the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces word-representable temporal graphs by partitioning a word representing a graph into factors with no repeated symbols, and declares an edge active in a timestep if at least one of its endpoints appears in the corresponding factor. The main claimed results are: (i) every always-connected word-representable temporal graph can be explored in 2δn timesteps, where δ is the minimum degree of the underlying graph (Theorem 4); (ii) if the representing word has length at least n(2dn+d) and the underlying graph has diameter d, the graph can be explored in 2dn timesteps (Theorem 11); and (iii) a lower-bound construction requiring Ω(dn) timesteps, which would make the bound asymptotically tight (Theorem 22). The paper is self-contained and proposes a genuinely new temporal graph model, but the central proofs contain serious gaps, including a false lemma on occurrence positions.","tokens_in":14384,"tokens_out":14186,"duration_ms":137533,"significance":"If the results were correct, the paper would contribute a new class of temporal graphs with a compact word representation and tight single-agent exploration bounds, complementing the existing literature on always-connected temporal graphs. The model is cleanly defined and the lower-bound construction is an interesting attempt to match the upper bound. However, the main theorems are not established by the arguments given: the always-connected result rests on an invalid inference in Lemma 3, and the general upper bound rests on Lemma 7, which is false on the paper's own path example. Because these are load-bearing errors in the central claims, the current manuscript cannot be accepted or recommended for minor revision.","major_comments":[{"comment":"The proof of Lemma 3 incorrectly strengthens the consequence of Corollary 2. Corollary 2 only says that the edge (vx,vy) is active in at least one timestep in a window of length min(d(vx),d(vy))+1. By the definition of Et in Section 2, an edge is active when the factor contains at least one of its endpoints, so the union of the factor alphabets over the window is only guaranteed to contain x or y, not necessarily both. The proof nevertheless states 'Therefore, x,y ∈ alph(w[St,...])', which is exactly the simultaneous-occurrence property needed to propagate degree bounds through neighbours. Since Theorem 4's waiting argument uses Lemma 3 to bound the delay at every vertex by δ, the always-connected 2δn upper bound is not established as written.","section":"Section 3, Lemma 3 and Theorem 4"},{"comment":"Lemma 7 is false. The path construction of Section 4.1 with n=4 gives w=12132434, whose represented graph has edges (1,2), (2,3), and (3,4), so Dist(1,4)=3. The first occurrence of 1 is at position 1 and the first occurrence of 4 is at position 6, but the lemma requires γ_1 ≤ χ_1 + d = 4. The second occurrences are at positions 3 and 8, again violating γ_2 ≤ χ_2 + d = 6. Thus the claimed relation between occurrence indices of vertices at distance d is not merely unproved; it fails on the paper's own construction. Since Lemma 9 explicitly invokes Lemma 7 and Corollary 10 and Theorem 11 inherit that dependence, the general 2dn upper bound is unsupported.","section":"Section 4, Lemma 7"},{"comment":"Independently of the falsity of Lemma 7, the proof of Lemma 9 contains an unjustified step: after assuming that the edge (vx,vy) is absent for d consecutive timesteps, it asserts that 'there must exist some symbol z such that |π{z}(w[St,St+d+1−1])| = d'. No argument is given that a single symbol must appear in each of those timestep factors, and the definition of timestep factors does not force consecutive factor alphabets to intersect. Consequently, even replacing Lemma 7 by a correct statement would not make the proof of Lemma 9 complete as written.","section":"Section 4, Lemma 9"},{"comment":"The lower-bound construction is incompletely specified: in the definition of the word v, the factors u2 and u3 are written as 'u2 = 0(1,2)(2,2)...' and 'u3 = 0(...)', where 0 is not a vertex symbol of the alphabet Σ = {(i,j)}. The paper's model in Section 2 defines words over the vertex alphabet only, so a separator symbol outside the alphabet is not admitted, and treating 0 as an ordinary letter would change the active-edge condition. The construction therefore needs a formal definition of the intended alphabet and the role of this symbol before Theorem 22 can be verified.","section":"Section 4.1, Theorem 22 construction"}],"minor_comments":[{"comment":"The statement of Lemma 6 contains a self-referential typo: it compares |π{x}(w)| with itself instead of comparing |π{x}(w)| with |π{y}(w)|. The proof has a similar garbled inequality, though the intended triangle-inequality argument for the number of occurrences is clear.","section":"Section 4, Lemma 6"},{"comment":"Theorem 17 states that the constructed word has length 4n^2, but the construction uses w^n where w has length 2n, giving length 2n^2. In the proof, sums such as Σ_{i∈[1,n/3]} ⌊2n−5⌋/4−3 are missing parentheses around the summand, making the displayed algebra ambiguous.","section":"Section 4.1, Theorem 17"},{"comment":"The displayed formula in Observation 12 conditions on the parity of k, the repetition count, where the intended condition appears to be the parity of the local index ℓ; as printed the formula is difficult to parse and should be rewritten.","section":"Section 4.1, Observation 12"},{"comment":"There are numerous notation and typesetting errors, for example '(vx,vy) /∈ T′t' in Lemma 9 should presumably be '(vx,vy) ∉ Et′', and the bibliography contains the placeholder venue 'CVIT 2016'. These need correction in any revision.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The paper proposes an appealing model and the lower-bound idea is worth preserving, but the main upper-bound proofs are not merely missing details: Lemma 7 is false on the paper's own example, and Lemma 3's proof makes an invalid inference from the active-edge definition. Because Theorem 4 and Theorem 11 both depend on these points, the central claims are unproven in the submitted version. I would be willing to look at a substantially revised manuscript with corrected proofs or appropriately weakened claims, but in its current form the paper does not meet the bar for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces word-representable temporal graphs, a new model that is a natural synthesis of word-representable graph theory and temporal graph exploration. The definitions are clean, the examples are helpful, and the idea of bounding exploration time via occurrence positions in the representing word is genuinely interesting. The always-connected section (2δn bound) is a plausible extension of known spanning-tree-with-waiting techniques, though Lemma 3's proof has a real gap: edge activity only requires one endpoint to appear in the factor, not both, so the propagation argument is not justified as written.\n\nThe general upper bound, however, is not just missing a detail—it rests on a false lemma. Lemma 7 claims that if Dist(vx, vy) = d, the i-th occurrence positions of x and y differ by at most d. The paper's own n=4 path construction gives w = 12132434, where vertices 1 and 4 are at distance 3, but their first occurrences are at positions 1 and 6, and 6 > 1+3. So Lemma 7 is simply false, and no missing constant saves it. Lemma 9 explicitly uses Lemma 7 to derive the waiting-time bound, and Corollary 10 and Theorem 11 depend on Lemma 9. That means the main 2dn upper bound is unproven in this manuscript. The lower-bound section is also sketchy: Theorem 17's summation has a missing parenthesis and the argument is informal, and Theorem 22 is too terse to verify the claimed Ω(dn) bound for all d in [1, n].\n\nThe paper is not written in bad faith; it is a genuine attempt at a new model, and the proof errors are internal logical gaps rather than circular reasoning or overclaiming of prior work. The citation pattern is appropriate and the related work is relevant. But the central theorem is currently unsupported.\n\nWho gets value from this? Someone working on temporal graph exploration or word-representable graphs might find the model worth thinking about, and the false lemma is instructive as a caution about mixing occurrence positions and graph distances. I would not cite the 2dn result in its current form. However, the model itself and the always-connected question may be salvageable, so I would send this to a serious referee rather than desk-reject—ideally with the expectation of major revision and a corrected or weakened main theorem.","headline":"New model, flawed proof: the paper's central 2dn exploration bound rests on Lemma 7, which is false on the paper's own path construction.","tokens_in":14923,"tokens_out":1581,"would_cite":false,"duration_ms":15314,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"A word-representable temporal graph can be explored in at most 2dn timesteps, and this is asymptotically optimal.","keywords":["temporal graphs","word-representable graphs","graph exploration","alternating words","diameter","lower bounds"],"falsifier":"Check Lemma 7 on the paper's own path construction for n=4, whose word is 1 2 1 3 2 4 3 4: vertices 1 and 4 are at distance 3 in the underlying path, yet the first occurrence of 1 is at position 1 and the first occurrence of 4 is at position 6, so the position difference (5) exceeds d=3. If this single check confirms the violation, the lemma is false and the general upper-bound argument is unsupported.","tokens_in":13958,"feed_emoji":"🧭","tokens_out":8615,"duration_ms":77426,"temperature":0.7,"pith_summary":"This paper introduces word-representable temporal graphs, where a single word over the vertex alphabet is cut into contiguous factors, each factor is a timestep, and an edge is active at that timestep whenever either endpoint appears in the factor. The paper studies how fast a single agent can visit every vertex by moving along edges that are active in successive timesteps. It presents two upper bounds: when the underlying graph is connected and has diameter d, graphs whose representing word is at least n(2dn+d) symbols long are explorable in at most 2dn timesteps; and when every timestep is itself connected, exploration takes at most 2δn timesteps, where δ is the minimum degree. It also constructs, for every n and d, a word-representable temporal graph with n vertices and diameter d that needs Ω(dn) timesteps, which would make the 2dn bound asymptotically optimal. The general upper bound rests on a structural lemma about how close the k-th occurrences of distance-d vertices must lie in the word.","feed_headline":"Word-representable temporal graphs explore in at most 2dn steps","feed_subtitle":"A single word encodes all timesteps; exploration time scales with diameter times vertex count.","key_machinery":"The central object is the word representation itself: a word w over the vertex alphabet is parcelled into timestep factors, each containing no repeated symbol, and an edge between two vertices is present in a timestep if and only if one of its endpoints occurs in that factor. The argument's engine is the occurrence-proximity lemma (Lemma 7), which asserts that for any two vertices at graph distance d, the index of the i-th occurrence of one vertex differs from that of the other by at most d. From this lemma the paper derives the bounded-dormancy corollary that no edge can be inactive for more than d consecutive timesteps, which in turn justifies the waiting-time analysis of the exploration walk.","core_discovery":"The central discovery is that word-representable temporal graphs have a built-in bounded-dormancy property: once an edge appears in a timestep, it must reappear within a fixed window of consecutive timesteps. The proof of the main upper bound, Theorem 11, uses a spanning tree of the underlying graph and traverses it edge by edge, waiting at each vertex until the next tree edge becomes active; the bounded-dormancy property caps each wait at d timesteps, giving 2dn in total. For always-connected graphs, a stronger dormancy bound in terms of the minimum degree δ gives the 2δn upper bound. The lower-bound construction layers many copies of a slow path gadget, forcing an agent to advance through at most five layers and then wait Ω(d) timesteps, which sums to Ω(dn).","pith_inferences":["The occurrence-proximity lemma (Lemma 7) can be tested directly on the paper's own path construction: for n=4, w = 1 2 1 3 2 4 3 4, vertices 1 and 4 are distance 3 apart, yet their first occurrence positions are 1 and 6, which violates the lemma's bound; if this counterexample stands, the general upper-bound proof loses its foundation, though the always-connected bound (which relies on a different","The lower-bound construction suggests a natural stress test for the constants: computing the exact optimal exploration time for the constructed path graphs would reveal whether the factor 2 in 2dn can be reduced, since the construction's waiting gaps indicate the true worst case may have a smaller constant.","The definition of word-representable temporal graphs ties the timing of edges to the internal repetition structure of a single word; this could be exploited to give simple exploration algorithms for specific word families (e.g., periodic words), and to characterise which temporal graphs admit such a compact representation."],"forward_implications":["If Theorem 11 holds, then every sufficiently long word-representable temporal graph with connected underlying graph is explorable in time linear in the product of diameter and vertex count, and no asymptotic improvement is possible because of Theorem 22.","The always-connected bound of 2δn is stronger than the diameter bound when the graph is dense, because δ can be much smaller than d; this gives a faster schedule for graphs that are well-connected at every step.","The lower-bound construction shows that temporal graphs can encode forced waiting periods, so any exploration algorithm for this representation class must budget for Ω(dn) timesteps in the worst case.","For path-like word-representable temporal graphs, the paper's construction yields a quadratic lower bound (Ω(n^2) for diameter d=Θ(n)), indicating that even very sparse graph classes can be slow to explore."],"supporting_citations":[{"why":"Introduces word-representable graphs, the base notion from which the paper's temporal word-representation is derived.","marker":"[20]"},{"why":"Landmark study of temporal graph exploration; provides the general O(n^2) upper bound and the single-agent exploration model the paper builds on.","marker":"[8]"},{"why":"Shows always-connected k-edge-deficient temporal graphs are explorable in O(kn log n) timesteps, a bound the paper's always-connected result improves.","marker":"[10]"},{"why":"Gives faster exploration for k-chord graphs and treewidth-bounded graphs, serving as a comparison baseline for the new linear-in-diameter bound.","marker":"[1]"}],"fun_headline_variants":["Bounded dormancy makes word-representable temporal graphs fast to explore","Exploration time for word-temporal graphs: at most 2dn steps","Waiting windows: how word-encoding cuts exploration to 2dn","Temporal graphs from words: guaranteed 2dn-step exploration"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 7, which says that in the representing word, the k-th occurrence of any two vertices at graph distance d lie at most d positions apart; if that proximity bound fails, the proof that no edge stays inactive for more than d consecutive timesteps—and hence the 2dn upper bound—collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bounded dormancy makes word-representable temporal graphs fast to explore","Exploration time for word-temporal graphs: at most 2dn steps","Waiting windows: how word-encoding cuts exploration to 2dn","Temporal graphs from words: guaranteed 2dn-step exploration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000662,"raw_usage":{"total_tokens":3028,"prompt_tokens":952,"completion_tokens":2076,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":2001}},"tokens_in":568,"tokens_out":2076,"duration_ms":14045,"temperature":1.0,"reasoning_tokens":2001,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T12:35:55.049053+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check Lemma 7 on the paper's own path construction for n=4, whose word is 1 2 1 3 2 4 3 4: vertices 1 and 4 are at distance 3 in the underlying path, yet the first occurrence of 1 is at position 1 and the first occurrence of 4 is at position 6, so the position difference (5) exceeds d=3. If this single check confirms the violation, the lemma is false and the general upper-bound argument is unsupported.","supporting_citations":[{"cited_title":"On representable graphs","cited_arxiv_id":null,"evidence_quote":"Introduces word-representable graphs, the base notion from which the paper's temporal word-representation is derived."},{"cited_title":"On temporal graph exploration","cited_arxiv_id":null,"evidence_quote":"Landmark study of temporal graph exploration; provides the general O(n^2) upper bound and the single-agent exploration model the paper builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows always-connected k-edge-deficient temporal graphs are explorable in O(kn log n) timesteps, a bound the paper's always-connected result improves."},{"cited_title":"Faster exploration of some temporal graphs","cited_arxiv_id":null,"evidence_quote":"Gives faster exploration for k-chord graphs and treewidth-bounded graphs, serving as a comparison baseline for the new linear-in-diameter bound."}],"review_version":1}