Forbidding a Set Difference of Size 1

2013/04/28 by Imre Leader, Leader, Imre, Eoin Long +1
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1304.7471

openalex publication_date 2013/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Forbidden hypermatrices imply general bounds on induced forbidden\n subposet problems
• Forbidden induced subposets of given height
• Supersaturation, counting, and randomness in forbidden subposet problems
• Tilted Sperner Families
• Largest Sperner families with restricted differences