A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set SS of cardinality nn, and an assignment of intervals of the discrete set {1,…,n}{1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n}f:S→{1,…,n} such that for each element of F, its image under ff is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.