Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

For any fixed temporal motif, random temporal graphs show a sharp existence threshold set by the motif's sparsest subgraph — a different exponent from static random graphs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 05:35 UTC pith:RGVNB3KG

load-bearing objection Plausible and natural sharp-threshold results, but the printed second-moment bounds do not close at the claimed thresholds, so the existence half of the main theorem needs repair before the paper is verifiable. the 3 major comments →

arxiv 2602.01847 v3 pith:RGVNB3KG submitted 2026-02-02 cs.DM math.PR

Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs

Henry Austin , George B. Mertzios , Paul G. Spirakis This is my paper
classification cs.DM math.PR MSC 05C8068R10
keywords temporal motifsrandom temporal graphssharp thresholdssparsitysecond moment methoddoubling timereachabilitytemporal clique
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves sharp thresholds for the appearance of arbitrary temporal motifs in two random temporal graph models (continuous and discrete labels). The threshold window is n^{-ρ_H}, where ρ_H is the minimum over subgraphs of (number of vertices)/(number of edges minus one), a quantity the authors call sparsity. This differs from the static random graph threshold, where the densest subgraph density rules; as a result, cycles of different lengths appear at distinct windows, and the partial order on edges does not change the asymptotic threshold. The same techniques bound the largest δ-temporal clique and characterize the doubling time of reachability balls.

Core claim

The central claim is Theorem 10 (and its discrete analogue Theorem 11): for any fixed graph H and partial order P, a random temporal graph sampled from Γ_n(ψ) contains (H,P) as a δ(n)-temporal motif with high probability when δ(n)=ω(n^{-ρ_H}) and does not contain it with high probability when δ(n)=o(n^{-ρ_H}), where ρ_H = min_{I⊆H} |V_I|/(|E_I|−1). The exponent is governed by the sparsest subgraph (with edges minus one in the denominator), not by the overall edge density of H. The paper also proves that the largest δ-temporal clique grows as roughly 2 log n / log(1/δ)-type bounds, and that in the continuous model with a constant number of labels per edge, the maximum doubling time is (2±o(1)

What carries the argument

The paper's main object is the sparsity ρ_H = min_{I⊆H} |V_I|/(|E_I|−1), which sets the threshold exponent. The proofs use first and second moment methods on the number C_δ of motif occurrences, with a refined ratio bound that controls the contribution of multiple occurrences sharing edges. A stochastic domination lemma reduces arbitrary label-multiplicity distributions to Bernoulli or bounded ones. For doubling times, the key tools are the order discretization (retaining only the relative order of labels), a time-reversal symmetry that converts small-set doubling to large-set doubling, and couplings of the growth of reachability balls with sums of geometric random variables.

Load-bearing premise

The load-bearing premise is that the second-moment and ratio bounds actually deliver the subgraph-minimized exponent ρ_H; the text's displayed bounds as written only close for the full graph's ratio n^{-|V_H|/(|E_H|-1)}, and a factor appears missing in Lemma 22, so the claimed sharpness rests on the gap being typographical rather than substantive.

What would settle it

Take H as a K4 with a pendant leaf (5 vertices, 7 edges); the claimed threshold is n^{-4/5} because of the K4 subgraph, while the full-graph ratio gives n^{-5/6}. Simulate the continuous model at δ = n^{-0.81} and δ = n^{-0.79} and determine where (H, any order) appears with high probability; if the switch occurs at n^{-5/6} rather than n^{-4/5}, the subgraph optimization is not realized. Independently, recompute the variance bound for H = triangle: check whether Var[C_δ] ≤ (√(2δr))^{2|E|}(...)n^{2|V|}... as printed, or whether a (δr)^{|E_H|} factor is missing, by a direct calculation of E[C_δ

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Cycles of different lengths appear as temporal motifs at different window sizes: cycle C_i appears at δ=Θ(n^{-i/(i-1)}), whereas in static random graphs all cycles share one threshold.
  • The asymptotic threshold is independent of the partial order P: time-respecting paths of a given length have the same threshold as non-time-respecting ones.
  • For the largest δ-temporal clique, the size is Θ(log n / log(1/δ))-type, with constants depending only on the first two moments of the label multiplicity distribution.
  • In the continuous model with degenerate label counts, the maximum doubling time is concentrated at (2±o(1)) log n / (r n); this gives a sharp finite-doubling threshold for the simpler one-label-per-edge model at edge probability about 2 log n / n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The subgraph-minimized exponent suggests that the temporal motif threshold is controlled not by typical density but by the most 'time-efficient' sub-arrangement; one can test this by comparing two motifs with the same full-graph ratio but different subgraph minima.
  • The paper's threshold result implies a form of universality: the label multiplicity distribution affects the constant factor but not the exponent, so experiments at different label distributions should see the same phase transition location up to constants.
  • For the discrete model, the threshold depends only on the ratio β/T, which suggests a scaling conjecture: any property of the discrete model at window β should match the continuous model at window β/T as T grows; this could be checked against Theorem 11.
  • The doubling-time result, when extended to non-degenerate distributions, would say that the maximum doubling time is governed by the mean label count r; this is testable by simulating the model with different label multiplicity distributions sharing the same r.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper defines two models of random temporal graphs: a continuous model Γ_n(ψ), where each edge receives a random number of labels drawn from a distribution ψ and each label is uniform in (0,1], and a discrete model Γ_n(ψ,T) with labels in {1,...,T}. The central result, Theorem 10/11, claims a sharp existence threshold for every fixed δ-temporal motif (H,P): the threshold is determined by ρ_H = min_{I⊆H} |V_I|/(|E_I|-1), with containment w.h.p. when the window parameter is ω(n^{-ρ_H}) and non-containment w.h.p. when it is o(n^{-ρ_H}). The same machinery is used to give two-sided bounds on the largest δ-temporal clique (Theorem 13) and to bound the doubling time of reachability balls for degenerate label multiplicity distributions (Theorem 14). The proofs use first- and second-moment methods, stochastic domination, and a reduction to an order discretization for the doubling time part.

Significance. If the proof were fully correct, this would be a substantial contribution: it identifies a new subgraph-optimized sparsity invariant that makes temporal motif thresholds qualitatively different from static Erdős–Rényi thresholds, and it extends earlier work on random simple temporal graphs to a more general label-multiplicity model. The paper is also valuable for its explicit treatment of both continuous and discrete model variants and for the breadth of results spanning fixed motifs, growing cliques, and temporal doubling time. The high-level approach is standard and the stated thresholds are plausible, but several load-bearing steps in the written proof need repair before the claimed theorems are established.

major comments (3)
  1. [§8.2, Lemma 46] The proof of the non-existence half applies Lemma 21 to the full graph H and concludes P[Cδ>0] ≤ O(n^{|V_H|} δ^{|E_H|-1}) = o(1) whenever δ = o(n^{-ρ_H}). This implication is false in general. The displayed bound tends to 0 only when δ = o(n^{-|V_H|/(|E_H|-1)}), and |V_H|/(|E_H|-1) can be strictly larger than ρ_H. For example, for H = K4 with a pendant leaf, ρ_H = 4/5 while |V_H|/(|E_H|-1) = 5/6; for δ = n^{-0.81} = o(n^{-4/5}) the bound is n^5 δ^6 = n^{0.14}, which does not go to 0. The argument needs to apply the first moment to a minimizing subgraph I with |V_I|/(|E_I|-1)=ρ_H, since an occurrence of H contains an occurrence of I. This is fixable, but as written it is a load-bearing gap.
  2. [§8.2, Lemmas 50 and 51] The statements of Lemmas 50 and 51 use the threshold n^{-|V_H|/(|E_H|-1)}, not n^{-ρ_H}. These lemmas are therefore strictly weaker than the existence half of Theorems 10 and 11 whenever the minimizing subgraph is proper. The sentence 'Theorem 10 and Theorem 11 then follow immediately from Lemma 46 and Lemma 50' is not justified by the printed statements. The proof of Lemma 50 cites Lemma 48, which is already stated with ρ_H, so it seems the correct threshold is supported by the argument; nevertheless, the formal statements and the derivation need to be corrected. This is a central issue for the main theorem.
  3. [§8.3, Claim 54 / Lemma 53] Claim 54 is stated with k = (1−ε) log n / log W, whereas Lemma 53 requires k = 2(1−ε) log n / log( (δr2−δr+r)/(δr2) ). The factor 2 can only be absorbed if W in Claim 54 is redefined as the square root of that ratio, but the claim does not say this and the surrounding text uses the unsimplified ratio. As printed, the maximization proof does not cover the k used in Lemma 53, so the derivation of the lower bound on the largest δ-temporal clique is incomplete. Please state the definition of W explicitly and adjust the exponent W^{i^2−i} or the statement of k accordingly.
minor comments (4)
  1. [§8.1.2, Lemma 22] I checked the variance bound in Lemma 22 against its proof. The displayed factor (√(2δr))^{2|E_H|} (2δr)^{-|E_I|} gives the per-intersection term (2δr)^{|E_H|-|E_I|}, which matches the derivation; there is no missing (δr)^{|E_H|} factor. The stress-test concern on this point does not land.
  2. [§8.2, after Lemma 48] The notation in Lemma 48's proof is compressed: after substituting Lemma 22, the simplification to O(max_I n^{-|V_I|} δ^{1-|E_I|}) relies on the factor (1+|E_H|(1−δ)/δ) being Θ(δ^{-1}) for δ→0. This is correct but should be stated explicitly, since the same factor appears squared in the denominator.
  3. [General] There are minor notation inconsistencies between Theorem 13 and Lemmas 52/53: the theorem has constant 0<δ<1, while the lemmas also use 0<ε<δ<1. Please harmonize the parameter conventions.
  4. [Definition 4] The definition of a valid label multiplicity distribution says first and second moments are positive and finite, but later q = P[Q>0] is used. If q=0 the model is degenerate; consider stating explicitly that q>0, or treating this case separately.

Circularity Check

1 steps flagged

No significant circularity: thresholds are derived in-text; the sole self-citation (Lemma 3 of [44], via Lemma 39) is a parameter-free geometric probability and does not force the results.

specific steps
  1. other [Section 8.1 (Technical Preliminaries), Lemma 39, adapted from Lemma 3 of [44]]
    "Lemma 39.[Adapted from Lemma 3 of [44]] ForH = (VH,EH)a fixed static graph, P∅(EH,≺)the order overE H such that no two edges are comparable,S∈Sandτ∈T S, P[B(δ) S,τ = 1] =δ|EH|(1 +|EH|(1−δ) δ )"

    The only load-bearing point imported from the authors' own prior work. Lemma 3 of [44] (Mertzios–Nikoletseas–Raptopoulos–Spirakis; two of the present authors) supplies the window probability used by the first/second-moment calculations (Lemmas 20, 22, 23, 41) behind Theorems 10/11/13. This is not a circular reduction: the result is a parameter-free order-statistics probability (for m iid U(0,1] labels, P(range ≤ δ) = mδ^{m−1}(1−δ)+δ^m), independent of the claimed thresholds, and re-derivable in-line. The subgraph-minimized exponent ρ_H and the clique/doubling-time bounds come from in-text computations, not from [44]. Flagged only as a minor, non-load-bearing self-citation.

full rationale

The derivation chain is self-contained and non-circular. The motif thresholds (Theorems 10, 11) rest on first/second moment estimates built in-text: Lemma 20 (expectation), Lemma 21 (probability bound via conditional expectation, Claims 42–43), Lemmas 22–23 (variance, Claims 44–45), Lemma 18 (stochastic domination, proved in-text), and the reductions to Bernoulli (Lemma 50) or to a truncated bounded σ (Lemma 55). The clique bound (Theorem 13) uses Lemmas 52/53/55 with the supporting algebra presented. The doubling-time result (Theorem 14) is proved from scratch via the order discretization: Lemmas 24–28, 56–60 and Claims 61–65 are all derived in the text; [14] is an inspiration, not an imported conclusion. No parameter is fitted to data, no target quantity is redefined as an input, and no uniqueness/ansatz is imported from the authors' earlier work. The sole self-citation in the chain is Lemma 39 = Lemma 3 of [44], an elementary parameter-free geometric probability; per the rubric it is real evidence and does not make any theorem equivalent to its inputs. The serious problems in the manuscript are correctness gaps, not circularity: Lemma 22's displayed bound drops a (δr)^{|E_H|} factor present in its own proof (the per-intersection term '2^{|E_H|-|E_I|}δ^{2|E_H|-|E_I|}r^{2|E_H|-|E_I|}'), which breaks Lemma 48's closing calculation at the claimed threshold (e.g., for H = K3 and δ = n^{-1.4}, the printed bound only gives Var/E^2 ≤ const·n^{2.6}, not o(1)); Claim 54 states k=(1−ε)logn/logW where Lemma 53 requires k=2(1−ε)logn/logW; and Lemmas 46/50 bound occurrences using the full graph H's size while the stated ρ_H = min_I |V_I|/(|E_I|−1) requires an optimization over subgraphs that is not carried out. These affect whether the proofs close, not whether the claims reduce to their inputs. Score 2 reflects the single minor self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The paper introduces no fitted constants or new physical entities. Its model parameters r, r2, q, δ, T are inputs, not free parameters. The main external inputs are standard probability inequalities, the random graph model itself, and one lemma adapted from the authors' own earlier paper. No data fitting or invented mechanisms appear.

axioms (5)
  • standard math First and second moment methods, Markov's inequality, Chernoff bounds, geometric tail bounds, and the drift theorem are valid and applicable as used.
    These are standard probabilistic tools cited in Section 7 (Lemmas 29–33) and used throughout the proofs.
  • domain assumption The random temporal graph models Γ[n](ψ) and Γ[n](ψ,T) are the correct model for the statements: each edge receives an independent number of labels from ψ, and each label is drawn uniformly from (0,1] or {1,…,T}.
    Definitions 4–6 specify the model; all theorems are claims about samples from these distributions.
  • domain assumption Lemma 39, adapted from Lemma 3 of [44], correctly gives the probability that a fixed set of edge labels falls in a δ-window as δ^{|E_H|}(1+O(1/δ)).
    This lemma is load-bearing for the first and second moment calculations and is cited rather than re-derived. It is a simple continuous-geometric fact, but it is still an external input from a self-cited paper.
  • domain assumption The stochastic domination lemma (Lemma 18) correctly reduces arbitrary label-multiplicity distributions to Bernoulli or bounded distributions.
    Used in Lemmas 50, 51, and 55 to extend the second-moment results for Bernoulli/bounded ψ to general ψ; the proof is sketched via a monotone coupling.
  • domain assumption In the doubling-time analysis, the order discretization G^O preserves the key reachability/doubling behavior, and the conversion between discretized and continuous times via label-count concentration (Lemma 60) is valid.
    Definitions 24–26 and Lemmas 56–60 set up the conversion; the proof depends on this discretization being faithful.

pith-pipeline@v1.3.0-alltime-deepseek · 40667 in / 37263 out tokens · 339672 ms · 2026-08-03T05:35:24.241044+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs." pith.science (2026). https://pith.science/paper/RGVNB3KG

@misc{pith2026260201847,
  author       = {Pith},
  title        = {Pith review of: Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RGVNB3KG}},
  note         = {Machine review of arXiv:2602.01847}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge $e$ is assigned $l_e$ labels, each drawn uniformly at random from $(0,1]$, where the numbers $l_e$ are independent random variables following the same discrete probability distribution. In the second, the discrete model, the $l_e$ labels of each edge $e$ are chosen uniformly at random from a set $\{1,2,\ldots,T\}$. In both models we study the existence of $\delta$-temporal motifs. Here a $\delta$-temporal motif consists of a pair $(H,P)$, where $H$ is a fixed static graph and $P$ is a partial order over its edges. A temporal graph $\mathcal{G}=(G,\lambda)$ contains $(H,P)$ as a $\delta$-temporal motif if $\mathcal{G}$ has a simple temporal subgraph on the edges of $H$ whose time labels are ordered according to $P$, and whose life duration is at most $\delta$. We prove sharp existence thresholds for all $\delta$-temporal motifs, and we identify a qualitatively different behavior from the analogous static thresholds in Erdos-Renyi random graphs. Applying the same techniques, we then characterize the growth of the largest $\delta$-temporal clique in the continuous variant of our random temporal graphs model. Finally, we consider the doubling time of the reachability ball centered on a small set of vertices of the random temporal graph as a natural proxy for temporal expansion. We prove sharp upper and lower bounds for the maximum doubling time in the continuous model.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Maximizing Reachability via Shifting of Temporal Paths

    cs.DS 2026-05 unverdicted novelty 6.0

    Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.

Reference graph

Works this paper leans on

10 extracted references · 1 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [4]

    How to color temporal graphs to ensure proper transitions.CoRR, abs/2505.10207,

    29 Allen Ibiapina, Minh-Hang Nguyen, Mikaël Rabie, and Cléophée Robin. How to color temporal graphs to ensure proper transitions.CoRR, abs/2505.10207,

    Pith/arXiv arXiv

  2. [6]

    Temporal motifs in time-dependent networks.Journal of Statistical Mechanics: Theory and Experiment, 2011(11):P11005,

    35 Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks.Journal of Statistical Mechanics: Theory and Experiment, 2011(11):P11005,

    2011

  3. [11]

    Detecting mixing services via mining bitcoin transaction network with hybrid motifs.IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52(4):2237–2249, 2022

    59 Jiajing Wu, Jieli Liu, Weili Chen, Huawei Huang, Zibin Zheng, and Yan Zhang. Detecting mixing services via mining bitcoin transaction network with hybrid motifs.IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52(4):2237–2249, 2022

    2022

  4. [2011]

    General drift analysis with tail bounds.CoRR, abs/1307.2559,

    36 Per Kristian Lehre and Carsten Witt. General drift analysis with tail bounds.CoRR, abs/1307.2559,

    Pith/arXiv arXiv

  5. [2015]

    Vestergaard

    23 Laetitia Gauvin, Mathieu Génois, Márton Karsai, Mikko Kivelä, Taro Takaguchi, Eugenio Valdano, and Christian L. Vestergaard. Randomized reference models for temporal networks. SIAM Review, 64(4):763–830, 2022.arXiv:https://doi.org/10.1137/19M1242252, doi:10. 1137/19M1242252. 24 Thekla Hamm, Nina Klobas, George B. Mertzios, and Paul G. Spirakis. The com...

    doi:10.1137/19m1242252 2022

  6. [2016]

    Temporal exploration of random spanning tree models

    9 Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, and Viktor Zamaraev. Temporal exploration of random spanning tree models. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2876–2887,

    2026

  7. [2017]

    Porter, Baharan Mirzasoleiman, and Jure Leskovec

    52 Alexandra M. Porter, Baharan Mirzasoleiman, and Jure Leskovec. Analytical models for motifs in temporal networks. InProceedings of the Companion of The Web Conference 2022, pages 903–909. ACM,

    2022

  8. [2019]

    57 Jordan Viard, Matthieu Latapy, and Clémence Magnien

    URL: http://arxiv.org/abs/1906.11121, arXiv: 1906.11121. 57 Jordan Viard, Matthieu Latapy, and Clémence Magnien. Revealing contact patterns among high-school students using maximal cliques in link streams. InProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 1517–1522,

    Pith/arXiv arXiv 1906

  9. [2023]

    Temporal connectivity of random geometric graphs.arXiv preprint arXiv:2502.15274,

    12 Anna Brandenberger, Serte Donderwinkel, Céline Kerriou, Gábor Lugosi, and Rivka Mitchell. Temporal connectivity of random geometric graphs.arXiv preprint arXiv:2502.15274,

    Pith/arXiv arXiv

  10. [2025]

    How to Color Temporal Graphs to Ensure Proper Transitions

    URL: https: //doi.org/10.48550/arXiv.2505.10207. 30 Svante Janson. Tail bounds for sums of geometric and exponential variables.Statistics & Probability Letters, 135:1–6,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2505.10207