Phase transitions of extremal cuts for the configuration model

Souvik Dhara, Debankur Mukherjee, Subhabrata Sen

Research output: Contribution to journalArticleAcademicpeer-review

45 Downloads (Pure)

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 languageEnglish
Article number86
Number of pages29
JournalElectronic Journal of Probability
Volume22
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • Fixed degree sequence
  • Max-cut
  • Minimum bisection
  • Phase transition

Fingerprint

Dive into the research topics of 'Phase transitions of extremal cuts for the configuration model'. Together they form a unique fingerprint.

Cite this