Acyclic Subgraphs in $k$-Majority Tournaments

Abstract

A $k$-majority digraph is a directed graph created by combining $k$ individual rankings on the same ground set to form a consensus where edges point in the direction indicated by a strict majority of the rankings. The $k$-majority digraph is used to model voting scenarios, where the vertices correspond to options ranked by $k$ voters. When $k$ is odd, the resulting digraph is always a tournament, called $k$-majority tournament. Let $f_k(n)$ be the minimum, over all $k$-majority tournaments with $n$ vertices, of the maximum order of an induced transitive sub-tournament. Recently, Milans, Schreiber, and West proved that $\sqrt{n}\le f_3(n)\le 2\sqrt{n}+1$. In this paper, we improve the upper bound of $f_3(n)$ by showing that $f_3(n)<\sqrt{2n}+\frac{1}{2}$.