Search

In this paper we conduct a simulation study of the spread of an epidemic like COVID-19 with temporary immunity on finite spatial and non-spatial network models. In particular, we assume that an epidemic spreads stochastically on a scale-free network and that each infected individual in the network gains a temporary immunity after its infectious period is over. After the temporary immunity period is over, the individual becomes susceptible to the virus again. When the underlying contact network is embedded in Euclidean geometry, we model three different intervention strategies that aim to control the spread of the epidemic: social distancing, restrictions on travel, and restrictions on maximal number of social contacts per node. Our first finding is that on a finite network, a long enough average immunity period leads to extinction of the pandemic after the first peak, analogous to the concept of "herd immunity". For each model, there is a critical average immunity length $L_c$ above which this happens. Our second finding is that all three interventions manage to flatten the first peak (the travel restrictions most efficiently), as well as decrease the critical immunity length $L_c$, but elongate the epidemic. However, when the average immunity length $L$ is shorter than $L_c$, the price for the flattened first peak is often a high second peak: for limiting the maximal number of contacts, the second peak can be as high as 1/3 of the first peak, and twice as high as it would be without intervention. Thirdly, interventions introduce oscillations into the system and the time to reach equilibrium is, for almost all scenarios, much longer. We conclude that network-based epidemic models can show a variety of behaviors that are not captured by the continuous compartmental models., Comment: 17 pages text, 27 figures of which 22 in the appendix

Let $\mathcal{T}$ be a supercritical Galton-Watson tree with a bounded offspring distribution that has mean $\mu >1$, conditioned to survive. Let $\varphi_{\mathcal{T}}$ be a random embedding of $\mathcal{T}$ into $\mathbb{Z}^d$ according to a simple random walk step distribution. Let $\mathcal{T}_p$ be percolation on $\mathcal{T}$ with parameter $p$, and let $p_c = \mu^{-1}$ be the critical percolation parameter. We consider a random walk $(X_n)_{n \ge 1}$ on $\mathcal{T}_p$ and investigate the behavior of the embedded process $\varphi_{\mathcal{T}_p}(X_n)$ as $n\to \infty$ and simultaneously, $\mathcal{T}_p$ becomes critical, that is, $p=p_n\searrow p_c$. We show that when we scale time by $n/(p_n-p_c)^3$ and space by $\sqrt{(p_n-p_c)/n}$, the process $(\varphi_{\mathcal{T}_p}(X_n))_{n \ge 1}$ converges to a $d$-dimensional Brownian motion. We argue that this scaling can be seen as an interpolation between the scaling of random walk on a static random tree and the anomalous scaling of processes in critical random environments., Comment: 47 pages, 1 figure

A geometric $t$-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most $t$ times the Euclidean distance between the points. Informally, a spanner is $\mathcal{O}(k)$-robust if deleting $k$ vertices only harms $\mathcal{O}(k)$ other vertices. We show that on any one-dimensional set of $n$ points, for any $\varepsilon>0$, there exists an $\mathcal{O}(k)$-robust $1$-spanner with $\mathcal{O}(n^{1+\varepsilon})$ edges. Previously it was only known that $\mathcal{O}(k)$-robust spanners with $\mathcal{O}(n^2)$ edges exists and that there are point sets on which any $\mathcal{O}(k)$-robust spanner has $\Omega(n\log{n})$ edges., Comment: 6 pages, 6 figures

In this note we study the phase transition for percolation on quasi-transitive graphs with quasi-transitively inhomogeneous edge-retention probabilities. A quasi-transitive graph is an infinite graph with finitely many different "types" of edges and vertices. We prove that the transition is sharp almost everywhere, i.e., that in the subcritical regime the expected cluster size is finite, and that in the subcritical regime the probability of the one-arm event decays exponentially. Our proof extends the proof of sharpness of the phase transition for homogeneous percolation on vertex-transitive graphs by Duminil-Copin and Tassion [Comm. Math. Phys., 2016], and the result generalizes previous results of Antunovi\'c and Veseli\'c [J. Stat. Phys., 2008] and Menshikov [Dokl. Akad. Nauk 1986]., Comment: 9 pages

We identify the scaling limit of the backbone of the high-dimensional incipient infinite cluster (IIC), both in the finite-range and the long-range setting. In the finite-range setting, this scaling limit is Brownian motion, in the long-range setting, it is a stable motion. The proof relies on a novel lace expansion that keeps track of the number of pivotal bonds., Comment: This is a thorough revision of a previous submission, arXiv:1301.3486v2, which was retracted because of an error in the proof. The results presented here are the same as those claimed in arXiv:1301.3486v2 (modulo a few details), but large parts of the proof are different. 86 pages, 46 figures

The Hamming graph $H(d,n)$ is the Cartesian product of $d$ complete graphs on $n$ vertices. Let $m=d(n-1)$ be the degree and $V = n^d$ be the number of vertices of $H(d,n)$. Let $p_c^{(d)}$ be the critical point for bond percolation on $H(d,n)$. We show that, for $d \in \mathbb N$ fixed and $n \to \infty$, \begin{equation*} p_c^{(d)}= \dfrac{1}{m} + \dfrac{2d^2-1}{2(d-1)^2}\dfrac{1}{m^2} + O(m^{-3}) + O(m^{-1}V^{-1/3}), \end{equation*} which extends the asymptotics found in \cite{BorChaHofSlaSpe05b} by one order. The term $O(m^{-1}V^{-1/3})$ is the width of the critical window. For $d=4,5,6$ we have $m^{-3} = O(m^{-1}V^{-1/3})$, and so the above formula represents the full asymptotic expansion of $p_c^{(d)}$. In \cite{FedHofHolHul16a} \st{we show that} this formula is a crucial ingredient in the study of critical bond percolation on $H(d,n)$ for $d=2,3,4$. The proof uses a lace expansion for the upper bound and a novel comparison with a branching random walk for the lower bound. The proof of the lower bound also yields a refined asymptotics for the susceptibility of a subcritical Erd\H{o}s-R\'enyi random graph., Comment: 32 pages, 3 figures

We study bond percolation on the hypercube $\{0,1\}^m$ in the slightly subcritical regime where $p = p_c (1-\varepsilon_m)$ and $\varepsilon_m = o(1)$ but $\varepsilon_m \gg 2^{-m/3}$ and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality $\Theta\left(\varepsilon_m^{-2} \log(\varepsilon_m^3 2^m)\right)$, that the maximal diameter of all clusters is $(1+o(1)) \varepsilon_m^{-1} \log(\varepsilon_m^3 2^m)$, and that the maximal mixing time of all clusters is $\Theta\left(\varepsilon_m^{-3} \log^2(\varepsilon_m^3 2^m)\right)$. These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high-dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions., Comment: 38 pages

We study the critical probability for the metastable phase transition of the two-dimensional anisotropic bootstrap percolation model with $(1,2)$-neighbourhood and threshold $r = 3$. The first order asymptotics for the critical probability were recently determined by the first and second authors. Here we determine the following sharp second and third order asymptotics: \[ p_c\big( [L]^2,\mathcal{N}_{(1,2)},3 \big) \; = \; \frac{(\log \log L)^2}{12\log L} \, - \, \frac{\log \log L \, \log \log \log L}{ 3\log L} + \frac{\left(\log \frac{9}{2} + 1 \pm o(1) \right)\log \log L}{6\log L}. \] We note that the second and third order terms are so large that the first order asymptotics fail to approximate $p_c$ even for lattices of size well beyond $10^{10^{1000}}$., Comment: 46 pages

Scale-free percolation is a percolation model on $\mathbb{Z}^d$ which can be used to model real-world networks. We prove bounds for the graph distance in the regime where vertices have infinite degrees. We fully characterize transience vs. recurrence for dimension 1 and 2 and give sufficient conditions for transience in dimension 3 and higher. Finally, we show the existence of a hierarchical structure for parameters where vertices have degrees with infinite variance and obtain bounds on the cluster density., Comment: Revised Definition 2.5 and an argument in Section 6, results are unchanged. Correction of minor typos. 29 pages, 7 figures

We study the connectivity of random subgraphs of the $d$-dimensional Hamming graph $H(d, n)$, which is the Cartesian product of $d$ complete graphs on $n$ vertices. We sample the random subgraph with an i.i.d.\ Bernoulli bond percolation on $H(d,n)$ with parameter $p$. We identify the window of the transition: when $ np- \log n \to - \infty$ the probability that the graph is connected goes to $0$, while when $ np- \log n \to + \infty$ it converges to $1$. We also investigate the connectivity probability inside the critical window, namely when $ np- \log n \to t \in \mathbb{R}$. We find that the threshold does not depend on $d$, unlike the phase transition of the giant connected component the Hamming graph (see [Bor et al, 2005]). Within the critical window, the connectivity probability does depend on d. We determine how., Comment: 10 pages, no figures

Consider a long-range percolation model on $\mathbb{Z}^d$ where the probability that an edge $\{x,y\} \in \mathbb{Z}^d \times \mathbb{Z}^d$ is open is proportional to $\|x-y\|_2^{-d-\alpha}$ for some $\alpha >0$ and where $d > 3 \min\{2,\alpha\}$. We prove that in this case the one-arm exponent equals $ \min\{4,\alpha\}/2$. We also prove that the maximal displacement for critical branching random walk scales with the same exponent. This establishes that both models undergo a phase transition in the parameter $\alpha$ when $\alpha =4$., Comment: 28 pages, 1 figure, 1 appendix

We identify the scaling limit of the backbone of the high-dimensional incipient infinite cluster (IIC), both in the long- as well as in the finite-range setting. In the finite-range setting, this scaling limit is Brownian motion, in the long-range setting, it is a stable motion. The proof relies on a novel lace expansion for percolation that resembles the original expansion for self-avoiding walks by Brydges and Spencer in 1985. This expansion is interesting in its own right., Comment: Withdrawn because certain correction terms that arise in the Lace expansion of Section 3 were not identified and taken into account in the subsequent derivation. A new version with these correction terms included is in preparation

We study the asymptotic behavior the exit times of random walk from Euclidean balls around the origin of the incipient infinite cluster in a manner inspired by [26]. We do this by obtaining bounds on the effective resistance between the origin and the boundary of these Euclidean balls. We show that the geometric properties of long-range percolation clusters are significantly different from those of finite-range clusters. We also study the behavior of random walk on the backbone of the IIC and we prove that the Alexander-Orbach conjecture holds for the incipient infinite cluster in high dimensions, both for long-range percolation and for finite-range percolation., Comment: 48 pages. Main difference with previous version: some proofs have been strengthened to work under milder assumptions. To appear in Commun. Math. Phys

The incipient infinite cluster (IIC) measure is the percolation measure at criticality conditioned on the cluster of the origin to be infinite. Using the lace expansion, we construct the IIC measure for high-dimensional percolation models in three different ways, extending previous work by the second author and Jarai. We show that each construction yields the same measure, indicating that the IIC is a robust object. Furthermore, our constructions apply to spread-out versions of both finite-range and long-range percolation models. We also obtain estimates on structural properties of the IIC, such as the volume of the intersection between the IIC and Euclidean balls., Comment: 47 pages, 7 figures

In this note we analyze an anisotropic, two-dimensional bootstrap percolation model introduced by Gravner and Griffeath. We present upper and lower bounds on the finite-size effects. We discuss the similarities with the semi-oriented model introduced by Duarte., Comment: Key words: Bootstrap percolation, anisotropy, finite-size effects