Maximal chains and cutsets of an ordered set: A Menger type approach
type: Item
instance of: scholarly article
title: Maximal chains and cutsets of an ordered set: A Menger type approach
zbMATH Open document ID: 0678.06001
DOI: 10.1007/BF00354896
author: J.-M. Brochet
author: Maurice Pouzet
published in: Order
publication date: 1988-01-01T00:00:00Z
review text: A cutset of a family of non-empty sets \({\mathcal F}\) is a subset \(S\subseteq \cup {\mathcal F}\) which has a non-empty intersection with each member F of \({\mathcal F}\). \({\mathcal F}\) is a disjoint family if the members of \({\mathcal F}\) are pairwise disjoint: cut(\({\mathcal F})=\min \{| S|:\) S is a cutset of \({\mathcal F}\}\), disj(\({\mathcal F})=\sup \{| {\mathcal F}'|:\) \({\mathcal F}'\subseteq {\mathcal F}\) and \({\mathcal F}'\) disjoint\(\}\). The family \({\mathcal F}\) is a Menger family if cut(\({\mathcal F})=disj({\mathcal F}).\) Menger's theorem can be stated in the following way: If A, B are sets of vertices in a finite directed graph, then the set of all (A,B)-paths is a Menger family. (An (A,B)-path is the set of vertices of a path starting in A and ending in B.) The following results related to Menger's theorem for (infinite) ordered sets are obtained: (1) If the space of maximal chains of an ordered set is compact, then the maximum number of pairwise disjoint maximal chains is finite and is equal to the minimum size of a cutset (i.e. a set which meets all maximal chains). (2) If the maximal chains pairwise intersect, then the intersection of finitely many is never empty. (3) If the maximal chains pairwise intersect and if one of the maximal chains is complete, then there is an element common to all maximal chains. The reader may also want to consult the paper of \textit{R. Aharoni}, \textit{J.-M. Brochet} and \textit{M. Pouzet} reviewed below (see Zbl 0678.06002).
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 54D30
zbMATH DE Number: 4110753
zbMATH Keywords: cutset
zbMATH Keywords: disjoint family
zbMATH Keywords: Menger family
zbMATH Keywords: Menger's theorem
zbMATH Keywords: maximal chains
MaRDI profile type: Publication
cites work: Compact Spaces and Spaces of Maximal Complete Subgraphs
cites work: A decomposition theorem for partially ordered sets
cites work: Antichains and Finite Sets that Meet all Maximal Chains
cites work: Antichain cutsets
full work available at URL: https://doi.org/10.1007/bf00354896
OpenAlex ID: W2053903296
Recommended article: The Menger property for infinite ordered sets
Recommended article: Q3972097
Recommended article: Q3726173
Recommended article: Infinite ordered sets spanned by finitely many chains
Recommended article: A minimax theorem for chain complete ordered sets
Recommended article: Binary Trees and the n-Cutset Property
Recommended article: Finite cutsets and finite antichains
Recommended article: Maximal Chains and Antichains in Boolean Lattices
Recommended article: Q5689024
Recommended article: Minimax theorems for infinite graphs with the ends as ideal points
description: scientific article; zbMATH DE number 4110753