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 条

[11]

Coja-Oghlan A, 2013, ELECTRON J COMB, V20

[12] Proof of the Satisfiability Conjecture for Large k [J].

Ding, Jian ;

Sly, Allan ;

Sun, Nike .

STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2015, :59-68

[13] On the chromatic number of a random hypergraph [J].

Dyer, Martin ;

Frieze, Alan ;

Greenhill, Catherine .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 113 :68-122

[14]

ERDOS P, 1960, B INT STATIST INST, V38, P343

[15] Random k-SAT:: A tight threshold for moderately growing k [J].

Frieze, A ;

Wormald, NC .

COMBINATORICA, 2005, 25 (03) :297-305

[16] On the Number of Perfect Matchings in Random Lifts [J].

Greenhill, Catherine ;

Janson, Svante ;

Rucinski, Andrzej .

COMBINATORICS PROBABILITY & COMPUTING, 2010, 19 (5-6) :791-817

[17] Sharp thresholds for constraint satisfaction problems and homomorphisms [J].

Hatami, Hamed ;

Molloy, Michael .

RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (03) :310-332

[18]

Janson S., 2000, Wiley-Interscience Series in Discrete Mathematics and Optimization, DOI 10.1002/9781118032718

[19] THE NATURE OF THE GLASSY STATE AND THE BEHAVIOR OF LIQUIDS AT LOW TEMPERATURES [J].

KAUZMANN, W .

CHEMICAL REVIEWS, 1948, 43 (02) :219-256

[20]

Krivelevich M, 1998, RANDOM STRUCT ALGOR, V12, P381, DOI 10.1002/(SICI)1098-2418(199807)12:4<381::AID-RSA5>3.0.CO

← 1 2 3 →