RSB bounds on the maximum cut
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908423719747584 |
|---|---|
| author | Harangi, Viktor |
| author_facet | Harangi, Viktor |
| contents | In the context of random regular graphs, the size of the maximum cut is probably the second most studied graph parameter after the independence ratio. Zdeborová and Boettcher used the cavity method, a non-rigorous statistical physics technique, to predict one-step replica symmetry breaking (1-RSB) formulas. Coja-Ohglan et al. confirmed these predictions as rigorous upper bounds using the interpolation method. While these upper bounds were not expected to be exact, they may be very close to the true values.
In this paper, we establish 2-RSB upper bounds and fine-tune their parameters to beat the aforementioned 1-RSB bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21296 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | RSB bounds on the maximum cut Harangi, Viktor Combinatorics Probability 05C80, 05C70 In the context of random regular graphs, the size of the maximum cut is probably the second most studied graph parameter after the independence ratio. Zdeborová and Boettcher used the cavity method, a non-rigorous statistical physics technique, to predict one-step replica symmetry breaking (1-RSB) formulas. Coja-Ohglan et al. confirmed these predictions as rigorous upper bounds using the interpolation method. While these upper bounds were not expected to be exact, they may be very close to the true values. In this paper, we establish 2-RSB upper bounds and fine-tune their parameters to beat the aforementioned 1-RSB bounds. |
| title | RSB bounds on the maximum cut |
| topic | Combinatorics Probability 05C80, 05C70 |
| url | https://arxiv.org/abs/2506.21296 |