A note on tilted Sperner families with patterns

DOI10.1016/J.DISC.2016.05.029MaRDI QIDQ2629285zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Máté Vizer

Publication date 5 July 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutation methodSperner familytilted Sperner family

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Let $p$ and $q$ be two nonnegative integers with $p+q>0$ and $n>0$. We call $mathcalFsubsetmathcalP([n])$ a extit{(p,q)-tilted Sperner family with patterns on [n]} if there are no distinct $F,GinmathcalF$ with: ${\displaystyle }$(i) p|F setminus G|=q|G setminus F|, extrm{and}${\displaystyle }$ ${\displaystyle }$(ii) f > g extrm{for all} f in F setminus G extrm{and} g in G setminus F.${\displaystyle }$ Long (cite{L}) proved that the cardinality of a (1,2)-tilted Sperner family with patterns on $[n]$ is ${\displaystyle }$O(e^{120sqrt{log n}} frac{2^n}{sqrt{n}}).${\displaystyle }$ We improve and generalize this result, and prove that the cardinality of every ($p,q$)-tilted Sperner family with patterns on [$n$] is ${\displaystyle }$O(sqrt{log n} frac{2^n}{sqrt{n}}).${\displaystyle }$

Recommendations

• Tilted Sperner families
• scientific article; zbMATH DE number 3946128
• A generalization of Sperner's theorem for convex families
• Set families with a forbidden pattern
• On the structure of maximum 2-part Sperner families

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A new proof of the density Hales-Jewett theorem
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Forbidding intersection patterns between layers of the cube
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 2165490 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• Set families with a forbidden pattern
• Tilted Sperner families
• Two-Part and k-Sperner Families: New Proofs Using Permutations

Cited in

(4)

• Smart elements in combinatorial group testing problems
• A note on arrays of dots with distinct slopes
• Tilted Sperner families
• Set families with a forbidden pattern

This page was built for publication: A note on tilted Sperner families with patterns

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