Forbidding a set difference of size 1

DOI10.1016/J.DAM.2013.12.021MaRDI QIDQ2449075zbMATH OpenOpenAlexFDO

Authors Imre Leader, Eoin Long

Publication date 6 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7471

zbMATH Keywords

antichainextremal set theorySperner family

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: How large can a family cal A subset cal P [n] be if it does not contain A,B with |Asetminus B| = 1? Our aim in this paper is to show that any such family has size at most frac{2+o(1)}{n} �inom {n}{lfloor n/2 floor }. This is tight up to a multiplicative constant of $2$. We also obtain similar results for families cal A subset cal P[n] with |Asetminus B| eq k, showing that they satisfy |{mathcal A}| leq frac{C_k}{n^k}�inom {n}{lfloor n/2 floor }, where C_k is a constant depending only on k.

Recommendations

• scientific article; zbMATH DE number 3997795
• Size-maximal symmetric difference-free families of subsets of \([n]\)
• On the number of distinct differences in an intersecting family
• Set families with a forbidden subposet
• Bounding one-way differences

Cites work

• Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
• Forbidding just one intersection
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tilted Sperner families

Cited in

(3)

• scientific article; zbMATH DE number 3997795 (Why is no real title available?)
• Set families with a forbidden pattern
• Unions of intervals in codes based on powers of sets

This page was built for publication: Forbidding a set difference of size 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2449075)