Hypergraph coloring up to condensation

被引：14

作者：

Ayre, Peter ^{[1
]}

Coja-Oghlan, Amin ^{[2
]}

Greenhill, Catherine ^{[2
]}

机构：

[1] UNSW Sydney, Sch Math & Stat, Sydney, NSW 2052, Australia

[2] Goethe Univ, Math Inst, D-60325 Frankfurt, Germany

来源：

RANDOM STRUCTURES & ALGORITHMS | 2019年 / 54卷 / 04期

基金：

欧洲研究理事会; 澳大利亚研究理事会;

关键词：

coloring; chromatic number; hypergraphs; random hypergraphs; RANDOM K-SAT; CHROMATIC NUMBER; RANDOM GRAPHS;

D O I：

10.1002/rsa.20824

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the q-colorability threshold in random k-uniform hypergraphs up to an additive error of ln2+epsilon q, where limq ->infinity epsilon q=0. The new lower bound on the threshold matches the "condensation phase transition" predicted by statistical physics considerations [Krzakala et al., PNAS 2007].

引用

页码：615 / 652

页数：38

共 27 条

[1] The two possible values of the chromatic number of a random graph [J].

Achlioptas, D ;

Naor, A .

ANNALS OF MATHEMATICS, 2005, 162 (03) :1335-1351

[2] Rigorous location of phase transitions in hard optimization problems [J].

Achlioptas, D ;

Naor, A ;

Peres, Y .

NATURE, 2005, 435 (7043) :759-764

[3]

Achlioptas D., 2002, Randomization and Approximation Techniques in Computer Science. 6th International Workshop, RANDOM 2002. Proceedings (Lecture Notes in Computer Science Vol.2483), P78

[4] Random k-SAT:: Two moments suffice to cross a sharp threshold [J].

Achlioptas, Dimitris ;

Moore, Cristopher .

SIAM JOURNAL ON COMPUTING, 2006, 36 (03) :740-762

[5] Algorithmic Barriers from Phase Transitions [J].

Achlioptas, Dimitris ;

Coja-Oghlan, Amin .

PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, :793-+

[6] The concentration of the chromatic number of random graphs [J].

Alon, N ;

Krivelevich, M .

COMBINATORICA, 1997, 17 (03) :303-313

[7]

[Anonymous], 2012, P 23 ANN ACM SIAM S

[8] THE CHROMATIC NUMBER OF RANDOM GRAPHS [J].

BOLLOBAS, B .

COMBINATORICA, 1988, 8 (01) :49-55

[9]

Coja-Oghlan A, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P899

[10] Chasing the k-colorability threshold [J].

Coja-Oghlan, Amin ;

Vilenchik, Dan .

2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, :380-389

← 1 2 3 →