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

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

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 B C D
• On a lemma of Littlewood and Offord
• On families of subsets with a forbidden subposet

Cited in

(20)

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

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)