We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting $\lambda(G)$ denote the spectral radius (maximum eigenvalue) of $G$, we prove that the critical probability is at $1/\lambda(G)$: above this probability there is typically a component of order $\Omega(\lambda(G))$, whereas below it all components are of order at most $O(\sqrt{|G|})$. These results in particular confirm a conjecture of Krivelevich and Samotij about percolation on graphs of a given average degree, and vastly extend theorems of Bollob\'as, Borgs, Chayes, and Riordan, who proved analogous results but only for dense graphs. Our theorems are optimal in many regimes, and also demonstrate that percolation has an unexpectedly subtle behaviour on graphs whose spectral radius is roughly the square root of their maximum degree.
We introduce a conjecture for Bernoulli bond percolation on finite graphs. Roughly speaking, it asserts that if each boundary vertex is associated with a highly probable event that is increasing with respect to the percolation configuration, then, conditionally on the origin being connected to the boundary, the origin...
For a tree $T$, let $g(T)=\lambda_1(T)-\lambda_2(T)$ be the difference between its two largest adjacency eigenvalues. A balanced double comet is obtained by attaching equally many leaves to the two endpoints of a path. Jovovi\'c, Koledin and Stani\'c conjectured that such a tree attains the minimum adjacency spectral g...
We consider the weight-dependent random connection model on a Poisson point process of intensity $\lambda$ on $\mathbb{R}\times(0,1)$ in which the vertices $(x,t)$ and $(y,s)$ are joined precisely when $(t\vee s)|x-y|\le\beta$. Points at distance $d$ are joined with probability $\min(1,\beta/d)^2$, the critical decay o...
We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph $G(n,p)$. Here we aim for first-order asymptotics for the quantity $\mathbb{P}[X=k]$ with $X$ the number of triangles in $G(n,p)$ and $0 \le k \le (1-\epsilon) \mathbb{E}X$, in the sparse...
Jade Lintott, Will Perkins, Corrine Yap· 0 citations
For a finite graph $G$ on $n$ vertices, let $\eta(G)$ denote the least order of a finite abelian group $\Gamma$ for which $G$ is an induced subgraph of some Cayley graph of $\Gamma$. Babai and S\'os (1985) settled the worst-case order of magnitude: it is $\Theta(n^2)$. We treat $\eta$ instead as an invariant of the ind...
Consider an infinite edge-weighted graph satisfying an isoperimetric inequality of the type $\|\partial A\|\geq C|A|^\alpha$ for some $\alpha,C>0$, where $\|\partial A\|$ denotes the weighted size of the edge boundary of $A$. We prove that, for $C$ large enough depending on $\alpha$, if each edge is open independently...
Ivailo Hartarsky, Franco Severo, Augusto Teixeira· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
