Families of sets with locally bounded width

DOI10.1007/BF02986659MaRDI QIDQ1334941zbMATH OpenFDO

Authors Emanuel Knill

Publication date 26 September 1994

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02986659

zbMATH Keywords

antichainboundsclosure operationsfiltersposetssubsetswidth

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• Locally thin set families
• A better bound for locally thin set families
• Set families with a forbidden subposet

Cites work

• A decomposition theorem for partially ordered sets
• Extreme \(k\)-families
• scientific article; zbMATH DE number 3156376 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 19538 (Why is no real title available?)
• scientific article; zbMATH DE number 42741 (Why is no real title available?)
• scientific article; zbMATH DE number 3566976 (Why is no real title available?)
• The structure of Sperner k-families

Cited in

(7)

• Extreme \(k\)-families
• Locally thin set families
• Self-similarity bounds for locally thin set families
• Locally Finite Families, Completely Separated Sets and Remote Points
• scientific article; zbMATH DE number 2068118 (Why is no real title available?)
• scientific article; zbMATH DE number 1501228 (Why is no real title available?)
• A better bound for locally thin set families

This page was built for publication: Families of sets with locally bounded width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334941)