Shadows and isoperimetry under the sequence-subsequence relation
The object of the paper is the so-called subword poset defined as the set of all binary words ordered by a subword relation. For the set \(U_n\) of all words of length \(n\) consider the problem of finding a set \(A\subseteq U_n\) with minimal shadow among all subsets of \(U_n\) of the same size. The authors consider various definitions of shadow. For example, they define \(\Delta(A)\) as the set of all words of length \(n-1\) obtained from the words of \(A\) by deleting a letter (i.e. \(0\) or \(1\)). Similarly let \(\nabla(A)\) be the set of all words of length \(n+1\) obtained from the words of \(A\) by inserting a letter. Denote by \(H_n\) the following total order of words of length \(n\). For two such words \(a=(a_1,\dots,a_n)\) and \(b=(b_1,\dots,b_n)\) write \(a>b\) if either \(\sum^n_{i=1} a_i > \sum^n_{i=1} b_i\) or if the two sums are equal, \(a\) is less than \(b\) in the lexicographic order. It is shown that for any \(m\), \(1\leq m\leq 2^n\), the collection of the first \(m\) words in the order \(H_n\) (i.e. an initial segment of this order) provide minimum to the functions \(\Delta\) and \(\nabla\). Although under certain conditions the extremal sets with respect to the function \(\nabla\) can be easily constructed from ones with respect to \(\Delta\), for the considered poset these two sets are the same. This, in particular, implies that the both shadows of an initial segment of the order \(H_n\) and of a final segment of \(H_n\) of the same length have the same size. This effect does not hold for posets studied in the literature, where solutions of similar problems are known. The mentioned results are applied for deriving some isoperimetric-type inequalities for the Hasse diagram of the considered poset. The result concerning the extremal set with respect to the function \(\Delta\) has also been obtained independently by the reviewer and published in his Habilitation thesis in 1996.
- Bounds on conditional probabilities with applications in multi-user communication
- Contributions to the geometry of Hamming spaces
- scientific article; zbMATH DE number 3974960 (Why is no real title available?)
- scientific article; zbMATH DE number 3570458 (Why is no real title available?)
- Optimal numberings and isoperimetric problems on graphs
This page was built for publication: Shadows and isoperimetry under the sequence-subsequence relation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382388)
