Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Discrepancy of permutations
open-in-new
<p>Discrepancy of permutations is a sub-field of <a href="/facts/Discrepancy_theory/8dknBzQa">discrepancy theory</a>, that deals with balancing intervals induced by permutations of elements. There is a set of <i>n</i> 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? </p><p>Formally, the <i>discrepancy</i> 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. </p>