Induced and non-induced forbidden subposet problems

zbMATH Open1307.05217arXiv1408.0899MaRDI QIDQ2256127FDOQ2256127

Authors: Balázs Patkós 

Publication date: 19 February 2015

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

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

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

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

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

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)

Cites Work

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

Cited In (19)

• 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
• Supersaturation, counting, and randomness in forbidden subposet problems

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)