Premium
On the chromatic number of set systems
Author(s) -
Kostochka Alexandr,
Mubayi Dhruv,
Rödl Vojtěch,
Tetali Prasad
Publication year - 2001
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/rsa.1020
Subject(s) - hypergraph , combinatorics , mathematics , struct , complement (music) , chromatic scale , probabilistic logic , set (abstract data type) , discrete mathematics , enhanced data rates for gsm evolution , computer science , biochemistry , chemistry , statistics , complementation , phenotype , gene , programming language , telecommunications
An ( r , l )‐system is an r ‐uniform hypergraph in which every set of l vertices lies in at most one edge. Let m k ( r , l ) be the minimum number of edges in an ( r , l )‐system that is not k ‐colorable. Using probabilistic techniques, we prove that$$a_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)}\leq m_k(r,l)\leq b_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)},$$ where b r , l is explicitly defined and a r , l is sufficiently small. We also give a different argument proving (for even k )$$m_k(r,l)\leq a'_{r,l}k^{(r-1)l/(l-1)}.$$ where a ′ r , l =( r − l +1)/ r (2 r −1 re ) − l /( l −1) . Our results complement earlier results of Erdős and Lovász [10] who mainly focused on the case l =2, k fixed, and r large. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 87–98, 2001