On the minimum number of completely 3-scrambling permutations (Q2476274): Difference between revisions

A family \({\mathcal P}\) of permutations on \([n]\) is completely \(3\)-scrambling if for any triple \((x_1,x_2,x_3)\) of distinct elements of \([n]\), there is a permutation \(\pi\in{\mathcal P}\) with \(\pi(x_1)<\pi(x_2)<\pi(x_3)\). It is proved that the minimum size of a completely \(3\)-scrambling family of pemutations on \([n]\) is at most \[ 2\log_2 n+(1+o(1))\log_2\log_2 n. \]