Shadows and isoperimetry under the sequence-subsequence relation (Q1382388)

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.