On the Distribution of 4-Cycles in Random Bipartite Tournaments

Extract

Let there be given two sets of points, P = {P₁,…, P_m}1 m and Q={Q₁,…, Q_n}, such that joining each pair of points (P_i, Q_k), 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 P_i to Q_k is oriented towards Q_k we may indicate this by p_i→Q_k, and similarly if the line is oriented in the other sense. The points P_i, P_j, Q_k, and Q_l. will be said to form a 4-cycle if either P_i→Q_k→P_j→Q_l→P_i or P_i→Q_l→P_j→Q_k→P_i. 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.