Abstract
The k-section width and the Max-Cut for the configuration model are shown to exhibit phase transitions according to the values of certain parameters of the asymptotic degree distribution. These transitions mirror those observed on Erdős-Rényi random graphs, established by Luczak and McDiarmid (2001), and Coppersmith et al. (2004), respectively.
Original language | English |
---|---|
Article number | 86 |
Number of pages | 29 |
Journal | Electronic Journal of Probability |
Volume | 22 |
DOIs | |
Publication status | Published - 1 Jan 2017 |
Keywords
- Fixed degree sequence
- Max-cut
- Minimum bisection
- Phase transition