Phase transitions of extremal cuts for the configuration model

Souvik Dhara, Debankur Mukherjee, Subhabrata Sen

    Research output: Contribution to journalArticleAcademicpeer-review

    33 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