EUVIMEDEUVIMED entdecken
Crossref

Gaussian to Log‐Normal Transition for Independent Sets in a Percolated Hypercube

Mriganka Basu Roy Chowdhury, Shirshendu Ganguly, Vilas Winstein

Random Structures & Algorithms · 2026-12 · 69 (4)

DOI: 10.1002/rsa.70101 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 05.11.2026. Verfasst von Mriganka Basu Roy Chowdhury und 2 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Independent sets in graphs, that is, subsets of vertices where no two are adjacent, have long been studied, particularly as a model for hard‐core gas in various settings such as lattices and random graphs. The ‐dimensional hypercube, , with the nearest neighbor structure, has been a particularly appealing choice for the base graph, owing in part to its many symmetries, as well as its connections to binary codes. Results go back to the work of Korshunov and Sapozhenko who proved sharp results on the count of such sets as well as structure theorems for random samples drawn uniformly. This was later extended by Galvin to the hard‐core model, where the probability of an independent set is proportional to where is the fugacity . Of much interest is the behavior of such Gibbs measures driven by external randomness. In this direction, Kronenberg and Spinka (2022) initiated the study of the count and geometry of independent sets in a random subgraph of the hypercube obtained by considering an instance of bond percolation with probability Relying on tools from statistical mechanics, such as polymer decompositions and cluster expansions, they obtained a detailed understanding of the moments of the partition function, say of the hard‐core model on such random graphs and consequently deduced certain fluctuation information, as well as posed a series of interesting questions. A particularly important outcome of their computations is that, in the uniform case, there is a natural phase transition at where transitions from being concentrated for to not concentrated at in the sense that the second moment transitions from being much smaller than the square of the expectation to being comparable at , to being exponentially larger for In this article, developing a probabilistic framework, as well as relying on certain cluster expansion inputs from Kronenberg and Spinka (2022), we present a detailed picture of both the fluctuations of as well as the geometry of a randomly sampled independent set. In particular, we establish that properly centered and scaled, converges to a standard Gaussian for and to a sum of two i.i.d. log‐normals at A particular step in the proof which could be of independent interest involves a non‐uniform birthday problem for which collisions emerge at establishing this as another natural transition point. Finally, our results also generalize to the hard‐core model with parameter establishing a similar transition at

Zitieren

APA

Chowdhury, M. B. R., Ganguly, S., & Winstein, V. (2026). Gaussian to Log‐Normal Transition for Independent Sets in a Percolated Hypercube. Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70101

Vancouver

Chowdhury MBR, Ganguly S, Winstein V. Gaussian to Log‐Normal Transition for Independent Sets in a Percolated Hypercube. Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70101

BibTeX
@article{Chowdhury2026,
  author = {Chowdhury, Mriganka Basu Roy and Ganguly, Shirshendu and Winstein, Vilas},
  title = {Gaussian to Log‐Normal Transition for Independent Sets in a Percolated Hypercube},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {69},
  number = {4},
  doi = {10.1002/rsa.70101}
}
Kostenlos starten →