Lattices of cuts in graphs (Q1187152): Difference between revisions

Let \(a\), \(b\) be non-adjacent vertices of a graph \(G\). A subset \(C\subseteq V(G)\) containing neither \(a\) nor \(b\) is called an \(a,b\)-cut if it separates these two vertices but no proper subset of \(C\) also has this property. Let \({\mathcal C}_ G(a,b)\) denote the collection of all \(a,b\)-cuts in \(G\) and for any cardinal \(\delta\) the set of all \(a,b\)-cuts of cardinality at most \(\delta\) or strictly less than \(\delta\) will be denoted by \({\mathcal C}_ G(a,b;\leq\delta)\) and \({\mathcal C}_ G(a,b;<\delta)\), respectively. Let \(C\), \(C'\in{\mathcal C}_ G(a,b)\). Then \(C\) is called a predecessor of \(C'\) denoted by \(C\trianglelefteq C'\) if there is no path from \(a\) to a vertex of \(C'\) which avoids \(C\). It is known that \({\mathcal C}_ G(a,b)\) forms a complete lattice with respect to \(\trianglelefteq\) and that every complete lattice appears as such a cut- lattice. If \({\mathcal M}\) is a subset of \({\mathcal C}_ G(a,b)\), then \({\mathcal L}({\mathcal M})\) denotes the sublattice of \({\mathcal C}_ G(a,b)\) generated by \({\mathcal M}\); i.e. \({\mathcal L}({\mathcal M})\) is the smallest subset of \({\mathcal C}_ G(a,b)\) containing \({\mathcal M}\) which is closed under forming the supremum (sup) and infimum (inf) of any pair of elements. A subset \(S\) of a complete lattice \(L\) will be called relatively complet in \(L\) if for any nonempty family of elements of \(S\) its sup and inf (with respect to \(L)\) again belong to \(S\). Thus if \(S\) is nonempty, then it forms a complete lattice and is faithful in \(L\) with respect to forming suprema and infima of nonempty families; but its unit- and zero-element may be different from the unit- and zero-element, respectively, of \(L\). For \(M\subseteq L\) there is a relatively complete hull in \(L\), formed from the suprema and infima of all nonempty families of elements in \(M\). The empty set is defined to be a sublattice and to be relatively complete in \(L\). For any \({\mathcal M}\subseteq{\mathcal C}_ G(a,b)\) its relatively complete hull will be denoted by \({\mathcal L}^ c({\mathcal M})\). Then \({\mathcal L}({\mathcal M})\subseteq{\mathcal L}^ c({\mathcal M})\) and both are empty if \({\mathcal M}=\varnothing\). The author is interested in determining what can be said about the cardinalities of \({\mathcal L}({\mathcal M})\) and \({\mathcal L}^ c({\mathcal M})\) (for \({\mathcal M}\subseteq{\mathcal C}_ G(a,b))\) if restrictions are placed on the cardinalities of \({\mathcal M}\) and on the members of \({\mathcal M}\). In particular, it is shown that \({\mathcal C}_ G(a,b;<\omega)\) (where \(\omega\) is the smallest infinite cardinal), is at most countable and a sublattice of \({\mathcal C}_ G(a,b)\); if it is countable then it is never relatively complete and its relatively complete hull arises by adding certain countable \(a,b\)-cuts. It is shown constructively that \({\mathcal L}^ c({\mathcal C}_ G(a,b;\omega))\) may have cardinality \(2^ \omega\). Moreover, in the case that \({\mathcal C}_ G(a,b;\omega)\) is infinite certain minimal configurations must be present. Suppose now that \(\delta\) is an infinite cardinal and consider \({\mathcal C}_ G(a,b;\leq\delta)\). It is shown that there exists a graph \(A\) with \(a,b\in V(A)\subseteq V(G)\) having cardinality at most \(\delta\) such that \({\mathcal C}_ A(a,b)\) is identical with \({\mathcal C}_ G(a,b;\leq\delta)\). As consequences it follows that \(|{\mathcal C}_ G(a,b;\leq\delta)|\leq 2^ \delta\) and that \({\mathcal C}_ G(a,b;\leq\delta)\) is always relative complete in \({\mathcal C}_ G(a,b)\). In closing, an extension of these investigations to edge-cuts is discussed.