  Given three permutations on the integers 1 through n, consider the set system
consisting of each interval in each of the three permutations. Jozsef Beck
conjectured (c. 1987) that the discrepancy of this set system is O(1). We give
a counterexample to this conjecture: for any positive integer n = 3^k, we
exhibit three permutations whose corresponding set system has discrepancy
Omega(log(n)). Our counterexample is based on a simple recursive construction,
and our proof of the discrepancy lower bound is by induction. This example also
disproves a generalization of Beck's conjecture due to Spencer, Srinivasan and
Tetali, who conjectured that a set system corresponding to l permutations has
discrepancy O(sqrt(l)).
