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) > c2n/ log n, the authors prove that m(n) \leq c1n/ log n (where c1,c2 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