## 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
Show Scanned Page ### MSC:

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

topology

Zbl 0090.25101