Majorization and Schur-convex observables (BCEKMN17, Section 2.1) #
Majorizes x y (the paper's x ⪰ y): equal total sums, and for every j the sum of the j
largest entries of x is at least that of y. It is stated without sorting: every sum of y
over a set S is bounded by a sum of x over a set S' of the same size, which is the same as
comparing the sums of the |S| largest entries.
SchurConvex φ: an observable of configurations that is monotone for the majorization of the
configuration vectors (the paper's Schur-convex functions of c, for the preorder ⪯ on the
configuration space 𝒞). Such an observable depends on the configuration only through its
sorted configuration vector. The indicator of "at most κ colours" is one of them
(schurConvex_numColours_le), which is how the comparison of Theorem 2 controls the number of
remaining colours.
Vector majorization x ⪰ y (BCEKMN17, Section 2.1): equal sums, and the sum of the j
largest entries of y is at most that of x for every j, in the sort-free form "every sum of
y over a set is bounded by a sum of x over a set of the same size".
Equations
Instances For
The configuration vector (c_a)_a of a configuration, as a real vector.
Equations
- ThreeMajority.countVec c a = ↑(ThreeMajority.colourCount c a)
Instances For
A Schur-convex observable of configurations (BCEKMN17, Section 2.1): monotone for the majorization of the configuration vectors.
Equations
- ThreeMajority.SchurConvex φ = ∀ (c c' : Fin n → σ), ThreeMajority.Majorizes (ThreeMajority.countVec c) (ThreeMajority.countVec c') → φ c' ≤ φ c
Instances For
A configuration whose vector majorizes another one has at most as many colours: the
numColours c' largest entries of c' already sum to n, so c has all its mass on as many
colours (BCEKMN17, Section 2.3, observation 1 after Lemma 1: consensus is maximal for ⪯).
The indicator of "at most κ colours" is Schur-convex.