Slightly subcritical hypercube percolation

DOI10.1002/RSA.20853zbMATH Open1436.60081arXiv1612.01772OpenAlexW2561196309WikidataQ128037618 ScholiaQ128037618MaRDI QIDQ5113949FDOQ5113949

Tim Hulshof, Asaf Nachmias

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study bond percolation on the hypercube ${0,1}^m$ in the slightly subcritical regime where $p=p_c(1-varepsilo{n}_m)$ and $varepsilo{n}_m=o(1)$ but $varepsilo{n}_{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 $Thetaleft(varepsilo{n}_m^{-2}log(varepsilo{n}_m^3{2}^m)ight)$, that the maximal diameter of all clusters is $(1+o(1))varepsilo{n}_m^{-1}log(varepsilo{n}_m^3{2}^m)$, and that the maximal mixing time of all clusters is $Thetaleft(varepsilo{n}_m^{-3}lo{g}^2(varepsilo{n}_m^3{2}^m)ight)$. 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.

Full work available at URL: https://arxiv.org/abs/1612.01772

zbMATH Keywords

hypercubediametermixing timepercolationsubcriticality

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cited In (10)

• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Weak Multiplex Percolation
• Preferential attachment without vertex growth: emergence of the giant component
• The component structure of dense random subgraphs of the hypercube
• High-dimensional near-critical percolation and the torus plateau
• Slightly supercritical percolation on non‐amenable graphs I: The distribution of finite clusters
• Majority Bootstrap Percolation on the Hypercube
• Random graph asymptotics on high-dimensional tori
• The giant component after percolation of product graphs
• Self‐avoiding walk on the hypercube

   Recommendations

• Hypercube percolation 👍 👎
• Weakly constrained-degree percolation on the hypercubic lattice 👍 👎
• Subcritical regimes in some models of continuum percolation 👍 👎
• Supercritical site percolation on the hypercube: small components are small 👍 👎
• Percolation in the hyperbolic plane 👍 👎
• Saturation in the Hypercube and Bootstrap Percolation 👍 👎
• Bernoulli hyperplane percolation 👍 👎
• Critical percolation in finite geometries 👍 👎
• Bootstrap percolation on the hypercube 👍 👎

This page was built for publication: Slightly subcritical hypercube percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113949)