Poset-free Families and Lubell-boundedness

Autor: Griggs, Jerrold R., Li, Wei-Tian
Rok vydání: 2012
Předmět:
Druh dokumentu: Working Paper
Popis: 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$, $\pi(P):= \lim_{n\rightarrow\infty} \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_2$, the existence of $\pi$ frustratingly remains open. Here we develop theory to show that $\pi(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 $\pi=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.
Databáze: arXiv