首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号