Families of sets with locally bounded width
type: Item
instance of: scholarly article
title: Families of sets with locally bounded width
zbMATH Open document ID: 0811.06003
DOI: 10.1007/BF02986659
author: Emanuel Knill
published in: Graphs and Combinatorics
publication date: 1994-09-26T00:00:00Z
review text: The author establishes that if \(F\) is a family of subsets of the set \([n]= \{1,\dots, n\}\) such that for each \(x\in \bigcup F\), the poset \(F_ x= \{U\in F\mid x\in U\}\) (ordered by set inclusion) has width at most \(k\) (i.e., a maximal antichain contains at most \(k\) elements) then \(F\) is locally \(k\)-wide and \(| F|\leq (2k)^{k-1} n\). This result of a quite general nature follows from other results where additional restrictions are placed on the members of \(F\). It improves on simpler bounds obtained in the paper and depends on estimates and counting arguments involving families of closed sets also studied by the author, with the closure operations being the Sperner closures in the filters of \(F\), i.e., the intersections of the members of the greatest Sperner antichains containing elements of these filters in the filters themselves. The proof of the main theorem is an interesting application of the techniques used to prove the theorem, techniques which should prove useful in similar settings elsewhere.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 644732
zbMATH Keywords: posets
zbMATH Keywords: subsets
zbMATH Keywords: width
zbMATH Keywords: antichain
zbMATH Keywords: bounds
zbMATH Keywords: closure operations
zbMATH Keywords: filters
MaRDI profile type: Publication
cites work: A decomposition theorem for partially ordered sets
cites work: Q3274165
cites work: The structure of Sperner k-families
cites work: Q3992560
cites work: Q4138831
cites work: Q3979027
cites work: Extreme \(k\)-families
cites work: Q3748279
description: scientific article; zbMATH DE number 644732