Discrepancy of permutations is a sub-field of discrepancy theory, that deals with balancing intervals induced by permutations of elements. There is a set of "n" elements, and there are m different permutations on this set. The general research question is: can we color each element in one of two different colors (e.g. black and white), such that in each permutation, every interval contains roughly the same number of elements of each color?
Formally, the "discrepancy" of an interval is defined as the difference between the number of white elements and the number of black elements in that interval; the objective is to color the elements such that the maximum discrepancy of an interval in each of the permutations is as small as possible.
Definitions.
Let "p"1, ...,"pm" be permutations of ["n"]. The "interval set" of a permutation is the set of all subsets of ["n"], that are adjacent to each other in the permutation. For example, if "n"=4 and one of the permutations is (1,2,3,4), then its interval set of contains e.g. the edges (1,2), (1,2,3), (2,3), (2,3,4), etc.
The discrepancy of the permutations "p"1, ...,"pm" is the minimum, over all black-white colorings of the integers in ["n"], of the maximum over all intervals, of the difference between the number of white and black integers in the interval.
Offline colorings.
Jiang, Kulkarni and Singla study the online setting with stochastic point arrival, and prove that:
Online colorings.
Sometimes the elements are not available in advance, but arrive one by one, and each elements should be colored immediately when it arrives. This online setting is challenging even for a single permutation. Jiang, Kulkarni and Singla call the setting with one permutation Online Interval Discrepancy. They prove that:Sec.3.2
The proof extends for the case of two permutations, which they call Online Stripe Discrepancy.
Applications.
Results in discrepancy of permutations have been used in the computation of Agreeable subsets, as well as in Online fair division.
References.
 ;templatestyles src="Reflist/styles.css" / ;