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

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

Authors: Dániel Grósz, Abhishek Methuku, 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,\mathrm{...},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

Recommendations

• A note on the largest size of families of sets with a forbidden poset
• Families of subsets without a given poset in double chains and Boolean lattices
• Poset-free families and Lubell-boundedness
• On families of subsets with a forbidden subposet
• An upper bound on the size of diamond-free families of sets

zbMATH Keywords

extremal set theoryforbidden subposetsdouble countinggeneral bounds

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• The largest family of subsets satisfying sequential-evaluation convergence
• A note on the largest size of families of sets with a forbidden poset
• Forbidden induced subposets of given height
• Families of subsets without a given poset in double chains and Boolean lattices
• Largest family without a pair of posets on consecutive levels of the Boolean lattice
• Poset-free families and Lubell-boundedness
• On forbidden poset problems in the linear lattice
• An upper bound on the size of diamond-free families of sets
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• The method of double chains for largest families with excluded subposets
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Boolean algebras and Lubell functions
• Ramsey numbers for partially-ordered sets
• Forbidden subposet problems with size restrictions

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

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