An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements
type: Item
instance of: scholarly article
title: An extremal problem of \(d\) permutations containing every permutation of every \(t\) elements
zbMATH Open document ID: 0860.05001
DOI: 10.1016/0012-365X(95)00087-D
author: Yoshiyas Ishigami
published in: Discrete Mathematics
publication date: 1997-04-21T00:00:00Z
review text: 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)].
reviewed by: Le Maohua
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 955105
zbMATH Keywords: extremal problem
zbMATH Keywords: permutation
MaRDI profile type: Publication
cites work: An extremal problem of orthants containing at most one point besides the origin
cites work: Minimal scrambling sets of simple orders
cites work: Logarithmic order of free distributive lattice
Recommended article: Extremal problems on permutations under cyclic equivalence
Recommended article: A unified approach to simple special cases of extremal permutation problems
Recommended article: On extremal permutations avoiding \(\omega_N=NN-1\dots 1\)
Recommended article: On the extension problem for partial permutations
Recommended article: On the enumeration of d-minimal permutations
Recommended article: Extremal permutations with respect to weak majorizations
Recommended article: Permutations with extremal number of fixed points
Recommended article: The enumeration of permutations whose posets have a maximum element
Recommended article: Q5260327
Recommended article: Some problems of the theory of enumerating the permutations with restricted positions
description: scientific article; zbMATH DE number 955105