Independent Sets in a Percolated Hypercube
Back to main page
Back to selected works
Independent sets in a graph are sets of vertices which contain no neighbors.
They are important from a computer science perspective as counting the number of independent sets and finding the largest independent sets in general graphs are both NP-hard problems.
Additionally, they are used in the hard-core model of a gas in statistical mechanics.
In the '80s, Sapozhenko's graph container method was developed in order to approximately count the number of independent sets in the Boolean hypercube, and more recently interest has developed
in a disordered media version of this problem, where the edges of the hypercube are removed independently with probability \(p\) each.
In our paper Gaussian to log-normal transition for independent sets in a percolated hypercube
(joint work with Mriganka Basu Roy Chowdhury and Shirshendu Ganguly), we develop a new probabilistic framework to study the number of independent sets in this random graph.
We prove that this random variable obeys a central limit theorem when \(p>\tfrac{2}{3}\), and has a log-normal distributional limit when \(p=\tfrac{2}{3}\).
Moreover, we use our techniques to extract information about typical geometric structure of independent sets in a percolated hypercube for all \(p\geq\tfrac{2}{3}\).