On the Distribution of 4-Cycles in Random Bipartite Tournaments

Canadian mathematical bulletin, Tome 5 (1962) no. 1, pp. 5-12

Résumé

Let there be given two sets of points, P = {P1,..., Pm}1 m and Q={Q1,..., Qn}, such that joining each pair of points (Pi, Qk), for i=1,..., m and k=1..., n, is a line oriented towards one, and only one, of the pair. Such a configuration will be called an m×n bipartite tournament. If the line joining Pi to Qk is oriented towards Qk we may indicate this by pi→Qk, and similarly if the line is oriented in the other sense. The points Pi, Pj, Qk, and Ql. will be said to form a 4-cycle if either Pi→Qk→Pj→Ql→Pi or Pi→Ql→Pj→Qk→Pi. C(m, n), the number of 4-cycles in a given m×n bipartite tournament, provides, in some sense, a measure of the degree of transitivity of the relationship indicated by the orientation of the lines, and the complete configuration may be thought of as representing the outcome of comparing each member of one population with each member of a second population, and making a decision, upon some basis, as to which component of each pair is the preferred one.

Détail

DOI : 10.4153/CMB-1962-002-0