Maximal chains and cutsets of an ordered set: A Menger type approach (Q1123914): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compact Spaces and Spaces of Maximal Complete Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Antichains and Finite Sets that Meet all Maximal Chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Antichain cutsets / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf00354896 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2053903296 / rank | |||
Normal rank |
Latest revision as of 09:44, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximal chains and cutsets of an ordered set: A Menger type approach |
scientific article |
Statements
Maximal chains and cutsets of an ordered set: A Menger type approach (English)
0 references
1988
0 references
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).
0 references
cutset
0 references
disjoint family
0 references
Menger family
0 references
Menger's theorem
0 references
maximal chains
0 references