On the representation of directed graphs as unions of orderings. (English) Zbl 0136.44901

In this paper an \(m \times n \) matrix \(R\) is considered in which each row consists of a permutation of the integers \(1,2,...,n\). Such matrix is called the \(m \times n\; R\)-matrix (or briefly the \(R\)-matrix). We define an oriented graph on the vertices \(1,2,...,n,\) in which there is an edge oriented from \(i\) to \(j\) provided \(i\) precedes \(j\) in a majority of the rows of \(R\). If \(i\) precedes \(j\) as often as \(j\) precedes \(i\), the vertices \(i,j\) are not joined by an edge. McGarvey [Econometrica 21, 608-610 (1953), dated erroneously 1963 by the authors] proved that every oriented graph in which every pair of vertices are joined by at most one edge can be realized as a graph associated with some \(R\)-matrix in this manner. Denote by \(m(n)\) the smallest number such that every graph on \(n\) vertices corresponds to some \(m \times n\) \(R\)-matrix. The main object of this paper is to obtain estimates for \(m(n)\). R.Stearns (Zbl 0090.25101) proved that \(m(n) > c_2n/\log n\), the authors prove that \(m(n) \leq c_1n/\log n\) (where \(c_1,c_2\) are fixed positive constants). The paper is concluded with a number of unsolved problems.
Reviewer: J.Sedláček


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)




Zbl 0090.25101