Maximal chains and cutsets of an ordered set: A Menger type approach (Q1123914): Difference between revisions

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).