Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199603)8:2<131::AID-RSA4>3.0.CO;2-Z" /><131::AID-RSA4>3.0.CO;2-Z 10.1002/(SICI)1098-2418(199603)8:2<131::AID-RSA4>3.0.CO;2-ZzbMath0844.05087OpenAlexW1974136796MaRDI QIDQ4870538

Andrés D. Fundia

Publication date: 20 March 1996

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199603)8:2<131::aid-rsa4>3.0.co;2-z

zbMATH Keywords

polynomial time algorithmindependent setChebyshev's inequalityregular hypergraph

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Large triangles in the \(d\)-dimensional unit cube ⋮ Distributions of points in the unit square and large \(k\)-gons ⋮ Access balancing in storage systems by labeling partial Steiner systems ⋮ Point sets in the unit square and large areas of convex hulls of subsets of points ⋮ On the independence number of non-uniform uncrowded hypergraphs

This page was built for publication: Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs