Set families with a forbidden induced subposet

DOI10.1017/S0963548312000028zbMATH Open1260.06002arXiv1106.2315OpenAlexW2121851282MaRDI QIDQ2908124FDOQ2908124

Authors: Edward Boehnlein, Tao Jiang 

Publication date: 4 September 2012

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

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

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)