Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders |
| |
Authors: | Email author" target="_blank">Uwe?LeckEmail author |
| |
Institution: | (1) Universität Rostock, Fachbereich Mathematik, 18051 Rostock, Germany |
| |
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 vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n 2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n 3 by explicitly giving a counterexample. Based on this, we prove that for no n 3 the subword order SO(n) is a Macaulay poset. |
| |
Keywords: | 06A07 05D05 68R15 |
本文献已被 SpringerLink 等数据库收录! |