##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 136.44901

**Autor: ** Erdös, Pál; Moser, L.

**Title: ** On the representation of directed graphs as unions of orderings (In English)

**Source: ** Publ. Math. Inst. Hung. Acad. Sci., Ser. A 9, 125-132 (1964).

**Review: ** In this paper an m × 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 × 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 × n R-matrix. The main object of this paper is to obtain estimates for m(n). *R.Stearns* (Zbl 090.25101) proved that m(n) > c_{2}n/ log n, the authors prove that m(n) \leq c_{1}n/ log n (where c_{1},c_{2} are fixed positive constants). The paper is concluded with a number of unsolved problems.

**Reviewer: ** J.Sedlácek

**Classif.: ** * 05C50 Graphs and matrices

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag