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

forbidden subposetsextremal set systems

Mathematics Subject Classification ID

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

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$.

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

• scientific article; zbMATH DE number 3845613 (Why is no real title available?)
• 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
• 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
• 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

(19)

• Supersaturation, counting, and randomness in forbidden subposet problems
• Forbidding rank-preserving copies of a poset
• Existence thresholds and Ramsey properties of random posets
• On the forbidden induced subgraph probe and sandwich problems
• Families of subsets without a given poset in double chains and Boolean lattices
• The saturation number of induced subposets of the Boolean lattice
• Exact forbidden subposet results using chain decompositions of the cycle
• Induced and non-induced poset saturation problems
• On forbidden poset problems in the linear lattice
• An upper bound on the size of diamond-free families of sets
• Improved bounds for induced poset saturation
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Supersaturation, counting, and randomness in forbidden subposet problems
• Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems
• Boolean lattices: Ramsey properties and embeddings
• Forbidden subposet problems in the grid
• Rainbow Ramsey problems for the Boolean lattice
• Forbidden subposet problems with size restrictions
• An improvement of the general bound on the largest family of subsets avoiding a subposet

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)