Premium
Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs
Author(s) -
Fundia Andrés D.
Publication year - 1996
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(199603)8:2<131::aid-rsa4>3.0.co;2-z
Subject(s) - hypergraph , mathematics , random variable , set (abstract data type) , probabilistic logic , combinatorics , discrete mathematics , chebyshev polynomials , inequality , computer science , statistics , mathematical analysis , programming language
In [1] it is proved that an uncrowded ( k + 1)‐hypergraph of average degree t k contains an independent set of size ( cn / t )(1n t ) 1/k . We present a polynomial time algorithm that finds such an independent set by derandomizing the original probabilistic proof. The technique that we use can be applied to derandomize other random algorithms that use several random variables having sufficiently small variances. © 1996 John Wiley & Sons, Inc.