Acyclic sets in \(k\)-majority tournaments (Q547779)

Summary: When \(\Pi \) is a set of \(k\) linear orders on a ground set \(X\), and \(k\) is odd, the \(k\)- majority tournament generated by \(\Pi \) has vertex set \(X\) and has an edge from \(u\) to \(v\) if and only if a majority of the orders in \(\Pi \) rank \(u\) before \(v\) Let \(f_{k}(n)\) be the minimum, over all \(k\)-majority tournaments with \(n\) vertices, of the maximum order of an induced transitive subtournament. We prove that \(f_{3}(n) \geq n\) always and that \(f_{3}(n) \leq 2 \sqrt {n - 1}\) when \(n\) is a perfect square. We also prove that \(f_{5(n)} \geq n^{1/4}\). For general \(k\), we prove that \(n^{ck}\leq f_{k(n)} \leq n^{d_{k(n}})\), where \(c_k = 3^{-(k - 1)/2}\) and \(d_{k}(n) \rightarrow {{1+lg lg k}\over{-1+lg k}}\) as \(n \rightarrow \infty \).