Bounds on the size of the largest "induced V" free Boolean Family
by
Teena Carroll
St. Norbert College
Coauthors: Gyula Katona

Define an "induced V" as 3 distinct sets A, B, C so that C ⊆ A∩B but A is not a subset of B. We are interested in how large an "induced-V" free Boolean family can be. If F is such a family, and N is the size of the middle layer of the Boolean Lattice, we show that: N( 1+[1/n]+W( [1/(n²)]) ) ≤ max(|F|) ≤ N ( 1+[2/n]+O( [1/(n²)] ) ). This result builds on Sperner's Lemma which can be thought of as finding the largest subset of the Boolean Lattice which does not contain distinct sets A, B so A ⊂ B. It also relates to several other forbidden substructure bounds developed by Katona and Griggs. However, due to the induced nature of this property, we needed to develop new techniques.

Date received: April 24, 2009