Enumeration of graded (3+1)-avoiding posets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Lewis, Joel Brewster¹  Zhang, Yan X.² 

[1] Univ Minnesota, Minneapolis, MN USA

[2] MIT, Cambridge, MA 02139 USA

关键词: Posets;    (3+1)-avoidance;    Generating functions;    Asymptotic enumeration;   

DOI  :  10.1016/j.jcta.2013.03.012

来源: Elsevier

【 摘 要 】

The notion of (3 + 1)-avoidance has shown up in many places in enumerative combinatorics, but the natural goal of enumerating all (3 + 1)-avoiding posets remains open. In this paper, we enumerate graded (3 + 1)-avoiding posets for both reasonable definitions of the word graded. Our proof consists of a number of structural theorems followed by some generating function computations. We also provide asymptotics for the growth rate of the number of graded (3 + 1)-avoiding posets. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free