Induced and non-induced forbidden subposet problems

MaRDI QIDQ2256127zbMATH OpenFDO

Authors Balázs Patkós

Publication date 19 February 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0899, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal set systemsforbidden subposets

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35) Extremal set theory (05D05) Combinatorics of partially ordered sets (06A07)

Abstract: The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $L{a}^{\ast }(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.

Review text

Summary: The problem of determining the maximum size \(\mathrm{La}(n,P)\) that a \(P\)-free subposet of the Boolean lattice \(B_n\) can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of \(\mathrm{La}^\ast(n,P)\), the maximum size that an induced \(P\)-free subposet of the Boolean lattice \(B_n\) can have for the case when \(P\) is the complete two-level poset \(K_{r,t}\) or the complete multi-level poset \(K_{r,s_{1},\dots,s_{j},t}\) when all \(s_i\)'s either equal 4 or are large enough and satisfy an extra condition.~We also show lower and upper bounds for the non-induced problem in the case when \(P\) is the complete three-level poset \(K_{r,s,t}\). These bounds determine the asymptotics of \(\mathrm{La}(n,K_{r,s,t})\) for some values of \(s\) independently of the values of \(r\) and \(t\).

Recommendations

• Generalized forbidden subposet problems
• On families of subsets with a forbidden subposet
• Forbidden induced subposets of given height
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Set families with forbidden subposets

Cites work

• A note on the largest size of families of sets with a forbidden poset
• Bounds on maximal families of sets not containing three sets with \(A\cap B \subset C\), \(A \not\subset B\)
• Diamond-free families
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• Largest family without A B C D
• On a lemma of Littlewood and Offord
• On families of subsets with a forbidden subposet
• Set families with a forbidden induced subposet
• Set families with forbidden subposets
• The method of double chains for largest families with excluded subposets
• The partition method for poset-free families

Cited in

(20)

• On extremal orthoposets without forbidden substructures
• On the forbidden induced subgraph probe and sandwich problems
• Forbidden subposet problems with size restrictions
• An upper bound on the size of diamond-free families of sets
• The saturation number of induced subposets of the Boolean lattice
• Induced and non-induced poset saturation problems
• Forbidden subposet problems in the grid
• Rainbow Ramsey problems for the Boolean lattice
• Improved bounds for induced poset saturation
• Forbidding rank-preserving copies of a poset
• On forbidden poset problems in the linear lattice
• Boolean lattices: Ramsey properties and embeddings
• Supersaturation, counting, and randomness in forbidden subposet problems
• Existence thresholds and Ramsey properties of random posets
• 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
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Supersaturation, counting, and randomness in forbidden subposet problems
• Families of subsets without a given poset in double chains and Boolean lattices
• Exact forbidden subposet results using chain decompositions of the cycle

This page was built for publication: Induced and non-induced forbidden subposet problems

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