Poset-free Families and Lubell-boundedness

2012/08/21 by Griggs, Jerrold R., Li, Wei-Tian · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1208.4241

Abstract

Given a finite poset P, we consider the largest size \lanp of a family \F of subsets of [n]:=\1,...,n\ that contains no subposet P. This continues the study of the asymptotic growth of \lanp; it has been conjectured that for all P, π(P):= lim_n→∞ \lanp/\nchn exists and equals a certain integer, e(P). While this is known to be true for paths, and several more general families of posets, for the simple diamond poset \D₂, the existence of π frustratingly remains open. Here we develop theory to show that π(P) exists and equals the conjectured value e(P) for many new posets P. We introduce a hierarchy of properties for posets, each of which implies π=e, and some implying more precise information about \lanp. The properties relate to the Lubell function of a family \F of subsets, which is the average number of times a random full chain meets \F. We present an array of examples and constructions that possess the properties.

Cited by

• Ramsey numbers for partially-ordered sets

Related

• Diamond-free Families
• The method of double chains for largest families with excluded subposets
• On families of subsets with a forbidden subposet
• The Asymptotic Bound of the Lubell Function for Diamond-free Families
• Supersaturation, counting, and randomness in forbidden subposet problems