No label defined (Q3972306)

[For the entire collection see Zbl 0706.00007.] If \(\alpha>0\) and \(\pi_ 1,\pi_ 2,\ldots,\pi_ r\) are permutations of \(\{1,2,\ldots,n\}\) then they have the expanding property if for all \(X\subset\{1,2,\ldots,n\}\) with \(| X|\geq\alpha n\;\left|\bigcup^ r_{i=1}\pi_ i(X)\right|>(1-\alpha)n\). The construction of such permutations is a difficult problem. It is known that if one chooses the permutations at random they have the expanding property, but no explicit constructions is known. For instance take \(\pi_ i\) of the form \(\sigma^ i\) with \(\sigma\) fixed. Then this is known to fail. The authors prove that there exist pairs \((\sigma,\tau)\) such that the \(\pi_ i\) of the form \(\sigma^ i\tau^ i_ 1\), \(1\leq i\leq r\), are expanding, where \(r=O(1/\alpha^ 3)\). Moreover most pairs have this property. Again it is impossible to give the pairs explicitly.