Tata Institute of Fundamental Research
A survey on finding Kings in tournaments
STCS Student Seminar
Speaker:
Arghya Chakraborty
Date:
Friday, 20 Jan 2023, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Arghya Chakraborty |
| Date: | Friday, 20 Jan 2023, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
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.
The results that I will go over are mostly from https://epubs.siam.org/doi/abs/10.1137/S0097539702410053.