A Tight Epidemic Threshold for Competing Stochastic Infection Processes with Mutually Exclusive Immunity
Pith reviewed 2026-05-20 04:33 UTC · model grok-4.3
The pith
Two competing infections with mutually exclusive immunity exhibit a tight epidemic threshold on perfectly mixed graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Our main result is a tight threshold, known as epidemic threshold, where the survival time rapidly changes from at most quasi-linear in the graph size n to at least super-polynomial in n. This result is applicable to perfectly mixed graphs, which are graphs where the density of edges between each non-empty subset of vertices is a given value p ∈ (0, 1]. Our super-polynomial lower bound extends to jumbled graphs, which allow for some more flexibility in the density. In particular, this includes with high probability Erdos-Renyi graphs with an average degree of k∈ω(ln²(n)). The proof for the lower bound is based on a potential that transforms the configurations of the IRIR process to a superma
What carries the argument
A potential function derived from a Lyapunov function of the transition equilibrium that converts IRIR configurations into a supermartingale with drift in a large region.
If this is right
- Below the threshold the survival time of the IRIR process is at most quasi-linear in n on perfectly mixed graphs.
- Above the threshold the survival time is at least super-polynomial in n with high probability.
- The super-polynomial lower bound carries over to jumbled graphs that include Erdős–Rényi graphs of average degree omega(log squared n).
- A systematic derivation produces the required potential from a Lyapunov function of the equilibrium of the transition rates.
Where Pith is reading between the lines
- In networks that closely approximate uniform edge density, competing pathogens with type-specific immunity may persist far longer than single-infection models predict.
- The supermartingale construction from equilibrium Lyapunov functions may extend to persistence questions in other multi-state Markov chains on graphs.
- Finite-n simulations should reveal a sharp increase in observed survival times as the control parameter crosses the threshold value.
Load-bearing premise
There exists a potential function that converts the IRIR configurations into a supermartingale with drift in a sufficiently large region of the state space.
What would settle it
Running the IRIR process many times on a large perfectly mixed graph with parameters just above the threshold and finding that survival time stays polynomial in n in a positive fraction of runs would disprove the super-polynomial lower bound.
read the original abstract
Stochastic infection processes are continuous-time Markov chains on graphs that assign each vertex one of multiple states, such as susceptible, infected, or recovered. Depending on the model, vertices change their state based on random transition rates and the states of their neighbors, resulting in a variety of complex dynamics. The body of rigorous literature is rich for processes that consider a single infection. In contrast, the setting with at least two infections, where the same state exists for different types, allows for far more transition combinations, leaving several interesting models entirely unexplored. We address this shortcoming in the literature by defining the IRIR process, in which two SIR processes run on the same graph and each vertex is immune only to its most recent infection. We study the survival time of the IRIR process, that is, the time until no infected vertex remains, with mathematical rigor. Our main result is a tight threshold, known as epidemic threshold, where the survival time rapidly changes from at most quasi-linear in the graph size $n$ to at least super-polynomial in $n$. This result is applicable to perfectly mixed graphs, which are graphs where the density of edges between each non-empty subset of vertices is a given value $p \in (0, 1]$. Our super-polynomial lower bound extends to jumbled graphs, which allow for some more flexibility in the density. In particular, this includes with high probability Erdos-Renyi graphs with an average degree of $k\in \omega(\ln^2(n))$. Our proof for the lower bound is based on a potential that transforms the configurations of the IRIR process to a supermartingale with drift in a large region, implying the lower bound. We detail how to systematically derive such a potential, based on a Lyapunov function of the transition equilibrium of the process.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript defines the IRIR process, a continuous-time Markov chain on a graph in which two SIR-type infections compete and each vertex acquires immunity exclusively to its most recent infection. On perfectly mixed graphs (constant edge density p for every nonempty vertex subset) the authors prove a tight epidemic threshold: below the threshold the survival time is at most quasi-linear in n, while above it the survival time is at least super-polynomial in n with high probability. The super-polynomial lower bound is obtained by constructing a potential V from a Lyapunov function L of the deterministic mean-field equilibrium; the resulting process is shown to be a supermartingale with negative drift on a large region of state space. The argument extends to jumbled graphs and therefore applies to Erdős–Rényi graphs with average degree ω(log² n).
Significance. If the supermartingale construction is uniform, the result supplies the first rigorous tight threshold for competing infections with mutually exclusive immunity on dense random graphs. The systematic derivation of the potential from the mean-field Lyapunov function is a methodological contribution that may extend to other multi-type infection models. The explicit applicability to Erdős–Rényi graphs with moderately dense regimes strengthens the practical relevance.
major comments (1)
- [Proof of the super-polynomial lower bound (via potential construction from mean-field Lyapunov function)] The central lower-bound argument asserts that the potential V, built from the Lyapunov function L of the transition equilibrium, yields a supermartingale with strictly negative drift on a 'large region' of configurations. Because the super-polynomial survival claim rests on this property holding with high probability, the manuscript must explicitly control the second-order terms arising from the continuous-time Markov chain generator when empirical densities fluctuate by O(1/√n) or when one infection type dominates. Without a uniform bound on these fluctuation terms (or an explicit error analysis showing they remain o(1) relative to the negative drift), the supermartingale property may fail on a set of positive probability, undermining the claimed threshold.
minor comments (2)
- [Abstract] The abstract states that the result applies to 'perfectly mixed graphs' with density p ∈ (0,1]; a brief remark clarifying whether p may depend on n (while remaining bounded away from 0 and 1) would help readers interpret the regime.
- [Statement of main results] The extension to jumbled graphs is mentioned but not quantified; stating the precise discrepancy tolerance (e.g., o(1) or O(1/log n)) would make the Erdős–Rényi corollary fully self-contained.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the detailed comment on the supermartingale construction. We address the concern below and will incorporate the requested clarification in the revision.
read point-by-point responses
-
Referee: The central lower-bound argument asserts that the potential V, built from the Lyapunov function L of the transition equilibrium, yields a supermartingale with strictly negative drift on a 'large region' of configurations. Because the super-polynomial survival claim rests on this property holding with high probability, the manuscript must explicitly control the second-order terms arising from the continuous-time Markov chain generator when empirical densities fluctuate by O(1/√n) or when one infection type dominates. Without a uniform bound on these fluctuation terms (or an explicit error analysis showing they remain o(1) relative to the negative drift), the supermartingale property may fail on a set of positive probability, undermining the claimed threshold.
Authors: We agree that an explicit uniform bound on the second-order fluctuation terms is needed to complete the argument. In the revised manuscript we will add a dedicated error-analysis subsection. Using standard concentration bounds on the empirical densities together with a case distinction near the axes (where one infection dominates), we will show that the generator error is at most O(1/√n) while the negative drift inherited from the mean-field Lyapunov function remains bounded below by a positive constant on the region of interest. The resulting supermartingale inequality then holds with high probability, preserving the super-polynomial lower bound. revision: yes
Circularity Check
No circularity: potential derived systematically from mean-field Lyapunov equilibrium
full rationale
The lower-bound proof constructs a potential V from a Lyapunov function L of the deterministic transition equilibrium (mean-field ODE) and verifies supermartingale drift on a large region for perfectly mixed graphs. This is a standard, non-circular technique that uses external graph-density properties and does not reduce the claimed threshold to a fitted parameter, self-definition, or self-citation chain. The super-polynomial survival follows directly from the supermartingale property without the result being presupposed in the construction. No load-bearing self-citations or ansatz smuggling appear in the provided derivation outline.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The IRIR process is a continuous-time Markov chain whose transitions depend on the states of neighboring vertices and the most recent infection type at each vertex.
- domain assumption Perfectly mixed graphs have uniform edge density p between every non-empty subset of vertices.
invented entities (1)
-
IRIR process
no independent evidence
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Our proof for the lower bound is based on a potential that transforms the configurations of the IRIR process to a supermartingale with drift in a large region, implying the lower bound. We detail how to systematically derive such a potential, based on a Lyapunov function of the transition equilibrium of the process.
-
IndisputableMonolith/Foundation/AlphaCoordinateFixation.leancostAlphaLog_high_calibrated_iff unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We define for all t ... F_t = x1 f(I1*,I1,t) + ... with f(x*,x) = x*(x/x* - ln(x/x*) - 1)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
On the spread of viruses on the internet , author =. 2005 , journal =
work page 2005
-
[2]
Random Structures & Algorithms , volume =
How to distribute antidote to control epidemics , author =. Random Structures & Algorithms , volume =. 2010 , publisher =
work page 2010
-
[3]
ACM Transactions on Information and System Security (TISSEC) , volume =
Epidemic thresholds in real networks , author =. ACM Transactions on Information and System Security (TISSEC) , volume =. 2008 , publisher =
work page 2008
-
[4]
Journal of Nonlinear Systems and Applications , volume =
VIRUSLIKE DYNAMICS ON STARLIKE GRAPHS , author =. Journal of Nonlinear Systems and Applications , volume =
-
[5]
IEEE/ACM Transactions On Networking , volume =
Virus spread in networks , author =. IEEE/ACM Transactions On Networking , volume =. 2008 , publisher =
work page 2008
-
[6]
Proceedings of International Conference on Computer Communications (INFCOM) , volume =
The effect of network topology on the spread of epidemics , author =. Proceedings of International Conference on Computer Communications (INFCOM) , volume =. 2005 , doi =
work page 2005
-
[7]
Discrete-time Markov chain approach to contact-based disease spreading in complex networks , author =. EPL , volume =. 2010 , publisher =
work page 2010
-
[8]
IEEE Control Systems Magazine , volume =
Analysis and control of epidemics: A survey of spreading processes on complex networks , author =. IEEE Control Systems Magazine , volume =. 2016 , publisher =
work page 2016
-
[9]
Reviews of Modern Physics , volume =
Epidemic processes in complex networks , author =. Reviews of Modern Physics , volume =. 2015 , doi =
work page 2015
-
[10]
Spread of epidemic disease on networks , author =. Physical review E , volume =. 2002 , publisher =
work page 2002
-
[11]
52nd IEEE conference on decision and control , pages =
Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks , author =. 52nd IEEE conference on decision and control , pages =. 2013 , organization =
work page 2013
-
[12]
IEEE Transactions on Control of Network Systems , volume =
Optimal resource allocation for network protection against spreading processes , author =. IEEE Transactions on Control of Network Systems , volume =. 2014 , publisher =
work page 2014
-
[13]
IEEE Transactions on Network Science and Engineering , volume =
An efficient curing policy for epidemics on graphs , author =. IEEE Transactions on Network Science and Engineering , volume =. 2014 , publisher =
work page 2014
-
[14]
Journal of the ACM (JACM) , volume =
Amplifiers for the Moran process , author =. Journal of the ACM (JACM) , volume =. 2017 , publisher =
work page 2017
-
[15]
ACM SIGMETRICS Performance Evaluation Review , volume =
The behavior of epidemics under bounded susceptibility , author =. ACM SIGMETRICS Performance Evaluation Review , volume =. 2014 , publisher =
work page 2014
-
[16]
IEEE INFOCOM 2014-IEEE Conference on Computer Communications , pages =
Epidemic thresholds with external agents , author =. IEEE INFOCOM 2014-IEEE Conference on Computer Communications , pages =. 2014 , organization =
work page 2014
-
[17]
Analyzing Two Competing Epidemic Processes-The Power of Influential Nodes , author =. preprint , year =
-
[18]
Fixed speed competition on the configuration model with infinite variance degrees: equal speeds
Fixed speed competition on the configuration model with infinite variance degrees: equal speeds , author =. arXiv preprint arXiv:1503.09046 , year =
work page internal anchor Pith review Pith/arXiv arXiv
-
[19]
SIAM Journal on Applied Mathematics , volume =
Global stability of virus spreading in complex heterogeneous networks , author =. SIAM Journal on Applied Mathematics , volume =. 2008 , publisher =
work page 2008
-
[20]
Journal of mathematical biology , volume =
Vaccination based control of infections in SIRS models with reinfection: special reference to pertussis , author =. Journal of mathematical biology , volume =. 2013 , publisher =
work page 2013
-
[21]
arXiv preprint arXiv:2007.08047 , year =
Heterogeneity Learning for SIRS model: an Application to the COVID-19 , author =. arXiv preprint arXiv:2007.08047 , year =
-
[22]
Physica A: Statistical Mechanics and its Applications , volume =
Epidemic threshold for the SIRS model on the networks , author =. Physica A: Statistical Mechanics and its Applications , volume =. 2019 , publisher =
work page 2019
-
[23]
Communications in Nonlinear Science and Numerical Simulation , volume =
Analysis of epidemic spreading of an SIRS model in complex heterogeneous networks , author =. Communications in Nonlinear Science and Numerical Simulation , volume =. 2014 , publisher =
work page 2014
-
[24]
Global dynamics of an SIRS model with demographics and transfer from infectious to susceptible on heterogeneous networks , author =. Math. Biosci. Eng , volume =
-
[25]
Physica A: Statistical Mechanics and its Applications , volume =
The optimal dynamic immunization under a controlled heterogeneous node-based SIRS model , author =. Physica A: Statistical Mechanics and its Applications , volume =. 2016 , publisher =
work page 2016
-
[26]
Applied Mathematics-A Journal of Chinese Universities , volume =
An SIRS epidemic model , author =. Applied Mathematics-A Journal of Chinese Universities , volume =. 2004 , publisher =
work page 2004
-
[27]
Chaos, Solitons & Fractals , volume =
Stability of a delayed SIRS epidemic model with a nonlinear incidence rate , author =. Chaos, Solitons & Fractals , volume =. 2009 , publisher =
work page 2009
-
[28]
2009 International Conference on Computational Intelligence and Software Engineering , pages =
An improved SIRS epidemic model on complex network , author =. 2009 International Conference on Computational Intelligence and Software Engineering , pages =. 2009 , organization =
work page 2009
-
[29]
Epidemic spreading on a complex network with partial immunization , author =. Soft Computing , volume =. 2018 , publisher =
work page 2018
-
[30]
Applied Mathematics Letters , volume =
Lyapunov functions and global stability for SIR, SIRS, and SIS epidemiological models , author =. Applied Mathematics Letters , volume =. 2002 , publisher =
work page 2002
-
[31]
The Annals of Probability , volume =
Contact processes on random graphs with power law degree distributions have critical value 0 , author =. The Annals of Probability , volume =. 2009 , publisher =
work page 2009
-
[32]
arXiv preprint arXiv:2004.01149 , year =
Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs , author =. arXiv preprint arXiv:2004.01149 , year =
-
[33]
Journal of Computer and System Sciences , volume =
Temporal cliques admit sparse spanners , author =. Journal of Computer and System Sciences , volume =. 2021 , publisher =
work page 2021
-
[34]
Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical results , author =. Physical Review E , volume =. 2012 , publisher =
work page 2012
-
[35]
The Annals of Probability , volume =
Survival and extinction of epidemics on random graphs with general degree , author =. The Annals of Probability , volume =. 2021 , publisher =
work page 2021
-
[36]
Computational complexity: a modern approach , author =. 2009 , publisher =
work page 2009
-
[37]
SIAM Journal on Discrete Mathematics , author =
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs , doi =. SIAM Journal on Discrete Mathematics , author =
-
[38]
Geometric inhomogeneous random graphs , journal =. 2019 , issn =. doi:https://doi.org/10.1016/j.tcs.2018.08.014 , author =
-
[39]
Random Structures & Algorithms , author =
Cover and hitting times of hyperbolic random graphs , doi =. Random Structures & Algorithms , author =
-
[40]
Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs , journal =. 2020 , issn =. doi:https://doi.org/10.1016/j.spa.2019.04.014 , author =
-
[41]
arXiv preprint arXiv:2501.12170 , year =
Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion , author =. arXiv preprint arXiv:2501.12170 , year =
-
[42]
Krejca and Marcus Pappik , title =
Tobias Friedrich and Andreas G\"obel and Nicolas Klodt and Martin S. Krejca and Marcus Pappik , title =. Electronic Journal of Probability , year =
-
[43]
Proceedings of the International AAAI Conference on Web and Social Media , pages =
Social Influence-Maximizing Group Recommendation , author =. Proceedings of the International AAAI Conference on Web and Social Media , pages =
-
[44]
Proceedings of the International AAAI Conference on Web and Social Media , year =
Retweet-BERT: Political Leaning Detection Using Language Features and Information Diffusion on Social Networks , author =. Proceedings of the International AAAI Conference on Web and Social Media , year =
-
[45]
Proceedings of the AAAI Conference on Artificial Intelligence , year =
Human Mobility Modeling during the COVID-19 Pandemic via Deep Graph Diffusion Infomax , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =
-
[46]
Proceedings of the AAAI Conference on Artificial Intelligence , year =
MS-HGAT: Memory-Enhanced Sequential Hypergraph Attention Network for Information Diffusion Prediction , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =
-
[47]
Journal of King Saud University - Computer and Information Sciences , volume =
State-of-art review of information diffusion models and their impact on social network vulnerabilities , author =. Journal of King Saud University - Computer and Information Sciences , volume =
-
[48]
Proceedings of the International AAAI Conference on Web and Social Media , year =
Network Inference from a Mixture of Diffusion Models for Fake News Mitigation , author =. Proceedings of the International AAAI Conference on Web and Social Media , year =
-
[49]
Maximizing the spread of influence through a social network , author =. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , pages =
-
[50]
Cost-effective outbreak detection in networks , author =. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining , pages =
-
[51]
Random Structures & Algorithms , volume =
Christian Borgs and Jennifer Chayes and Ayalvadi Ganesh and Amin Saberi , title =. Random Structures & Algorithms , volume =. 2010 , doi =
work page 2010
-
[52]
An Introduction to Probability Theory and its Applications , edition =
Feller, William , year =. An Introduction to Probability Theory and its Applications , edition =
-
[53]
Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical results , author =. Physical Review E , volume =. 2012 , month =. doi:10.1103/PhysRevE.86.041125 , url =
-
[54]
Collective versus hub activation of epidemic phases on networks , author =. Physical Review E , volume =. 2016 , doi =
work page 2016
-
[55]
Transactions of the American Mathematical Society , volume =
Critical value asymptotics for the contact process on random graphs , author =. Transactions of the American Mathematical Society , volume =. 2022 , doi =
work page 2022
-
[56]
doi:10.1088/1742-5468/aa58a6 , year =
Yi Wang and Jinde Cao and Ahmed Alsaedi and Tasawar Hayat , title =. doi:10.1088/1742-5468/aa58a6 , year =
-
[57]
Physical Review Letters , volume =
Small world effect in an epidemiological model , author =. Physical Review Letters , volume =. 2001 , doi =
work page 2001
-
[58]
Knowledge and information systems , volume =
Threshold conditions for arbitrary cascade models on arbitrary networks , author =. Knowledge and information systems , volume =. 2012 , publisher =
work page 2012
-
[59]
The European Physical Journal B (EPJB) , year =
Bancal, Jean-Daniel and Pastor-Satorras, Romualdo , title =. The European Physical Journal B (EPJB) , year =
-
[60]
38th Annual AAAI Conference on Artificial Intelligence , pages =
The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models , author =. 38th Annual AAAI Conference on Artificial Intelligence , pages =
-
[61]
Emergence of scaling in random networks , author =. science , volume =. 1999 , publisher =
work page 1999
-
[62]
More sets, graphs and numbers: A Salute to Vera Sos and Andr
Pseudo-random graphs , author =. More sets, graphs and numbers: A Salute to Vera Sos and Andr. 2006 , publisher =
work page 2006
-
[63]
North-Holland Mathematics Studies , volume =
Pseudo-random graphs , author =. North-Holland Mathematics Studies , volume =. 1987 , publisher =
work page 1987
-
[64]
Theoretical analyses of univariate estimation-of-distribution algorithms , author =. 2019 , school =
work page 2019
-
[65]
Statistics & Probability Letters , volume =
Tail bounds for sums of geometric and exponential variables , author =. Statistics & Probability Letters , volume =. 2018 , publisher =
work page 2018
- [66]
-
[67]
Proceedings of the National Academy of Sciences , volume =
Dynamics and selection of many-strain pathogens , author =. Proceedings of the National Academy of Sciences , volume =. 2002 , publisher =
work page 2002
-
[68]
Theoretical Population Biology , volume =
Spatial aspects of interspecific competition , author =. Theoretical Population Biology , volume =. 1998 , publisher =
work page 1998
-
[69]
A stochastic epidemic model with memory of the last infection and waning immunity , author =. 2025 , eprint =
work page 2025
-
[70]
Journal of Mathematical Biology , volume =
Capturing the dynamics of pathogens with many strains , author =. Journal of Mathematical Biology , volume =. 2016 , publisher =
work page 2016
-
[71]
Europhysics Letters , volume =
Outbreaks of coinfections: The critical role of cooperativity , author =. Europhysics Letters , volume =. 2013 , publisher =
work page 2013
-
[72]
The European Physical Journal B , volume =
On the relationship between cyclic and hierarchical three-species predator-prey systems and the two-species Lotka-Volterra model , author =. The European Physical Journal B , volume =. 2012 , publisher =
work page 2012
-
[73]
Journal of Physics A: Mathematical and Theoretical (J
Population oscillations in spatial stochastic Lotka--Volterra models: a field-theoretic perturbational analysis , author =. Journal of Physics A: Mathematical and Theoretical (J. Phys. A) , volume =. 2012 , publisher =
work page 2012
-
[74]
Ecological communities from random generalized Lotka--Volterra dynamics with nonlinear feedback , author =. Physical Review E , volume =. 2020 , publisher =
work page 2020
-
[75]
Journal of the Royal Society Interface , volume =
Cyclic dominance in evolutionary games: a review , author =. Journal of the Royal Society Interface , volume =. 2014 , publisher =
work page 2014
-
[76]
Royal Society Open Science , volume =
Interplay between competitive and cooperative interactions in a three-player pathogen system , author =. Royal Society Open Science , volume =. 2020 , publisher =
work page 2020
-
[77]
Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , volume =
Competing epidemics on complex networks , author =. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , volume =. 2011 , publisher =
work page 2011
-
[78]
Theoretical Biology and Medical Modelling , volume =
Epidemic cycling in a multi-strain SIRS epidemic network model , author =. Theoretical Biology and Medical Modelling , volume =. 2016 , publisher =
work page 2016
-
[79]
Theory of Evolutionary Computation:
Johannes Lengler , title =. Theory of Evolutionary Computation:. 2020 , publisher =
work page 2020
-
[80]
Artificial Intelligence , year =
Jun He and Xin Yao , title =. Artificial Intelligence , year =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.