pith. machine review for the scientific record. sign in

arxiv: 0912.5039 · v3 · pith:VPKMMYYMnew · submitted 2009-12-26 · 🧮 math.CO

Q₂-free families in the Boolean lattice

classification 🧮 math.CO
keywords familysubsetsbooleanfreelargestlatticemathcalordered
0
0 comments X
read the original abstract

For a family $\mathcal{F}$ of subsets of [n]=\{1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that $\mathcal{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) \leq ex(n, Q_2)\leq 2.283261N +o(N), $ where $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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.