THE DENSEST SUBGRAPH PROBLEM IN SPARSE RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Anantharam, Venkat; Salez, Justin
• 署名单位: University of California System; University of California Berkeley; Universite Paris Cite
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1091
• 发表日期: 2016
• 页码: 305-327
• 关键词: belief propagation; enumeration; matchings

摘要

We determine the asymptotic behavior of the maximum subgraph density of large random graphs with a prescribed degree sequence. The result applies in particular to the Erdos-Renyi model, where it settles a conjecture of Hajek [IEEE Trans. Inform. Theory 36 (1990) 1398-1414]. Our proof consists in extending the notion of balanced loads from finite graphs to their local weak limits, using unimodularity. This is a new illustration of the objective method described by Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].