A new lower bound for multi-color discrepancy with applications to fair division

Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam

A classical problem in combinatorics seeks colorings of low discrepancy. More concretely, the goal is to color the elements of a set system so that the number of appearances of any…