On the representation of directed graphs as unions of orderings

Erdős, P. and Moser, L. (1964) On the representation of directed graphs as unions of orderings. A MAGYAR TUDOMÁNYOS AKADÉMIA MATEMATIKAI KUTATÓ INTÉZETÉNEK KÖZLEMÉNYEI, 9 (1-2). pp. 125-132.

Preview

Text cut_MATKUTINT_1964_1_-_2_pp125_-_132.pdf - Published Version Download (3MB) | Preview

Abstract

Consider an m * n matrix in which each row consists of a permutation of the integers 1,2, . . . , n . Such matrices will be called A-matrices (they really should have been called m * n R-matrices, but where there is no danger of confusion we omit the mxn). Corresponding to such a matrix R we define an oriented graph on the vertices 1, 2, . . . , n, in which there is an edge oriented from i to j (notation: i ⭢ 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 and j are not joined by an edge. It has been known for some time [1] that every directed graph in which every pair of vertices are joined by at most one oriented edge can be realized as a graph associated with some R-matrix in this manner. The principal object of this paper is to obtain relatively sharp estimates for the smallest number m(n) such that every oriented graph on n vertices corresponds t o some m * n matrix of the type described. This as well as some related problems which we will treat arise from questions concerning methods of combining individual transitive preferences on a set of alternatives by means of majority decisions. Thus we may think of the rows of the matrix R as representing orderings by individual voters, of a set of n candidates 1, 2, . . . , n in order of preference. Although each voter thus expresses a set of transitive preferences, the majority opinion need not be transitive and indeed we will prove that every preference pattern (ties permitted) may be achieved by no more than c₁ n/log n voters, (c₁ a fixed constant), i.e. m(n) ≦ c₁ n/log n. On the other hand it was shown in a relatively simple way by Stearns [2] that some preference patterns on n candidates cannot be schieved by c₂ n/log n voters (where c₂ is another fixed positive constant) so that m(n) > c₂ n/log n. In § 1 we consider the following problem: What is the largest number f(n) such that every oriented graph on n vertices in which every pair of distinct vertices is jointed by a directed edge has at least one subgraph of f(n) vertices in which the orientation is transitive, i.e. in which i ⭢ j and j ⭢ k implies i ⭢ k. Our result here is that f(n) ≦ [ log₂ n ] + 1. In § 2 we will develop some lemmas concerning oriented graphs which can be represented by 2 * n R-matrices. In the voting terminology this means that we study the preference patterns of candidates that can be achieved by a pair of voters — we will call them a couple. The point in considering such pairs of voters is that by balancing their transitive preferences in a certain way the pair of voters can achieve a preference between certain pairs of candidates in the manner in which these pairs are to be preferred by the majority, while with respect to all other pairs the preferences of the couple cancel one another. In § 3 we relate the graph theoretic lemmas of § 2 to the problem of estimating m(v) and obtain the result c₁ n/log n > m(n) > c₂ n/log n . We conclude with a number of unsolved problems.

Actions (login required)

Edit Item