Interval orders without odd crowns are defect optimal (Q1079584): Difference between revisions

The defect of a (partial) order relation P is defined to be the rank of the kernel of the associated incidence matrix. \textit{G. Gierz} and \textit{W. Poguntke} [SIAM J. Algebraic Discrete Methods 4, 132-144 (1983; Zbl 0517.06004)] have shown that the defect provides a lower bound for the number of incomparable adjacent pairs in an arbitrary topological sorting of P. We show that this bound is sharp for interval orders without odd crowns. Furthermore, an efficient algorithm for topological sortings of such orders is presented which achieves the bound. We finally exhibit a natural matroid structure associated with the optimal topological sortings under consideration, which permits to solve the weighted case.