On families of subsets with a forbidden subposet

DOI10.1017/S096354830999037XMaRDI QIDQ3552501zbMATH OpenOpenAlexFDO

Authors Linyuan Lu, J. Griggs

Publication date 22 April 2010

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

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

zbMATH Keywords

extremal graph theoryprobability theory

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal set theory (05D05)

Abstract: Let $Fsubset{2}^{[n]}$ be a family of subsets of $1,2,\mathrm{...},n$. For any poset $H$, we say $F$ is $H$-free if $F$ does not contain any subposet isomorphic to $H$. Katona and others have investigated the behavior of $La(n,H)$, which denotes the maximum size of $H$-free families $Fsubset{2}^{[n]}$. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets $H$, for which $La(n,H)$ can be determined asymptotically as $noinfty$ for various posets $H$, including two-end-forks, up-down trees, and cycles $C_{4k}$ on two levels.

Recommendations

• Set families with forbidden subposets
• Generalized forbidden subposet problems
• Set families with a forbidden subposet
• A note on the largest size of families of sets with a forbidden poset
• Progress on poset-free families of subsets

Cites work

• A note on an inequality involving the normal distribution
• 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\)
• Correlation inequalities on some partially ordered sets
• Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
• Largest families without an \(r\)-fork
• Largest family without A B C D
• No four subsets forming an \(N\)
• On a lemma of Littlewood and Offord
• On the structure of linear graphs

Cited in

(52)

• On extremal orthoposets without forbidden substructures
• An extremal problem with excluded subposet in the Boolean lattice
• Forbidden induced subposets of given height
• Forbidden subposet problems with size restrictions
• An upper bound on the size of diamond-free families of sets
• Forbidden subposet problems for traces of set families
• Ramsey numbers for partially-ordered sets
• The partition method for poset-free families
• Induced and non-induced poset saturation problems
• Forbidden subposet problems in the grid
• Rainbow Ramsey problems for the Boolean lattice
• Induced and non-induced forbidden subposet problems
• Forbidding rank-preserving copies of a poset
• On the number of containments in \(P\)-free families
• A simple proof for a forbidden subposet problem
• Poset-free families and Lubell-boundedness
• Abelian groups yield many large families for the diamond problem
• Three layer \(Q _{2}\)-free families in the Boolean lattice
• Set families with a forbidden subposet
• On crown-free families of subsets
• Largest families without an \(r\)-fork
• Supersaturation, counting, and randomness in forbidden subposet problems
• Set families with a forbidden induced subposet
• Progress on poset-free families of subsets
• On forbidden sets
• Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method)
• scientific article; zbMATH DE number 4041978 (Why is no real title available?)
• Sperner type theorems with excluded subposets
• Diamond-free subsets in the linear lattices
• Turán problems on non-uniform hypergraphs
• Set families with forbidden subposets
• Boolean algebras and Lubell functions
• Supersaturation and stability for forbidden subposet problems.
• Schröder partitions, Schröder tableaux and weak poset patterns
• The method of double chains for largest families with excluded subposets
• An improvement of the general bound on the largest family of subsets avoiding a subposet
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Some Motzkin-Straus type results for non-uniform hypergraphs
• Uniform chain decompositions and applications
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• The covering lemma and q-analogues of extremal set theory problems
• On some extremal and probabilistic questions for tree posets
• Diamond-free families
• Supersaturation, counting, and randomness in forbidden subposet problems
• Intersecting V-free, -free families
• A note on vertex Turán problems in the Kneser cube
• Families of subsets without a given poset in double chains and Boolean lattices
• \(Q _{2}\)-free families in the Boolean lattice
• Generalized forbidden subposet problems
• Incomparable copies of a poset in the Boolean lattice.
• An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
• Exact forbidden subposet results using chain decompositions of the cycle

This page was built for publication: On families of subsets with a forbidden subposet

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