Phase transitions of extremal cuts for the configuration model

S. Dhara; D. Mukherjee; S. Sen

Phase transitions of extremal cuts for the configuration model

S. Dhara
, D. Mukherjee
, S. Sen

Stochastic Operations Research

Research output: Contribution to journal › Article › Academic

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

Original language	English
Number of pages	26
Journal	arXiv
Issue number	arXiv:1611.03075
Publication status	Published - 9 Nov 2016

Access to Document

Authors versionFinal author version , 469 KB

Cite this

@article{c0092f173e3643cf8b34e6ddedcfab08,

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

author = "S. Dhara and D. Mukherjee and S. Sen",

year = "2016",

month = nov,

day = "9",

language = "English",

journal = "arXiv",

publisher = "Cornell University",

number = " arXiv:1611.03075 ",

}

TY - JOUR

T1 - Phase transitions of extremal cuts for the configuration model

AU - Dhara, S.

AU - Mukherjee, D.

AU - Sen, S.

PY - 2016/11/9

Y1 - 2016/11/9

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

M3 - Article

JO - arXiv

JF - arXiv

IS - arXiv:1611.03075

ER -

Phase transitions of extremal cuts for the configuration model

Abstract

Access to Document

Fingerprint

Cite this