A note on scrambling permutations
A note on scrambling permutations
复制标题
关于扰乱排列的注释
DOI：
10.1002/rsa.10082
复制
发表时间：
2003
影响因子：
1
通讯作者：
J. Radhakrishnan
中科院分区：
文献类型：
--
作者：
J. Radhakrishnan
A family ℱ of permutations of [n] is completely k‐scrambling [Spencer, 1972 ] if for every sequence 〈p1, p2, …, pk〉 of k distinct elements of [n], there is a permutation π ∈ ℱ with π(p1) < π(p2) < … < π(pk). We show that the size of the smallest completely k‐scrambling family of permutations of [n] is at least \documentclass{article}\pagestyle{empty}\begin{document}\begin{displaymath} 1 + \left(\frac{2}{\mathrm{log}_2\,e}\right)\!\left(\frac{n}{2 n - k + 1}\right)\!(k - 1)! \; \mathrm{log}_2 (n - k + 2)\end{displaymath}\end{document} This improves the previous best lower bound, due to Füredi 1996 , by a factor of approximately 2/log2e. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 435–439, 2003
A family ℱ of permutations of [n] is completely k‐scrambling [Spencer, 1972 ] if for every sequence 〈p1, p2, …, pk〉 of k distinct elements of [n], there is a permutation π ∈ ℱ with π(p1) < π(p2) < … < π(pk). We show that the size of the smallest completely k‐scrambling family of permutations of [n] is at least \documentclass{article}\pagestyle{empty}\begin{document}\begin{displaymath} 1 + \left(\frac{2}{\mathrm{log}_2\,e}\right)\!\left(\frac{n}{2 n - k + 1}\right)\!(k - 1)! \; \mathrm{log}_2 (n - k + 2)\end{displaymath}\end{document} This improves the previous best lower bound, due to Füredi 1996 , by a factor of approximately 2/log2e. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 435–439, 2003