A survey on finding Kings in tournaments

Arghya Chakraborty
Friday, 20 Jan 2023, 16:00 to 17:00
In any tournament between several participants, transitivity is sometimes not satisfied (i.e. A may defeat B, B defeats C and C in turn defeats A). In any case, we shall have to define a winner. We shall first define the notion of a 'king' in a tournament graph and then show that one can find a king by organizing O(n^{3/2}) matches when there are n participants. Also, we shall show that at least \Omega(n^{4/3}) matches need to be organized in the worst case.

The results that I will go over are mostly from https://epubs.siam.org/doi/abs/10.1137/S0097539702410053.