On finding the bidimension of a relation (Q1099113)

For an arbitrary data matrix, a problem is how to construct a representation according to the conjunctive model. This paper concerns with the problem of finding the minimum dimensionality needed for such a representation. In their fundamental paper, \textit{J. P. Doignon}, \textit{A. DuCamp} and \textit{J. C. Falmagne}, ibid. 28, 73-109 (1984; Zbl 0562.92018), cast the problem in terms of the intersection of a minimal number of biorders, this number being its so-called bidimension. Doignon et al. give a characterization of this bidimension as the chromatic number of a certain hypergraph. This paper describes some principles enabling to reduce a hypergraph of the considered type to a subhypergraph having the same chromatic number. The chromatic number of hypergraph can be recursively determined in terms of the chromatic number of its subhypergraphs. These reductions and recursions can be used to compute the bidimension of data sets. Prospects for integrating these results in an efficient algorithm complete the paper.