On expectations and variances in the hard-core model on bounded degree graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908546230124544 |
|---|---|
| author | Davies, Ewan Sandhu, Juspreet Singh Tan, Brian |
| author_facet | Davies, Ewan Sandhu, Juspreet Singh Tan, Brian |
| contents | We extend the study of the occupancy fraction of the hard-core model in two novel directions. One direction gives a tight lower bound in terms of individual vertex degrees, extending work of Sah, Sawhney, Stoner and Zhao which bounds the partition function. The other bounds the variance of the size of an independent set drawn from the model, which is strictly stronger than bounding the occupancy fraction.
In the setting of triangle-free graphs, we make progress on a recent conjecture of Buys, van den Heuvel and Kang on extensions of Shearer's classic bounds on the independence number to the occupancy fraction of the hard-core model. Sufficiently strong lower bounds on both the expectation and the variance in triangle-free graphs have the potential to improve the known bounds on the off-diagonal Ramsey number $R(3,t)$, and to shed light on the algorithmic barrier one observes for independent sets in sparse random graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13396 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On expectations and variances in the hard-core model on bounded degree graphs Davies, Ewan Sandhu, Juspreet Singh Tan, Brian Combinatorics Discrete Mathematics We extend the study of the occupancy fraction of the hard-core model in two novel directions. One direction gives a tight lower bound in terms of individual vertex degrees, extending work of Sah, Sawhney, Stoner and Zhao which bounds the partition function. The other bounds the variance of the size of an independent set drawn from the model, which is strictly stronger than bounding the occupancy fraction. In the setting of triangle-free graphs, we make progress on a recent conjecture of Buys, van den Heuvel and Kang on extensions of Shearer's classic bounds on the independence number to the occupancy fraction of the hard-core model. Sufficiently strong lower bounds on both the expectation and the variance in triangle-free graphs have the potential to improve the known bounds on the off-diagonal Ramsey number $R(3,t)$, and to shed light on the algorithmic barrier one observes for independent sets in sparse random graphs. |
| title | On expectations and variances in the hard-core model on bounded degree graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2505.13396 |