Premium
The chromatic numbers of random hypergraphs
Author(s) -
Krivelevich Michael,
Sudakov Benny
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199807)12:4<381::aid-rsa5>3.0.co;2-p
Subject(s) - hypergraph , chromatic scale , combinatorics , mathematics , partition (number theory) , random graph , struct , discrete mathematics , graph , computer science , programming language
For a pair of integers 1≤γ< r , the γ‐chromatic number of an r ‐uniform hypergraph H =( V , E ) is the minimal k , for which there exists a partition of V into subsets T 1 ,…, T k such that | e ∩ T i |≤γ for every e ∈ E . In this paper we determine the asymptotic behavior of the γ‐chromatic number of the random r ‐uniform hypergraph H r ( n , p ) for all possible values of γ and for all values of p down to p =Θ( n − r +1 ). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998