{"id":"78d7c380-b2c3-420b-9e64-95c8e47efdf0","arxiv_id":"1908.03218","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Two-type annihilating random walks on complete and star graphs have extinction times asymptotically larger than one-type annihilation, with near-matching upper and lower bounds for symmetric and asymmetric speeds.","lead":"This paper studies red and blue particles that move randomly on two simple network shapes, the complete graph and the star graph, and annihilate when different colors meet. It proves the first bounds on how long two-color annihilation takes on finite graphs, and shows that asymmetric movement speeds change the extinction time.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim survives, but Lemma 18's printed proof does not justify the 3/n probability bound: the stated variance gives only Chebyshev O(1/((1-p)n)), so Theorem 5's upper bound needs a repaired concentration step.","rationale":"The paper's central claim—that two-type annihilating systems on the complete and star graphs survive asymptotically longer than one-type systems—is supported by arguments that are essentially correct. I checked the master formula Lemma 7 in detail; it is exact and handles all four cases (leaf-to-core collision, core-to-leaf collision, leaf-to-core non-collision, core-to-leaf non-collision). The stochastic domination for the complete graph lower bound and the upper-bound occupancy argument are also valid modulo small omitted high-probability error terms. The star-graph lower bounds via M_t and D_t are sound. The main weakness is Lemma 18: the displayed variance bound does not yield the stated 3/n via the implied Chebyshev step, so the proof of Theorem 5's upper bound needs a repaired concentration argument. This is a proof gap, not a refutation: a Chernoff bound for negatively associated coupon-collector indicators gives the needed tail, and a weaker O(1/n) bound would still suffice for the theorem's leading constant. The additional algebraic slips in Lemma 13 (equation (12)) and Lemma 10 (the asymptotic of ED_{2n}) are localized and, in the case of Lemma 10, the correct asymptote would only strengthen the lower-bound constant. The reader's conditional verdict is appropriate; my concern does not move it.","tokens_in":17868,"tokens_out":59038,"duration_ms":556657,"concrete_test":"Replace the final Chebyshev step in Lemma 18 with a sharp concentration bound for the negatively associated coupon-collector indicators, or numerically simulate the coupon process for r=5, p=0.99, n=10^4 and estimate P(V′ ≥ (1−p)n); check whether the probability is ≤ 3/n. Also verify Lemma 10 by summing 2^{-2k} binom(2k,k) from k=1 to n−1 and comparing with √(2n/π); the correct asymptote should be 2√(n/π).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing issue is in Lemma 18 (Section 5.2), the coupon-collector estimate supporting the p→1 upper bound (Theorem 5/Lemma 19). The proof bounds Var(V′) ≤ (1−p)n and then asserts P(V′ ≥ (1−p)n) ≤ 3/n via an implicit Chebyshev step. Direct substitution gives P ≤ 4(1−p)n/((1−p)^2 n^2) = 4/((1−p)n), which is not ≤ 3/n; for p=0.99, for example, this is 400/n. A weaker O(1/n) bound is sufficient for Lemma 19 because its contribution to E[A_t] is O(1), but the proof as printed has a real gap. Separately, Lemma 10 states ED_{2n} ∼ √(2n/π), which is inconsistent with its own sum formula 1 + ∑_{k=1}^{n-1} 2^{-2k} binom(2k,k) that asymptotes to 2√(n/π); Lemma 13's equation (12) is algebraically incorrect. These are localized and do not threaten the qualitative claims. The reader's identified weakest assumption, the master formula Lemma 7, checks out by induction in all collision and non-collision cases.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a discrete-time two-type annihilating particle system on the complete graph K_{2n} and the star graph S_{2n}, with equal initial numbers of red and blue particles and with blue selected with probability p≥1/2. It compares the extinction time T_p^2(G) with the one-type extinction time T^1(G). The main quantitative claims are: Theorem 2 gives 2n log n ≤ ET_p^2(K_{2n}) ≤ O(n(log n)^2/log log n); Theorem 3 gives ET_{1/2}^2(S_{2n}) = 2n + Θ(√n) up to a logarithmic factor in the upper bound; Theorems 4 and 5 bound the p∈(1/2,1) regime in terms of log(1/(1-p)); and Theorem 6 gives an exact distributional identity for p=1. The proofs are built around the master formula A_t = 2n - t + C_t + 2M_t, couplings to random walks, and coupon-collector estimates.","tokens_in":18138,"tokens_out":15337,"duration_ms":149274,"significance":"If the results stand after the repairs below, this is a useful and apparently novel contribution: it initiates the study of extinction times for two-type annihilating systems on finite graphs and identifies clustering as the reason the two-type system survives asymptotically longer than the one-type system. The proof strategy is self-contained and mostly transparent: the master formula is verified by induction, the p=1 result is an exact distributional identity, and the stochastic bounds use explicit geometric and coupon-collector arguments rather than fitted parameters. The paper also states open problems and conjectures that give the work additional value.","major_comments":[{"comment":"The proof bounds Var(V′) ≤ (1−p)n and then asserts P(V′ ≥ (1−p)n) ≤ 3/n. Chebyshev's inequality gives P(|V′−EV′| ≥ (1−p)n/2) ≤ 4 Var(V′)/((1−p)^2 n^2) ≤ 4/((1−p)n), which is not ≤ 3/n for any p∈[1/2,1); indeed 4/(1−p) > 3, so the printed variance bound cannot yield 3/n. This is load-bearing for the upper bound in Theorem 5 through Lemma 19. The gap is repairable: since Lemma 19 only needs an O(1/n) bound, replace the asserted 3/n by 4/((1−p)n) and adjust the subsequent 4/n estimate in Lemma 19 accordingly; the resulting error is O_p(1) and does not affect the leading constant in Theorem 5. The statements of Lemmas 18 and 19 should be corrected in the revision.","section":"§5.2, Lemma 18"},{"comment":"The claimed asymptotics ED_{2n} ∼ √(2n/π) is inconsistent with the displayed identity ED_{2n} = 1 + ∑_{k=1}^{n-1} 2^{-2k} binom(2k,k). Stirling gives 2^{-2k} binom(2k,k) ∼ 1/√(πk), so the sum is ∼ 2√(n/π). Theorem 3(i) uses the lemma to obtain the constant (32π)^{-1/2}; the corrected value gives a larger constant, so the theorem remains true, but the printed lemma and the sentence 'Integrating ... gives the claimed asymptotic formula' must be fixed.","section":"§4.1, Lemma 10"}],"minor_comments":[{"comment":"Equation (12) is algebraically incorrect: for C=4 the printed expression is negative while the integral is approximately 1.80. The conclusion of the lemma is still true, for instance by bounding √(2n−x) ≤ √(2n) and integrating x^{-1} dx over [1,2n]; the closed form should be corrected or replaced by this simpler estimate.","section":"§4, Lemma 13"},{"comment":"There are several typographical and OCR artifacts in the text, including 'throug h-' in the abstract and 'Micha/suppress l' in the bibliography; a careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the results are plausible; the required fixes are technical rather than conceptual, and I would not reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper before the next seminar: it is the first systematic study of two-type annihilation times on finite graphs, and it delivers real results. For the complete graph it shows the two-type extinction time is at least 2n log n, twice the one-type time, with an upper bound of n log^2 n/log log n. For the star graph the picture is sharper: symmetric speeds give a second-order term between sqrt(n) and sqrt(n) log n, and asymmetric speeds give leading constants matching up to constants, via a coupon-collector mechanism for p near 1. The p=1 case gives an exact distributional identity. The master formula in Lemma 7, A_t = 2n - t + C_t + 2M_t, is a neat tool and it checks out by induction; the lower-bound coupling to random walks and the coupon-collector arguments are fresh.\n\nThe soft spots are localized but real. Lemma 13's displayed closed form (12) is algebraically incorrect: for C=4 it evaluates negative while the integral is positive. The bound is still true, but the formula needs fixing. Lemma 10 states ED_{2n} ~ sqrt(2n/pi), but its own sum formula 1 + sum binom(2k,k)/4^k gives the constant 2/sqrt(pi), not sqrt(2/pi). Again the theorem is unaffected because only the order matters. More substantively, Lemma 18's concentration step is not justified as printed: the variance bound Var(V') <= (1-p)n and Chebyshev give P(...) = O(1/((1-p)n)), not 3/n. The final upper bound in Lemma 19 only needs O(1/n) with the constant allowed to depend on p, so this is repairable—I read it as a genuine typos rather than a crack in the argument—but the proof as written has a gap.\n\nNone of these affect the main qualitative claims. I'd send this to a serious referee, with the request that they check the constants in Section 5.2 and the two asymptotic statements. The paper introduces a quantity worth having and handles it honestly. If you work on interacting particle systems, finite graphs, or even coupon-collector variants, it is worth a slot in your reading group.","headline":"Solid finite-graph results for two-type annihilation, with localized proof errors that don't threaten the main theorems.","tokens_in":18661,"tokens_out":5717,"would_cite":true,"duration_ms":55476,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K35","05C81","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two-type annihilating systems on complete and star graphs survive asymptotically longer than their one-type counterparts, with sharp bounds on the star graph for every speed bias.","keywords":["annihilating particle systems","two-type systems","extinction time","complete graph","star graph","random walks","coupon collector","asymmetric speeds"],"falsifier":"Run the p=1 star process for n = $10^{2}$, $10^{3}$, $10^{4}$ and compare the empirical distribution of the extinction time against 2∑_{i=1}^n X(i/2n); a systematic deviation would falsify Theorem 6 and the master formula behind it. Alternatively, for a fixed p close to 1, measure $ET^{2}$_p(S_{2n})/n for increasing n and check that the coefficient lies between approximately 4 and 12 times log(1/(1-p)), as Theorem 5 requires; an empirical coefficient outside that window at large n would refute the asymptotics.","tokens_in":17694,"feed_emoji":"🧪","tokens_out":6840,"duration_ms":70284,"temperature":0.7,"pith_summary":"This paper asks how long red and blue particles take to annihilate each other on two finite graphs, the complete graph on 2n vertices and the star graph with 2n leaves plus one core, when each step samples a random particle to walk and opposite colors annihilate on contact. Its central claim is that a two-type system survives asymptotically longer than the one-type system, because like-colored particles cluster and create safe sites. On the complete graph the expected extinction time is shown to be at least 2n log n, twice the one-type baseline, and at most 20n(log n)^2/log log n. On the star graph the results are sharper: with symmetric speeds the excess over 2n is between c√n and C√n log n, and with asymmetric speeds the leading coefficient is identified up to universal constants, growing like log(1/(1-p)) as the speed bias p approaches 1. The p=1 case, where red particles are immobile, has an exact distributional formula.","feed_headline":"Two-type annihilation outlasts one-type on complete and star graphs","feed_subtitle":"New bounds show the color-mixing process takes longer to die out, with exact rates on the star graph for biased speeds.","key_machinery":"The load-bearing object is the accounting identity in Lemma 7, A_t = 2n - t + C_t + 2M_t, where A_t is the number of surviving particles, C_t the number at the core, and M_t the number of times a core particle is sampled and moves to a leaf without annihilating. The identity converts extinction-time questions into estimates of core occupancy and non-annihilating core exits; those are then controlled by couplings to simple random walks for the symmetric case and to a coupon-collector process for p near 1.","core_discovery":"The paper establishes that for all p in [1/2,1] the two-type extinction time $T^{2}$_p(K_{2n}) on the complete graph stochastically dominates a sum of geometric random variables, giving E $T^{2}$_p(K_{2n}) ≥ 2n log n, while a site-capacity argument gives E $T^{2}$_p(K_{2n}) ≤ 20n(log n)^2/log log n. Since the one-type extinction time on the complete graph is n log n + γn + Θ(1), the two-type process survives at least twice as long asymptotically. On the star graph, the master formula A_t = 2n - t + C_t + 2M_t yields, for p = 1/2, that E $T^{2}$_{1/2}(S_{2n}) - 2n has order between √n and √n log n; for p ∈ (1/2,1), the leading coefficient lies between 2 + (2p-1)/2 and 2/(1-p); and as p ↑ 1 the coefficient grows like log(1/(1-p)) with universal constants. The limiting p=1 case is equal in distribution to 2∑_{i=1}^n X(i/2n), so its expectation is 4n log n + 4γn + Θ(1).","pith_inferences":["The logarithmic gap between the complete-graph upper and lower bounds suggests the true order may be n log n with a coefficient of 2; a sharper upper bound of O(n log n) would confirm that the complete graph's two-type system is only twice as slow as the one-type system.","The master formula's structure suggests the same core-versus-leaves bookkeeping could transfer to any graph with a distinguished hub and many leaves, such as split graphs or trees with small diameter, where similar √n or log(1/(1-p)) corrections might appear.","The coupon-collector interpretation for p near 1 indicates that the bottleneck is blue particles visiting every initially red leaf, so the sharp constant may depend only on the sampling bias and not on finer graph structure; this could be tested by replacing the star's leaves with a regular tree and comparing coefficients."],"forward_implications":["On the complete graph, the expected extinction time of the two-type system is at least twice the one-type time, so like-colored clustering genuinely slows neutralization on dense graphs.","On the star graph with symmetric speeds, the extinction time exceeds 2n by a term of order between √n and √n log n, whereas the one-type correction is only logarithmic, making clustering at the core visible in the second-order term.","For asymmetric speeds with p ∈ (1/2,1), the leading coefficient of the star-graph extinction time is strictly larger than in the symmetric case, with explicit universal bounds in p.","As the speed bias approaches 1, the star-graph extinction time grows like log(1/(1-p)) n, with the leading constant pinned between 4 and 12; the conjectured sharp constant is 4.","When p=1 the extinction time on the star graph has an exact distributional identity, 2∑_{i=1}^n X(i/2n), giving expectation 4n log n + 4γn + Θ(1)."],"supporting_citations":[{"why":"Defines the p=1 immobile-red setting that Theorem 6 extends to an exact distributional identity.","marker":"[DGJ+17]"},{"why":"Supplies the birth-and-death chain hitting bound used in the complete-graph upper bound.","marker":"[Dur19]"},{"why":"Gives the benchmark density-decay results for two-type annihilating systems on Z^d that motivate the finite-graph comparison.","marker":"[BL91]"},{"why":"Provides the universal lower bound and asymmetric-speed framework that Theorem 4's bounds build on.","marker":"[CRS18]"},{"why":"Studies annihilating and predator-prey dynamics on finite random graphs, the closest prior finite-setting work the paper extends.","marker":"[CFR09a]"}],"fun_headline_variants":["Two-type extinction time at least double on complete graph","Color-mixing death takes longer on complete and star graphs","Two-type annihilation lasts twice as long on complete graph","Two-type annihilation outlives one-type on two graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The star-graph theorems all rest on Lemma 7's identity A_t = 2n - t + C_t + 2M_t, which assumes the particle count is determined exactly by elapsed time, the number of particles at the core, and the number of non-annihilating core exits; if collisions could occur without changing those three quantities, the identity and the bounds built on it would fail.","fun_headline_variants_meta":{"raw":{"variants":["Two-type extinction time at least double on complete graph","Color-mixing death takes longer on complete and star graphs","Two-type annihilation lasts twice as long on complete graph","Two-type annihilation outlives one-type on two graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000528,"raw_usage":{"total_tokens":2512,"prompt_tokens":877,"completion_tokens":1635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":1570}},"tokens_in":493,"tokens_out":1635,"duration_ms":12026,"temperature":1.0,"reasoning_tokens":1570,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:22:16.116734+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the p=1 star process for n = $10^{2}$, $10^{3}$, $10^{4}$ and compare the empirical distribution of the extinction time against 2∑_{i=1}^n X(i/2n); a systematic deviation would falsify Theorem 6 and the master formula behind it. Alternatively, for a fixed p close to 1, measure $ET^{2}$_p(S_{2n})/n for increasing n and check that the coefficient lies between approximately 4 and 12 times log(1/(1-p)), as Theorem 5 requires; an empirical coefficient outside that window at large n would refute the asymptotics.","supporting_citations":[],"review_version":1}