Phase transitions of extremal cuts for the configuration model

Souvik Dhara; Debankur Mukherjee; Subhabrata Sen

doi:10.1214/17-EJP109

Phase transitions of extremal cuts for the configuration model

Souvik Dhara, Debankur Mukherjee, Subhabrata Sen

Stochastic Operations Research

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Article number	86
Number of pages	29
Journal	Electronic Journal of Probability
Volume	22
DOIs	https://doi.org/10.1214/17-EJP109
Publication status	Published - 1 Jan 2017

Keywords

Fixed degree sequence
Max-cut
Minimum bisection
Phase transition

Access to Document

10.1214/17-EJP109

Publishers VersionFinal published version, 630 KB

Cite this

@article{abb19677de8d436bb2d75905100dac92,

title = "Phase transitions of extremal cuts for the configuration model",

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{\H o}s-R{\'e}nyi random graphs, established by Luczak and McDiarmid (2001), and Coppersmith et al. (2004), respectively.",

keywords = "Fixed degree sequence, Max-cut, Minimum bisection, Phase transition",

author = "Souvik Dhara and Debankur Mukherjee and Subhabrata Sen",

year = "2017",

month = jan,

day = "1",

doi = "10.1214/17-EJP109",

language = "English",

volume = "22",

journal = "Electronic Journal of Probability",

issn = "1083-6489",

publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Phase transitions of extremal cuts for the configuration model

AU - Dhara, Souvik

AU - Mukherjee, Debankur

AU - Sen, Subhabrata

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

KW - Fixed degree sequence

KW - Max-cut

KW - Minimum bisection

KW - Phase transition

UR - http://www.scopus.com/inward/record.url?scp=85049184493&partnerID=8YFLogxK

U2 - 10.1214/17-EJP109

DO - 10.1214/17-EJP109

M3 - Article

AN - SCOPUS:85049184493

VL - 22

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

M1 - 86

ER -

Phase transitions of extremal cuts for the configuration model

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this