Set families with a forbidden induced subposet

DOI10.1017/S0963548312000028MaRDI QIDQ2908124zbMATH OpenOpenAlexFDO

Authors Edward Boehnlein, Tao Jiang

Publication date 4 September 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: For each poset $H$ whose Hasse diagram is a tree of height $k$, we show that the largest size of a family $cF$ of subsets of $[n]=1,\mathrm{...},n$ not containing $H$ as an induced subposet is asymptotic to $(k-1)nchoosefln/2$. This extends the result of Bukh cite{bukh}, which in turn generalizes several known results including Sperner's theorem.

Recommendations

• Set families with a forbidden subposet
• Set families with forbidden subposets
• On families of subsets with a forbidden subposet
• A note on the largest size of families of sets with a forbidden poset
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems

Cites work

• An extremal problem with excluded subposet in the Boolean lattice
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• Largest families without an \(r\)-fork
• Largest family without \(A \cup B \subseteq C \cap D\)
• On a lemma of Littlewood and Offord
• On families of subsets with a forbidden subposet

Cited in

(18)

• Uniform chain decompositions and applications
• Forbidden subposet problems with size restrictions
• Set families with forbidden subposets
• Supersaturation and stability for forbidden subposet problems.
• Infinitely many trees have non-Sperner subtree poset
• A simple proof for a forbidden subposet problem
• Small dense subgraphs of a graph
• Induced Turán numbers
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Forbidden induced subposets of given height
• Sperner type theorems with excluded subposets
• A LYM inequality for induced posets
• Set families with a forbidden subposet
• Induced and non-induced forbidden subposet problems
• Forbidding rank-preserving copies of a poset
• Exact forbidden subposet results using chain decompositions of the cycle
• Packing the Boolean lattice with copies of a poset

This page was built for publication: Set families with a forbidden induced subposet

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