Discrepancy of permutations explained

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₁, ...,p_m 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₁, ...,p_m 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

• When there is only one permutation, a discrepancy of 1 is possible, by simply coloring the integers alternately white - black - white - black - etc.
• When there are two permutations, a discrepancy of 2 is possible; this was proved by Spencer in 1987.
• For any m permutations, the discrepancy is at most

8 m log {n} , and such a coloring can be computed efficiently.^[1]

• For any three permutations, Beck conjectured that the discrepancy is constant. However, this conjecture was refuted: for any n which is a power of 3, there exist 3 permutations whose discrepancy is

\lceil ( log _{3{n})/3} + 1 \rceil . More precisely, for any coloring, if the sum of all colors is d, then there exists some integer q such that, in all three permutations, the sum of the first q colors is at most ( -log _{3{n}} + 2 d - 2 )/ 3 .^[2] This has implications for the bin packing problem.

Jiang, Kulkarni and Singla study the online setting with stochastic point arrival, and prove that:

• A random coloring yields an expected discrepancy of

\tilde{O}(\sqrt{n}) .

• There is an efficient algorithm that guarantees

O(n ^{c/log{log{n} }}) discrepancy, for some universal constant c, with high probability. They show an application of this result to online fair division.

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:

• No online algorithm can guarantee a constant discrepancy.
• Random coloring gives

\tilde{O}(\sqrt{n}) expected discrepancy.

• If the arrival is adversarial, the discrepancy of any online algorithm is

\Omega(\sqrt{n}) .

• If the arrival is stochastic, there is an efficient algorithm that guarantees

O(n ^{c/log{log{n} }}) discrepancy, for some universal constant c, with high probability (i.e. with probability 1-1/poly(n), where the exponent of the polynomial depends on c).

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.

Notes and References

1. Bohus . Géza . 1990 . On the discrepancy of 3 permutations . Random Structures & Algorithms . en . 1 . 2 . 215–220 . 10.1002/rsa.3240010208 . 1098-2418.
2. Book: Newman . A. . 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science . Neiman . O. . Nikolov . A. . 2012-10-01 . 978-0-7695-4874-6 . 253–262 . Beck's Three Permutations Conjecture: A Counterexample and Some Consequences . 10.1109/FOCS.2012.84 . https://ieeexplore.ieee.org/document/6375303 . 14442594.