Lunches‎ > ‎

Fri May 12: Discrepancy upper bound

posted May 12, 2017, 6:31 AM by Dirk Oliver Theis   [ updated Jun 10, 2017, 1:16 AM ]
We worked through the proof that every hypergraph with sufficiently many edges has a 2-coloring with discrepancy at most sqrt( n log(m/n) ). Highlights of the proof included the use of entropy and Kleitman's theorem.
Comments