How Many Pairwise Preferences Do We Need to Rank A Graph Consistently?

Aadirupa Saha, Rakesh Shivanna, Chiranjib Bhattacharyya

We consider the problem of optimal recovery of true ranking of $n$ items from a randomly chosen subset of their pairwise preferences. It is well known that without any further assu…