Uwe Leck
Nonexistence of a Kruskal-Katona type theorem for subword orders
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt Rostock
MSC:
06A07 Combinatorics of partially ordered sets
05D05 Extremal set theory
Abstract: We consider the poset $SO(n)$ of all words over an $n$--element alphabet ordered
by the subword relation. It is known that $SO(2)$ falls into the class of
Macaulay posets, i.e. there is a theorem of Kruskal--Katona type for $SO(2)$.
As the corresponding linear ordering of the elements of $SO(2)$ the
\emph{vip}--order can be chosen.

Daykin introduced the \emph{V}--order which generalizes the \emph{vip}--order
to the $n\ge 2$ case. He conjectured that the \emph{V}--order gives a
Kruskal--Katona type theorem for $SO(n)$.

We show that this conjecture fails for all $n\ge 3$ by explicitely giving a
counterexample. Based on this, we prove that for no $n\ge 3$ the subword order
$SO(n)$ is a Macaulay poset.
Keywords: parially ordered set, subword orders, Macaulay posets