A finite word poset. (English) Zbl 0994.06002

Erdős, Péter L.; Sziklai, Péter; Torney, David C.

Electron. J. Comb. 8, No. 2, Research paper R8, 10 p. (2001).

The posets \(P^{(n)}\) denote the collections of all sequences of length \(n\) on a finite alphabet \(\Gamma= \{1,2,\dots, k\}\) ordered by subsequence containment with \(P^{(n)}_i\) comprising all \(k^i\) \(I\)-sequences as rank \(i\) elements. Investigated in the light of the poset of all finite sequences on \(\Gamma\), whose combinatorial properties are interesting, important and well-studied, similarly interesting results are obtained as well for the (poset) ideals \(B_{k,n}\) of \(P^{(n)}\) generated by \((w_1\cdots w_k)\cdots(w_1\cdots w_k) w_1\cdots w_\ell\), where \(\ell\equiv n\pmod k\) and \(w_1\cdots w_k\) is a fixed permutation of \(\Gamma\) (or the reverse of such a sequence) equipped with the derived (induced) order. Thus, e.g., if \(\pi\) is a permutation of \(\Gamma\), \(\sigma_\pi(w_1\cdots w_\ell)= \pi(w_1)\cdots \pi(w_\ell)\), \(\sigma_\pi\in \text{Sym}_k\cong S_k\), and \(\rho\) reverses words, then, for \(n> 2\), \(\alpha\in \operatorname{Aut}(P^{(n)})\) implies \(\alpha= \pi\rho\) or \(\alpha= \pi\), \(\operatorname{Aut}(P^{(n)})= \text{Sym}_k\otimes Z_2\), or, if \(n= 2\), \(\operatorname{Aut}(P^{(n)})= \text{Sym}_k\otimes Z^{{k\choose 2}}\). If \(\overline N(j,\xi;k)\) denotes the number of \(j\)-sequences not containing \(\xi\), then \(\overline N(j,\xi,k)= \sum^{|\xi|- 1}_{i=0} {j\choose i}(k- 1)^{(j- i)}\), \(|\xi|\) is the length of \(\xi\). The cardinality of a maximum antichain is \(k^n\). Further combinatorial properties of interest are obtained and the theorem of Burosch, Franke and Röhl is provided with an alternative proof, while the BLYM inequality is also verified via the normalized matching property established for the \(P^{(n)}\).

Reviewer: Joseph Neggers (Tuscaloosa)

MSC:

06A07	Combinatorics of partially ordered sets
68R15	Combinatorics on words
06B25	Free lattices, projective lattices, word problems

Keywords:

automorphisms; words of length at most \(n\); poset of finite sequences