Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs

被引:12
作者
Abert, Miklos [1 ]
Hubai, Tamas [1 ,2 ]
机构
[1] Hungarian Acad Sci, Alfred Renyi Inst Math, H-1053 Budapest, Hungary
[2] Eotvos Lorand Univ, Dept Comp Sci, H-1117 Budapest, Hungary
关键词
PARTITION-FUNCTION; POTTS-MODEL; ZEROS; POLYNOMIALS;
D O I
10.1007/s00493-014-3066-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We define the chromatic measure of a finite simple graph as the uniform distribution on its chromatic roots. We show that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. As a corollary, for a convergent sequence of finite graphs, we prove that the normalized log of the chromatic polynomial converges to an analytic function outside a bounded disc. This generalizes a recent result of Borgs, Chayes, Kahn and Lovasz, who proved convergence at large enough positive integers and answers a question of Borgs. Our methods also lead to explicit estimates on the number of proper colorings of graphs with large girth.
引用
收藏
页码:127 / 151
页数:25
相关论文
共 13 条
[1]  
[Anonymous], PROBAB THEORY RELAT
[2]  
[Anonymous], 2012, C PUBLICATIONS
[3]   Counting Without Sampling: Asymptotics of the Log-Partition Function for Certain Statistical Physics Models [J].
Bandyopadhyay, Antar ;
Gamarnik, David .
RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (04) :452-479
[4]  
Benjamini I., 2001, Electronic J. Probab, V6
[5]   Absence of zeros for the chromatic polynomial on bounded degree graphs [J].
Borgs, C .
COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (1-2) :63-74
[6]   Asymptotic enumeration of spanning trees [J].
Lyons, R .
COMBINATORICS PROBABILITY & COMPUTING, 2005, 14 (04) :491-522
[7]  
Mergelyan S.N., 1952, Usp. Mat. Nauk., V7, P31
[8]   Potts model on infinite graphs and the limit of chromatic polynomials [J].
Procacci, A ;
Scoppola, B ;
Gerasimov, V .
COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2003, 235 (02) :215-231
[9]   Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models [J].
Salas, Jesus ;
Sokal, Alan D. .
JOURNAL OF STATISTICAL PHYSICS, 2009, 135 (02) :279-373
[10]  
Sokal A. D., 2005, Surveys Combinatorics, V327, P173, DOI DOI 10.1017/CB09780511734885.009