Garth Isaak (Lehigh University)
If one ranks the players of a round robin tournament so as to minimize the number of inconsistiencies is it possible that in a tournament of 100 players that a subset of 35 will be ranked wrong, with the loser in each pair ranked higher? How about with ranking by number of wins?
The general problem is: given a ranking procedure for round robin tournaments and a digraph representing a pattern of inconsistencies when can that pattern arise? For ranking to minimize inconsistencies this is the same as determining `when' a given acyclic digraph is a feedback arc digraph of some larger tournament. In particluar we look at the smallest size of such a tournament. This talk will examine some recent and some less recent results on this problem including using tools like integer programming and possibly list coloring and providing explicit constructions of tournaments with gaps between the minimum size of a feedback arc set and the maximum size of an arc disjoint collection of directed cycles.
joint work with Darren Narayan