Discrepancy of permutations

Last updated August 13, 2024

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 permutationsp₁, ...,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.^[1]

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.^[1]

For any m permutations, the discrepancy is at most $8m\log {n}$ , and such a coloring can be computed efficiently.^[2]
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 {1,-1} 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}+2d-2)/3$ .^[3]^: Cor.2 This has implications for the bin packing problem.

Jiang, Kulkarni and Singla^[1] 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:^[1]^: Sec.3.2

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.^[1]

Related Research Articles

In mathematics, the factorial of a non-negative integer $,$ denoted by $,$ is the product of all positive integers less than or equal to $.$ The factorial of also equals the product of $with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.$

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x₁, ..., x_N has a low discrepancy.

In computational complexity theory, the 3SUM problem asks if a given set of $real numbers contains three elements that sum to zero. A generalized version, k -SUM, asks the same question on k elements, rather than simply 3. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation.$

In graph theory, a complete coloring is a (proper) vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper coloring with fewer colors by merging pairs of color classes. The achromatic number $ψ(G)$ of a graph $G$ is the maximum number of colors possible in any complete coloring of $G$ .

<span class="mw-page-title-main">Maximal independent set</span> Independent set which is not a subset of any other independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time $where denotes the length of the input sequence.$

<span class="mw-page-title-main">Prime gap</span> Difference between two successive prime numbers

A prime gap is the difference between two successive prime numbers. The n-th prime gap, denoted g_n or g(p_n) is the difference between the (n + 1)-st and the n-th prime numbers, i.e.

Discrepancy of hypergraphs is an area of discrepancy theory that studies the discrepancy of general set systems.

In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Different distributions have been used, leading to different properties for these trees.

In computer science and data mining, MinHash is a technique for quickly estimating how similar two sets are. The scheme was invented by Andrei Broder, and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results. It has also been applied in large-scale clustering problems, such as clustering documents by the similarity of their sets of words.

Leonid Mirsky was a Russian-British mathematician who worked in number theory, linear algebra, and combinatorics. Mirsky's theorem is named after him.

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If $is a finite set of non-negative integers on which no three elements form an arithmetic progression, then the Stanley sequence generated from starts from the elements of, in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley.$

Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

Geometric discrepancy theory is a sub-field of discrepancy theory, that deals with balancing geometric sets, such as intervals or rectangles. The general research question in this field is: given a set of points in a geometric space, and a set of objects in the same space, can we color each point in one of two different colors, such that each object contains roughly the same number of points of each color?

References

1 2 3 4 5 Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02), Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization, doi:10.48550/arXiv.1910.01073 , retrieved 2024-07-21
↑ Bohus, Géza (1990). "On the discrepancy of 3 permutations". Random Structures & Algorithms. 1 (2): 215–220. doi:10.1002/rsa.3240010208. ISSN 1098-2418.
↑ Newman, A.; Neiman, O.; Nikolov, A. (2012-10-01). "Beck's Three Permutations Conjecture: A Counterexample and Some Consequences". 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 253–262. doi:10.1109/FOCS.2012.84. ISBN 978-0-7695-4874-6. S2CID 14442594.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:22-1] 1 2 3 4 5 Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02), Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization, doi:10.48550/arXiv.1910.01073 , retrieved 2024-07-21

[2] Bohus, Géza (1990). "On the discrepancy of 3 permutations". Random Structures & Algorithms. 1 (2): 215–220. doi:10.1002/rsa.3240010208. ISSN 1098-2418.

[3] Newman, A.; Neiman, O.; Nikolov, A. (2012-10-01). "Beck's Three Permutations Conjecture: A Counterexample and Some Consequences". 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 253–262. doi:10.1109/FOCS.2012.84. ISBN 978-0-7695-4874-6. S2CID 14442594.

[1]

[2]

[3]