On finding the bidimension of a relation

Abstract

A method is presented for evaluating the bidimension of a finite binary relation, i.e., the number of biorders (Guttman relations) needed to yield the relation as their intersection. In case the relation is induced by a binary data matrix, the bidimension equals the minimal number of dimensions needed for a representation of the data matrix according to the conjunctive model of C. H. Coombs and R. C. Kao (Nonmetric factor analysis, Engineering Research Bulletin No. 38, Univ. of Michigan Press, Ann Arbor, 1955). Central to the evaluation of the bidimension is its characterization, provided by J.-P. Doignon, A. Ducamp, and J.-C. Falmagne (Journal of Mathematical Psychology, 28, 73–109, 1984), as the chromatic number of some associated hypergraph. A procedure is described to reduce hypergraphs of this kind to subhypergraphs with the same chromatic number. This reduction can be used throughout in applying a recurrence relation that expresses the chromatic number of a hypergraph in terms of the chromatic numbers of some of its subhypergraphs.