Combinatorial Discrepancy, or how randomness comes again to the rescue

Introduction

This is the 2nd post about the power of the so-called Probabilistic Method, which exploits randomness in order to prove claims for discrete structure that are always true! For an intro to the Probabilistic Method, you can have a look at my 1st post here.

The main problem of study will be what is known as Combinatorial Discrepancy. The setting is quite simple. We are given a finite set

of N points, and a family F of subsets of E,

The goal is to bi-color the set E, i.e., assign a color to each point of E (either RED or BLUE), so as to make the sets as balanced as possible.

More formally, we can think of the two colors as being represented by +1/-1 (e.g., RED = +1 and BLUE = -1), and we define the discrepancy of a coloring

to be the maximum discrepancy over all sets in F with respect to this coloring. The discrepancy of a set

with respect to a given coloring COL is equal to the quantity

In words, the discrepancy of a set is equal to the absolute value of the difference between the number of red and the blue points it contains.

A famous result from the 80s by Joel Spencer is the following.