An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements (Q1126218): Difference between revisions

Let \(t\), \(n\) be positive integers with \(t\leq n\), and let \(A\) be a set of \(n\) elements. Further let \(d_t(n)\) denote the smallest number \(d\) of permutations \(\sigma_1,\sigma_2,\dots,\sigma_d\) of \(A\) such that for every permutation \(\tau\) of every \(t\) elements of \(A\), there exists a \(\sigma_i\) \((1\leq i\leq d)\) containing \(\tau\). It is obvious that \(d_2(n)=2\) if \(n\geq 2\). For \(t\geq 3\), \textit{J. Spencer} [Acta Math. Acad. Sci. Hung. 22, 349-353 (1972; Zbl 0242.05001)] proved that \(\log_2n\leq d_t(n)\leq t\log n/\log(t!/(t!-1))\). In this paper, the author improves the above-mentioned lower bound that if \(t\geq 4\) and \(n\to\infty\), then \(d_t(n)\geq (t-2)/H(1/(t-2)!)-O(1)\), where \(H(a)=-a\log a-(1-a)\log(1-a)\) for any positive number \(a\) with \(a<1\). A related problem for \(t=3\) was discussed by the author in [Discrete Math. 132, No. 1-3, 383-386 (1994; Zbl 0810.52014)].