[25] Let T be a tournament on N = {1,...,n}. Define a ranking R as an ordering of N. For (i, j) ∈ T , if R(i) < R(j), we say that R agrees with (i, j). Otherwise, it disagrees with that edge. We are interested in a ranking that is most consistent with T , that is, such that the number of edges that agree with R is maximized. Show that for large enough n, there exist tournaments such that any ranking disagrees with at least 49% of its edges.

Comments. A simple incompressibility argument is given by M. Fouz and P. Nicholson [CS798 Course Report, University of Waterloo, December 2007]. Relevant literature on this problem can be found in [N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 2000, p. 134].