Independent sets in random subgraphs of the hypercube

MaRDI QIDQ6388383zbMATH OpenFDO

Authors Gal Kronenberg, Yinon Spinka

Publication date 16 January 2022

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Let $Q_{d,p}$ be the random subgraph of the $d$-dimensional hypercube ${0,1}^d$, where each edge is retained independently with probability $p$. We study the asymptotic number of independent sets in $Q_{d,p}$ as $doinfty$ for a wide range of parameters $p$, including values of $p$ tending to zero as fast as $fracClogd{d}^{1/3}$, constant values of $p$, and values of $p$ tending to one. The results extend to the hardcore model on $Q_{d,p}$, and are obtained by studying the closely related antiferromagnetic Ising model on the hypercube, which can be viewed as a positive-temperature hardcore model on the hypercube. These results generalize previous results by Galvin, Jenssen and Perkins on the hard-core model on the hypercube, corresponding to the case $p=1$, which extended Korshunov and Sapozhenko's classical result on the asymptotic number of independent sets in the hypercube.

This page was built for publication: Independent sets in random subgraphs of the hypercube

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