Families of subsets without a given poset in double chains and Boolean lattices
type: Item
instance of: scholarly article
title: Families of subsets without a given poset in double chains and Boolean lattices
zbMATH Open document ID: 1406.06003
author: Junyi Guo
author: Hongbin Chen
author: Wei-Tian Li
author: Fei-Huang Chang
published in: Order
publication date: 2018-07-27T00:00:00Z
review text: The paper under review studies, for a given finite partially ordered set (poset) \(P\), the quantity \(\mathrm{La}(n,P)\), the largest size of a family of subsets of \([n]=\{1,2,\dots ,n\}\) which does not contain \(P\) as a weak subposet. It was shown in [\textit{P. Burcsi} and \textit{D. T. Nagy}, Electron. J. Graph Theory Appl. 1, No. 1, 40--49 (2013; Zbl 1306.05239)] that \(\mathrm{La}(n,P)\leq \frac{1}{2} (| P|+h(P)-2){n\choose n/2}\) where \(| P|\) is the number of vertices of \(P\) and \(h(P)\) denotes the height of \(P\). The contribution of the paper under review is to replace this by the better upper bound \(\mathrm{La}(n,P)\leq \frac{1}{2} (| P|+h(P)-\alpha(G_{P})-2){n\choose n/2}\) in the special case that \(P\) is graded, where \(\alpha (G_{P})\) is the independence number of a certain auxiliary graph associated with \(P\). The proofs build on those in the article of Bursi and Nagy [loc. cit.]. This allows the authors to find further examples of posets supporting a conjecture from [\textit{J. R. Griggs} and \textit{L. Lu}, Comb. Probab. Comput. 18, No. 5, 731--748 (2009; Zbl 1215.05082)].
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 06B05
zbMATH DE Number: 6911232
zbMATH Keywords: extremal family
zbMATH Keywords: poset-free families
zbMATH Keywords: double counting
zbMATH Keywords: interval chains
zbMATH Keywords: graded poset
reviewed by: David B. Penman
MaRDI profile type: Publication
full work available at URL: s11083-017-9436-1
OpenAlex ID: W2753635756
cites work: Set families with a forbidden subposet
cites work: The method of double chains for largest families with excluded subposets
cites work: A note on the largest size of families of sets with a forbidden poset
cites work: The complexity of theorem-proving procedures
cites work: Largest families without an \(r\)-fork
cites work: Largest family without \(A \cup B \subseteq C \cap D\)
cites work: On a lemma of Littlewood and Offord
cites work: No four subsets forming an \(N\)
cites work: Poset-free families and Lubell-boundedness
cites work: Diamond-free families
cites work: An improvement of the general bound on the largest family of subsets avoiding a subposet
cites work: An upper bound on the size of diamond-free families of sets
cites work: Reducibility among Combinatorial Problems
cites work: Q3315539
cites work: On diamond-free subposets of the Boolean lattice
cites work: On crown-free families of subsets
cites work: A short proof of Sperner's lemma
cites work: Exact forbidden subposet results using chain decompositions of the cycle
cites work: A Dual of Dilworth's Decomposition Theorem
cites work: Induced and non-induced forbidden subposet problems
cites work: Diamond-free subsets in the linear lattices
cites work: An extremal problem with excluded subposet in the Boolean lattice
DOI: 10.1007/S11083-017-9436-1
description: scientific article; zbMATH DE number 6911232