×

On a set of relations arising from the triangulation problem. (English) Zbl 0569.08001

The classical triangulation problem can be formulated as follows: Given a real-valued \(n\times n\)-matrix \((a_{ij})\) find some \(\pi \in S_ n\) such that \(\sum_{i<j}a_{\pi i,\pi j}=\max_{\sigma \in S_ n}\sum_{i<j}a_{\sigma i,\sigma j}\). \((a_{ij})\) is called triangulated if for all \(\sigma \in S_ n\) \(\sum_{i<j}a_{ij}\geq \sum_{i<j}a_{\sigma i,\sigma j}\). The latter is equivalent to \(\sum_{(i,j)\in F}(a_{ij}-a_{ji})\geq 0\) for all \(F\in {\mathcal F}\) where \({\mathcal F}:=\{\{(i,j)|\) \(i<j\); \(\sigma i>\sigma j\}|\) \(\sigma \in S_ n\}\). The elements of \({\mathcal F}\) are characterized as relations and ordered in such a way that they form an ortholattice. Moreover, so-called ”indecomposable” elements of \({\mathcal F}\) (among which there are the join-irreducibles of the lattice \({\mathcal F})\) are studied which could also be useful for practical applications.

MSC:

08A02 Relational systems, laws of composition
06C15 Complemented lattices, orthocomplemented lattices and posets
15A21 Canonical forms, reductions, classification
PDFBibTeX XMLCite