Acyclic Subgraphs in $k$-Majority Tournaments

Details Acyclic Subgraphs in $k$-Majority Tournaments Acyclic Subgraphs in $k$-Majority Tournaments

2011-09-28

arxiv.org/abs/1109.6172v1

Mathematics

Combinatorics

Scientific paper

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 12 $.

Affiliated with

Also associated with

No associations

Rating

Acyclic Subgraphs in $k$-Majority Tournaments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acyclic Subgraphs in $k$-Majority Tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Subgraphs in $k$-Majority Tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-43521