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

DOI10.1002/(SICI)1098-2418(199603)8:2%3C131::AID-RSA4%3E3.0.CO;2-ZMaRDI QIDQ4870538zbMATH OpenOpenAlexFDO

Authors 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%3C131::aid-rsa4%3E3.0.co;2-z

zbMATH Keywords

independent setregular hypergraphpolynomial time algorithmChebyshev's inequality

Mathematics Subject Classification ID

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

Cited in

(6)

• Distributions of points in the unit square and large \(k\)-gons
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Large triangles in the \(d\)-dimensional unit cube
• Point sets in the unit square and large areas of convex hulls of subsets of points
• Access balancing in storage systems by labeling partial Steiner systems
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4870538)