A note on scrambling permutations

Let \(n\), \(k\) be any positive integers with \(k\leq n\). A family \({\mathcal F}\) of permutations of \([n]\) is said to be completely \(k\)-scrambling if for every sequence \((p_1,p_2,\dots, p_k)\) of \(k\) distinct elements of \([n]\), there is a permutation \(\pi\in{\mathcal F}\) with \(\pi(p_1)< \pi(p_2)<\cdots< \pi(p_k)\). Let \(N^*(n, k)\) be the size of the smallest completely \(k\)-scrambling family of permutations of \([n]\). For any \(k\) with \(3\leq k\leq n,\) \textit{Z. Füredi} [Random Struct. Algorithms 8, 97-104 (1996; Zbl 0842.05002)] showed that \[ {1\over 2} (k- 1)!\log_2n< N^*(n, k)< {k\over\log_2(k!/(k!- 1))} \log_2n.\tag{1} \] Using the concept of content of bipartite graphs, in the present paper the lower bound in (1) is improved as follows: If \(n> k\geq 3\), then \[ N^*(n, k)> 1+ \Biggl({2\over\log_2 e}\Biggr) \Biggl({n\over 2n- k+1}\Biggr) (k- 1)! \log_2(n- k+2). \] {}.

Recommendations

Cited in

(13)

This page was built for publication: A note on scrambling permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4419290)