Slightly subcritical hypercube percolation

DOI10.1002/RSA.20853MaRDI QIDQ5113949zbMATH OpenOpenAlexWikidataFDO

Authors Tim Hulshof, Asaf Nachmias

Publication date 19 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

diameterhypercubemixing timepercolationsubcriticality

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

• Weakly constrained-degree percolation on the hypercubic lattice
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Preferential attachment without vertex growth: emergence of the giant component
• Unlacing hypercube percolation: a survey
• Majority Bootstrap Percolation on the Hypercube
• Weak Multiplex Percolation
• Hypercube percolation
• The giant component after percolation of product graphs
• The component structure of dense random subgraphs of the hypercube
• Self‐avoiding walk on the hypercube
• Slightly supercritical percolation on non‐amenable graphs I: The distribution of finite clusters
• Supercritical site percolation on the hypercube: small components are small
• High-dimensional near-critical percolation and the torus plateau
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• A note about critical percolation on finite graphs
• Counting independent sets in percolated graphs via the Ising model
• Random graph asymptotics on high-dimensional tori

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)