Tournaments and Generalized Score Sequences (20??)

Originators: Folklore?    (presented by G. Isaak - REGS 2010)

Definitions: An oriented graph is an orientation of a (simple) graph; the edges, having distinct unordered pairs of two vertices, are turned into ordered pairs. The outdegree of a vertex v, written d+(v) is the number of such ordered pairs in which it appears first, and the indegree is the number in which it appears second.

A tournament is an orientation of a complete graph, modeling a "round-robin tournament", in which each team plays each other exactly once, with a winner declared. From this perspective, an oriented graph models a round-robin tournament with ties. In a FIFA round-robin tournament (World Cup soccer), the score of a team is 3 times the number of wins plus the number of ties. The FIFA score of a vertex v in an oriented n-vertex graph is thus 3d+(v)+(n-1-d+(v)-d¯(v)). The FIFA score list of an oriented is the list of FIFA scores of its vertices. In an ordinary tournament, there are no ties and the score is the number of wins.

Problem 1: Characterize integer lists that can occur as the FIFA score list of some oriented graph, or show that the problem of recognizing such lists is NP-complete.

Comments: This problem has probably been asked many times. A related problem is shown to be NP-complete in [Pal]. For ordinary n-vertex tournaments, Landau [L] characterized the realizable score lists as the nondecreasing nonnegative integer n-tuples d such that i=1kdi ≥ k(k-1)/2 for each k and the full sum equals n(n-1)/2. This characterization has many proofs.

Characterizations are also known for (outdegree,indegree)-lists of digraphs (allowing any multiplicity for each ordered pair). For a given graph G, network flow can be used to determine if there is an orientation with specified outdegrees and indegrees, and Hakimi [H] gave a necessary and sufficient condition.

Oriented graphs correspond to tournaments with ties scored by 1,0,-1 points for win,tie,loss, respectively; see [MWW] for essentially this situation. When the scores give consecutive integer weights to the three outcomes, characterizations of the realizable score lists follow from linear programming duality. Variations of Problem 1 can be asked for any weighting of the three outcomes.

Problem 2: Find interesting sufficient conditions or special classes of FIFA lists that can be characterized.

Problem 3: Characterize (outdegree,indegree) lists for oriented graphs. (A summer 2010 REU at Lafayette has done this when each team has at most one tie.)

Problem 4: Describe a collection of `elementary switching operations' so that any two tournaments with the same FIFA score can be obtained from each other using these operations.

Comments: For ordinary tournaments, Ryser [R] proved that each tournament with given vertex scores can be obtained from any other with the same vertex scores by iteratively reversing the direction on cycles of length 3; for analogous results involving reversal of cycles of other lengths, see [W] and [T].

References:
[H] S. L. Hakimi, On the degrees of the vertices of a directed graph. {\it J. Franklin Inst.} 279 (1965), 290-308.
[L] Landau, H. G. On dominance relations and the structure of animal societies. III. The condition for a score structure. Bull. Math. Biophys. 15, (1953). 143-148.
[MWW] Mubayi, Dhruv; Will, Todd G.; West, Douglas B.; Realizing degree imbalances in directed graphs. Discrete Math. 239 (2001), no. 1-3, 147-153.
[Pal] Palvolgyi, Domotor; Deciding Soccer Scores and Partial orientations of graphs, Acta Univ. Sapientiae, Mathematica, 1 (2009) 35-42.
[R] Ryser, H. J. Matrices of zeros and ones in combinatorial mathematics, in Recent Advances in Matrix Theory (Proc. Advanced Seminar, Math. Res. Center, U.S. Army, Univ. Wisconsin, Madison, Wis., 1963) (Univ. Wisconsin Press, Madison, Wis., 1964) 103-124.
[T] Thomassen, Carsten; Arc reversals in tournaments. Discrete Math. 71 (1988), no. 1, 73-86.
[W] Waldrop, Clay, Jr. An ARC-reversal theorem for tournaments. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp. 501-507. Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976.