A minimal cutset of the Boolean lattice with almost all members
type: Item
instance of: scholarly article
title: A minimal cutset of the Boolean lattice with almost all members
zbMATH Open document ID: 0687.05002
DOI: 10.1007/BF01788687
author: Daniel J. Kleitman
author: Zoltán Füredi
author: J. Griggs
published in: Graphs and Combinatorics
publication date: 1989-01-01T00:00:00Z
review text: The authors consider cutsets in the lattice of subsets of a finite set, where cutting means intersecting all maximal chains. They show that there exist minimal cutsets containing a fraction arbitrarily close to 1 of all subsets. They start with the cutset associated with a partition of the total set into subsets \(S_ i\) consisting of all subsets which either contain a nonempty proper subset of every \(S_ i\) or contain all of some \(S_ i\), none of some \(S_ j\). Then by a probabilistic argument they show a small subset can be removed to make it minimal.
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4125406
zbMATH Keywords: Boolean lattice
zbMATH Keywords: cutsets
zbMATH Keywords: maximal chains
reviewed by: Ki Hang Kim
MaRDI profile type: Publication
cites work: Sphere coverings of the hypercube with incomparable centers
cites work: Antichains and Finite Sets that Meet all Maximal Chains
cites work: Cutsets of Boolean lattices
cites work: Q5641810
cites work: Finite cutsets and finite antichains
full work available at URL: https://doi.org/10.1007/bf01788687
OpenAlex ID: W1987434516
description: scientific article; zbMATH DE number 4125406