Set families with forbidden subposets

DOI10.1016/J.JCTA.2015.06.002MaRDI QIDQ490910zbMATH OpenOpenAlexFDO

Authors Linyuan Lu, Kevin G. Milans

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Boolean latticeLubell functioninduced subposetTurán-type problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: Let $F$ be a family of subsets of $1,ldots,n$. We say that $F$ is $P$-free if the inclusion order on $F$ does not contain $P$ as an induced subposet. The emph{Tur'an function} of $P$, denoted $p{i}^{\ast }(n,P)$, is the maximum size of a $P$-free family of subsets of $1,ldots,n$. We show that $$ if $P$ is an $r$-element poset of height at most $2$. We also show that $$ where $S_r$ is the standard example on $2r$ elements, and that $$, where $B_2$ is the $2$-dimensional Boolean lattice.

Recommendations

• On families of subsets with a forbidden subposet
• A note on the largest size of families of sets with a forbidden poset
• Set families with a forbidden subposet
• Generalized forbidden subposet problems
• Set families with a forbidden induced subposet

Cites work

• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A note on the largest size of families of sets with a forbidden poset
• An extremal problem with excluded subposet in the Boolean lattice
• Boolean algebras and Lubell functions
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• Diamond-free families
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Largest families without an \(r\)-fork
• Largest family without \(A \cup B \subseteq C \cap D\)
• No four subsets forming an \(N\)
• On a lemma of Littlewood and Offord
• On diamond-free subposets of the Boolean lattice
• On families of subsets with a forbidden subposet
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Set families with a forbidden induced subposet
• Set families with a forbidden subposet
• The method of double chains for largest families with excluded subposets
• \(Q _{2}\)-free families in the Boolean lattice

Cited in

(28)

• A note on the largest size of families of sets with a forbidden poset
• Forbidden subposet problems for traces of set families
• The method of double chains for largest families with excluded subposets
• On crown-free families of subsets
• Induced Turán numbers
• \(Q _{2}\)-free families in the Boolean lattice
• On some extremal and probabilistic questions for tree posets
• Generalized forbidden subposet problems
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
• Poset Ramsey number \(R(P,Q_n)\). II: \(\mathrm{N}\)-shaped poset
• The Boolean rainbow Ramsey number of antichains, Boolean posets and chains
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Forbidden induced subposets of given height
• Progress on poset-free families of subsets
• Sperner type theorems with excluded subposets
• On families of subsets with a forbidden subposet
• Families of subsets without a given poset in double chains and Boolean lattices
• A LYM inequality for induced posets
• Intersecting V-free, \(\wedge\)-free families
• Set families with a forbidden subposet
• Induced and non-induced forbidden subposet problems
• Forbidding rank-preserving copies of a poset
• Set families with a forbidden pattern
• On the number of containments in \(P\)-free families
• Set families with a forbidden induced subposet
• On forbidden sets
• Packing the Boolean lattice with copies of a poset

This page was built for publication: Set families with forbidden subposets

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