Q
2-free Families in the Boolean Lattice |
| |
Authors: | Maria Axenovich Jacob Manske Ryan Martin |
| |
Institution: | 1. Iowa State University, Ames, IA, 50010, USA
|
| |
Abstract: | For a family F{{\cal F}} of subsets of n] = {1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that F{{\cal F}} is P-free if it does not contain a subposet isomorphic to P. Let ex(n, P) be the largest size of a P-free family of subsets of n]. Let Q
2 be the poset with distinct elements a, b, c, d, a < b,c < d; i.e., the 2-dimensional Boolean lattice. We show that 2N − o(N) ≤ ex(n, Q
2) ≤ 2.283261N + o(N), where
N = \binomn?n/2 ?N = \binom{n}{\lfloor n/2 \rfloor}. We also prove that the largest Q
2-free family of subsets of n] having at most three different sizes has at most 2.20711N members. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|