Two-coloring random hypergraphs

被引:20
作者
Achlioptas, D
Kim, JH
Krivelevich, M
Tetali, P [1 ]
机构
[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
[2] Microsoft Corp, Res, Redmond, WA 98052 USA
[3] Tel Aviv Univ, Dept Math, IL-69978 Tel Aviv, Israel
关键词
D O I
10.1002/rsa.997
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k, n, p) be a random k-uniform hypergraph on a vertex set V of cardinality n, where each k-subset of V is an edge of H with probability p, independently of all other k-subsets. Let m = p((n)(k)) denote the expected number of edges in H. Let us say that a sequence of events xi(n) holds with high probability (w.h.p.) if lim(n-->infinity) Pr[xi(n)] = 1. It is easy to show that if m = c2(k)n then w.h.p H is not 2-colorable for c > ln 2/2. We prove that there exists a constant c > 0 such that if M = (c2(k)/k)n, then w.h.p H is 2-colorable. (C) 2002 Wiley Periodicals, Inc.
引用
收藏
页码:249 / 259
页数:11
相关论文
共 20 条
[1]  
ALON N, UNPUB NOTE COLORING
[2]   3-CHROMATIC HYPERGRAPHS [J].
BECK, J .
DISCRETE MATHEMATICS, 1978, 24 (02) :127-137
[3]  
Berge C., 1989, HYPERGRAPHS
[4]  
Bernstein F., 1908, Leipzig Berichte, V60, P325
[5]  
Bollobas B, 1985, RANDOM GRAPHS
[6]  
CHAO MT, 1990, INFORM SCIENCES, V51, P289, DOI 10.1016/0020-0255(90)90030-E
[7]  
CHVATAL V, 1992, AN S FDN CO, P620
[8]  
ERDOS P, COLL MATH SOC JANOS, V10, P609
[9]  
Erdos P., 1963, NORDISK MAT TIDSKR, V11, P40
[10]   THE 1ST CYCLES IN AN EVOLVING GRAPH [J].
FLAJOLET, P ;
KNUTH, DE ;
PITTEL, B .
DISCRETE MATHEMATICS, 1989, 75 (1-3) :167-215