The discrepancy of permutation families

TitleThe discrepancy of permutation families
Publication TypeJournal Articles
Year of Publication2001
AuthorsSpencer JH, Srinivasan A, Tetali P
JournalUnpublished manuscript
Date Published2001///
Abstract

In this note, we show that the discrepancy of any family of l permutations of[n] = {1,2,...,n} is O(
√
llog n), improving on the O(llog n) bound due to Bohus
(Random Structures & Algorithms, 1:215–220, 1990). In the case where l ≥ n, we
show that the discrepancy is Θ(min{√nlog(2l/n),n}).