Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.05149 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917464957255680 |
|---|---|
| author | Davies, Ewan Sandhu, Juspreet Singh Seo, Jaehyeon Tan, Brian |
| author_facet | Davies, Ewan Sandhu, Juspreet Singh Seo, Jaehyeon Tan, Brian |
| contents | We present new degree-sequence lower bounds on the expected size of an independent set from the hard-core model. For arbitrary graphs, we establish a multivariate lower bound inspired by a conjecture of the first author and Kang and a recent bound on the multivariate partition function due to Lee and the third author. By applying a novel spectral analysis to the local occupancy linear program, our method successfully bypasses the convergence radius limitations of the cluster expansion and avoids induction. For graphs with bounded local maximum average degree, including triangle-free graphs, we prove a univariate bound extending prior work by a subset of the authors. In both cases our bounds require the fugacities to be upper bounded by $c/Δ$ where $Δ$ is the maximum degree of the graph and $c$ is an absolute constant depending on the setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05149 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Degree-sequence bounds for independent sets via multivariate local occupancy Davies, Ewan Sandhu, Juspreet Singh Seo, Jaehyeon Tan, Brian Combinatorics We present new degree-sequence lower bounds on the expected size of an independent set from the hard-core model. For arbitrary graphs, we establish a multivariate lower bound inspired by a conjecture of the first author and Kang and a recent bound on the multivariate partition function due to Lee and the third author. By applying a novel spectral analysis to the local occupancy linear program, our method successfully bypasses the convergence radius limitations of the cluster expansion and avoids induction. For graphs with bounded local maximum average degree, including triangle-free graphs, we prove a univariate bound extending prior work by a subset of the authors. In both cases our bounds require the fugacities to be upper bounded by $c/Δ$ where $Δ$ is the maximum degree of the graph and $c$ is an absolute constant depending on the setting. |
| title | Degree-sequence bounds for independent sets via multivariate local occupancy |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.05149 |