No four subsets forming an N

A 2007 Preprint by J. Griggs and G. Katona

• 2007:04

• We survey results concerning the maximum size of a family F of subsets of an n-element set such that a certain configuration is avoided. When F avoids a chain of size two, this is just Sperner's Theorem. Here we give bounds on how large F can be such that no four distinct sets $A,B,C,D\in{F}$ satisfy $A\subset{B},C\subset{B},C\subset{D}$. In this case, the maximum size satisfies

  $$\binom{n}{\lfloor{\frac{n}{2}}\rfloor}\left(1+\frac{1}{n}+O\left(\frac{1}{n^2}\right)\right)\leq|F|\leq\binom{n}{\lfloor\frac{n}{2}\rfloor}\left(1+\frac{2}{n}+O\left(\frac{1}{n^2}\right)\right),$$

  which is very similar to the best-known bounds for the more restrictive problem of F avoiding three sets $B,C,D$ such that $C\subset{B},C\subset{D}$.