Random permutations move small sets #
Thirty permutations of a finite set V can be chosen so that every set S of at most half of the
points has at least a tenth of its points moved out of S by one of them
(exists_perms_card_le_mul_card_filter_notMem). By Cslib.RotationMap.le_edgeExpansion_ofPerms
this makes the 60-regular multigraph of the permutations an edge expander, which is the classical
probabilistic proof that constant-degree expanders exist
Hoory, Linial and Wigderson, Theorem 4.16
Arora and Barak, Chapter 21.
The proof is a counting argument; it is the probabilistic method with the probabilities
multiplied out. Let n = |V| and let S have s points, 1 ≤ s ≤ n / 2. A permutation fails
S when it moves fewer than s / 10 points of S out of S; it then keeps some k-element
subset K ⊆ S inside S, where k = s - ⌊(s - 1) / 10⌋ ≥ 9 s / 10. For a fixed K this
happens for at most s (s - 1) ⋯ (s - k + 1) (n - k)! of the n! permutations, a fraction at
most (s / n)^k. Taking the C(s, k) ≤ 3^s / 2^k choices of K into account, a uniformly
random permutation fails S with probability at most 3^s (s / 2n)^k, and thirty independent
ones all fail it with probability at most 3^{30 s} (s / 2n)^{27 s}. As there are at most
(3 n / s)^s sets of size s, thirty random permutations all fail some set of size s with
probability at most (3^{31} / 2^{53})^s ≤ 8^{-s}. Summed over s ≥ 1, this is less than one.
Main results #
Cslib.exists_perms_card_le_mul_card_filter_notMem: thirty permutations that move a tenth of every set of at most half of the points out of it.
References #
Random permutations move small sets: there are thirty permutations of a finite type V such
that every set S of at most half of the points has at least a tenth of its points moved out of S
by one of them. This is the counting form of the probabilistic proof that constant-degree expanders
exist Hoory, Linial and Wigderson, Theorem 4.16
Arora and Barak, Chapter 21.