A characterization of (3+1)-free posets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:93

Article

Skandera, M

关键词: poset;    f-vector;    total positivity;   

DOI  :  10.1006/jcta.2000.3075

来源: Elsevier

【 摘 要 】

Posets containing no subposet isomorphic to the disjoint sums of chains 3+1 and/or 2+2 are known to have many special properties. However, while posers free of 2+2 and posets free or both 2+2 and 3+1 may be characterized as interval orders, no such characterization is known for posets free of only 3+1. We give here a characterization of (3+1)-free posers in terms of their antiadjacency matrices. Using results about totally positive matrices, we show that this characterization leads to a simple proof that the chain polynomial or a (3+1)-free poser has only real zeros. (C) 2001 Academic Press.

【 授权许可】

Free