An improvement of the general bound on the largest family of subsets avoiding a subposet

DOI10.1007/S11083-016-9390-3zbMATH Open1404.06003arXiv1408.5783OpenAlexW1682909341MaRDI QIDQ523149

Abhishek Methuku, Dániel Grósz, Casey Tompkins

Publication date: 20 April 2017

Published in: Order (Search for Journal in Brave)

Abstract: Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=1,2,...,n$ not containing $P$ as a (weak) subposet, and let $h(P)$ be the length of a longest chain in $P$. The best known upper bound for $La(n,P)$ in terms of $|P|$ and $h(P)$ is due to Chen and Li, who showed that $$ for any fixed $mge1$. In this paper we show that $La(n,P)lefrac12^{k-1}(|P|+(3k-5)2^{k-2}(h(P)-1)-1)nchooselfloorn/2floor$ for any fixed $kge2$, improving the best known upper bound. By choosing $k$ appropriately, we obtain that $La(n,P)=Oleft(h(P)lo{g}_{2}left(frac|P|h(P)+2ight)ight)nchooselfloorn/2floor$ as a corollary, which we show is best possible for general $P$. We also give a different proof of this corollary by using bounds for generalized diamonds. We also show that the Lubell function of a family of subsets of $[n]$ not containing $P$ as an induced subposet is $O(n^c)$ for every $c>frac12$.

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

zbMATH Keywords

extremal set theoryforbidden subposetsdouble countinggeneral bounds

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05)

Cites Work

• Unnamed Item
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Diamond-free families
• Induced and non-induced forbidden subposet problems
• Poset-free families and Lubell-boundedness
• Set families with a forbidden subposet
• No four subsets forming an \(N\)
• On crown-free families of subsets
• A note on the largest size of families of sets with a forbidden poset
• Largest families without an \(r\)-fork
• Largest family without \(A \cup B \subseteq C \cap D\)
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• The method of double chains for largest families with excluded subposets
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• A Dual of Dilworth's Decomposition Theorem
• On a lemma of Littlewood and Offord

Related Items (9)

Forbidden induced subposets of given height ⋮ Largest family without a pair of posets on consecutive levels of the Boolean lattice ⋮ Forbidden subposet problems with size restrictions ⋮ Poset Ramsey numbers: large Boolean lattice versus a fixed poset ⋮ An upper bound on the size of diamond-free families of sets ⋮ Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems ⋮ Families of subsets without a given poset in double chains and Boolean lattices ⋮ Ramsey numbers for partially-ordered sets ⋮ On forbidden poset problems in the linear lattice

This page was built for publication: An improvement of the general bound on the largest family of subsets avoiding a subposet