RSB bounds on the maximum cut
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Improved Replica Bounds for the Independence Ratio of Random Regular GraphsJournal of Statistical Physics, 2023
- The number of solutions for random regular NAE-SATProbability Theory and Related Fields, 2021
- Lower Bounds on the Chromatic Number of Random GraphsCombinatorica, 2021
- Replica Bounds by Combinatorial Interpolation for Diluted Spin SystemsJournal of Statistical Physics, 2018
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphsThe Annals of Probability, 2013
- A conjecture on the maximum cut and bisection width in random regular graphsJournal of Statistical Mechanics: Theory and Experiment, 2010
- Replica bounds for diluted non-Poissonian spin systemsJournal of Physics A: General Physics, 2003
- Replica Bounds for Optimization Problems and Diluted Spin SystemsJournal of Statistical Physics, 2003