Article ID Journal Published Year Pages File Type
419067 Discrete Applied Mathematics 2014 6 Pages PDF
Abstract

How large can a family A⊂P[n]A⊂P[n] be if it does not contain A,BA,B with |A∖B|=1|A∖B|=1? Our aim in this paper is to show that any such family has size at most 2+o(1)n(n⌊n/2⌋). This is tight up to a multiplicative constant of 2. We also obtain similar results for families A⊂P[n]A⊂P[n] with |A∖B|≠k|A∖B|≠k, showing that they satisfy |A|≤Cknk(n⌊n/2⌋), where CkCk is a constant depending only on kk.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,