Set families with forbidden subposets

DOI10.1016/J.JCTA.2015.06.002zbMATH Open1319.05075arXiv1408.0646OpenAlexW2963906655MaRDI QIDQ490910FDOQ490910

Authors: Linyuan Lu, Kevin G. Milans 

Publication date: 21 August 2015

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

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.

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

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

zbMATH Keywords

Boolean latticeLubell functioninduced subposetTurán-type problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• 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
• An extremal problem with excluded subposet in the Boolean lattice
• 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?)
• On families of subsets with a forbidden subposet
• Diamond-free families
• \(Q _{2}\)-free families in the Boolean lattice
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• On diamond-free subposets of the Boolean lattice
• A note on the largest size of families of sets with a forbidden poset
• Set families with a forbidden induced subposet
• Boolean algebras and Lubell functions
• The method of double chains for largest families with excluded subposets
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

Cited In (26)

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

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)