Families of subsets without a given poset in double chains and Boolean lattices
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)].
scientific article; zbMATH DE number 6911232
scientific article