The method of double chains for largest families with excluded subposets

Peter Burcsi (Department of Computer Algebra, Faculty of Informatics, Eotvos Lorand University, Budapest)
Daniel T. Nagy (Eotvos Lorand University, Budapest)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 1, No 1 (2013): Electronic Journal of Graph Theory and Applications

For a given finite poset $P$, $La(n,P)$ denotes the largest size of a family $\mathcal{F}$ of subsets of $[n]$ not containing $P$ as a weak subposet. We exactly determine $La(n,P)$ for infinitely many  $P$ posets. These posets are built from seven base posets using two operations. For arbitrary posets, an upper bound is given for $La(n,P)$ depending on $|P|$ and the size of the longest chain in $P$. To prove these theorems we introduce a new method, counting the intersections of $\mathcal{F}$ with double chains, rather than chains.