On Ramsey Properties of k-Majority Tournaments

This paper improves the known lower bound on the size of transitive subgraphs in $k$-majority tournaments from $n^{2^{-\Theta(k)}}$ to $n^{\Omega(1/k)}$, demonstrating an exponential improvement in the dependence of the exponent on $k$.

The Gist

Imagine you are at a massive, chaotic party with $n$ guests. In this party, every single person has a strong opinion about every other person: they either think Person A is "better" than Person B, or vice versa. There are no ties. In math-speak, this is called a tournament.

Usually, in such a chaotic crowd, it's very hard to find a group of people who all agree with each other in a perfect, logical chain (like a line of people where A > B > C > D). In a completely random party, the biggest group you can find that agrees perfectly is surprisingly small—only about the size of the logarithm of the total number of guests (roughly $\log n$). If you have a million guests, you might only find a group of 20 who fit this perfect chain.

The "Majority Vote" Twist

Now, imagine this party isn't random. Instead, every guest has a specific set of 2k - 1 different "lists" or "rankings" of everyone else.

• Maybe one list is based on height.
• Another is based on age.
• Another is based on how much they like pizza.

In this special party (called a k-majority tournament), Person A is considered "better" than Person B only if A appears higher than B in at least k of those lists. It's like a majority vote: if A beats B in more than half the categories, A wins the edge.

The big question the authors asked is: If we force the party to follow these "majority vote" rules, does the chaos disappear? Can we find a much larger group of people who form a perfect, logical chain?

The Old vs. New Discovery

For a long time, mathematicians knew that these "majority parties" were better than random ones. They knew you could find a chain of size roughly $n^{1/(\text{huge number})}$.

• The Old View: If you have a million people, the old math said you might find a chain of size $n^{1/1000}$. That's still a tiny number. The "exponent" (the power you raise $n$ to) was terrible; it depended on $k$ in a way that made the result shrink incredibly fast as the rules got more complex.

• The New Breakthrough (This Paper): The authors, Asaf Shapira and Raphael Yuster, proved that the situation is actually much better. They showed that the size of the perfect chain grows as $n^{1/k}$.

  • The Analogy: Think of the old result as finding a needle in a haystack where the haystack is a mountain. The new result says the haystack is actually just a small hill.
  • The Impact: If $k=2$ (a simple majority), the chain size is roughly the square root of $n$ ($\sqrt{n}$). If you have a million people, you can find a chain of 1,000 people! This is an exponential improvement over the previous understanding.

The "Bipartite" Secret Weapon

How did they do it? They didn't just look for a single line of people. They looked for a two-sided agreement.

Imagine splitting the party into two groups, Group A and Group B. They wanted to find a situation where every single person in Group A is considered "better" than every single person in Group B according to the majority vote.

• In math terms, this is a "transitive bipartite tournament."
• They proved that in these majority parties, you can always find two large groups (A and B) where A completely dominates B.
• Once you have this "A beats B" structure, you can use it like a ladder to climb up and find the long, single chain of agreement (the transitive tournament) much more easily.

They treated this like a game of "finding the perfect split." They showed that no matter how the lists are shuffled, you can always find a split where the "majority rule" creates a clean, one-way street from one group to the other.

The Random Guessing Game

The paper also looked at what happens if the lists are generated completely at random.

• The Question: If we just throw darts at the lists, how big of a perfect chain can we expect?
• The Result: Even with random lists, the "majority" rule creates order. For the simplest case ($k=2$), they proved the largest chain is roughly $n^{2/3}$. This is smaller than the guaranteed minimum for any majority party, but it's still huge compared to the random chaos of a normal tournament.

Why Does This Matter?

This paper is a victory for Ramsey Theory, a branch of math that asks: "How much order is forced to exist in a large system, even if we try to make it messy?"

• The Takeaway: Even if you try to create a complex, messy voting system with many different criteria, you cannot completely destroy the underlying order. There will always be a surprisingly large group of people who agree perfectly with each other.
• The Metaphor: Imagine trying to build a tower of blocks where every block is slightly tilted. You might think the tower will fall immediately. But this paper proves that if you follow the "majority tilt" rules, the tower is actually much more stable than you thought, and you can build it much taller than anyone previously believed possible.

In short: Chaos is inevitable, but in a "majority vote" world, order is much stronger and larger than we ever imagined.

Technical Summary

Here is a detailed technical summary of the paper "On Ramsey Properties of k-Majority Tournaments" by Asaf Shapira and Raphael Yuster.

1. Problem Statement and Context

Ramsey Theory in Tournaments:
In standard Ramsey theory, a central question is determining the size of the largest homogeneous substructure (a clique or independent set in graphs; a transitive subtournament in directed graphs) guaranteed within a structure of size $n$. For general $n$-vertex tournaments, it is known that the largest transitive subtournament has size $\Theta(\log n)$, and this bound is tight.

Restricted Families:
The paper investigates whether restricting the family of tournaments yields significantly larger homogeneous sets. Specifically, it focuses on $k$-majority tournaments.

• Definition: A $k$-majority tournament is generated by $2k-1$linear orders (permutations) of a vertex set$X$. An edge exists from$u$to$v$if$u$precedes$v$in at least$k$ of these orders.
• Prior Work: Milans, Schreiber, and West [11] established that $k$-majority tournaments contain transitive subtournaments of size $n^{1/c_k}$, where $c_k$ was bounded by $3k-1$(lower bound) and roughly$k/\ln k$(upper bound). This implied a size of$n^{2-\Theta(k)}$.
• The Gap: The dependence of the exponent on $k$ was doubly exponential in the gap between known bounds. The authors aim to exponentially improve the lower bound on the size of the transitive subtournament.

2. Methodology

The authors employ a multi-faceted approach combining combinatorial induction, probabilistic methods, and structural graph theory:

1. Bipartite Variants: The core technical innovation is shifting the focus from finding a transitive set $T_t$ to finding a transitive bipartite tournament $T_{t,t}$ (an orientation of $K_{t,t}$ where all edges go from one part to the other).

   • They define parameters $b_k(n)$ (largest $T_{t,t}$), $d_k(n)$ (largest $T_{t,t}$ where one set majority dominates the other), and $d^*_k(n)$ (largest $T_{t,t}$ where sets are consistent across all permutations).
   • They prove that a lower bound on $b_k(n)$ implies a lower bound on the standard Ramsey function $f_k(n)$.

2. Inductive Partitioning:

   • For the lower bounds of $d^*_k(n)$ and $d_k(n)$, the authors use an inductive construction. They recursively partition the vertex set based on the relative ordering of vertices in the generating permutations.
   • Specifically, they assign "types" (binary vectors) to vertices based on their positions in the permutations, ensuring that subsets of vertices with specific types maintain dominance or consistency properties.

3. Probabilistic Constructions (Upper Bounds):

   • To establish upper bounds, the authors utilize random permutations. They show that for random $k$-majority tournaments, the probability of finding large consistent or majority-dominating sets is low, using union bounds and estimates on the number of consistent pairs.

4. Lexicographical Products:

   • To prove upper bounds for $b_k(n)$, they utilize the lexicographical product of tournaments ($G_1 \circ G_2$). They construct specific tournaments (based on Paley tournaments and random tournaments) that are $k$-majority but lack large transitive bipartite subgraphs.

5. Matrix Pattern Avoidance:

   • In the analysis of random 2-majority tournaments, they leverage results by Cibulka and Kynčl [4] regarding pattern avoidance in multidimensional permutation matrices to bound the expected size of the largest transitive set.

3. Key Contributions and Results

A. Exponential Improvement in Ramsey Bounds (Theorem 1.1)

The primary result significantly improves the lower bound for the size of the largest transitive subtournament in a $k$-majority tournament.

• Previous Bound: $t \ge n^{1/(3k-1)}$ (roughly).
• New Bound: The authors prove that every $k$-majority tournament contains a transitive tournament of size $n^{\Omega(1/k)}$.
• Limit Existence: They prove that the limit $\lim_{n \to \infty} \log_n f_k(n)$ exists.
• Bounds on the Exponent: If the limit is $1/c_k$, then:
  $$\frac{(1+o_k(1)) \ln k}{\ln \ln k} \le c_k \le \frac{2k-1}{2 \log^2 k}$$
  This reduces the gap in the exponent's dependence on $k$ from doubly exponential to a single exponential factor.

B. Bipartite Parameters (Theorem 1.2)

The paper establishes tight bounds for the bipartite variants, which serve as the engine for the main result:

• Consistency ($d^*_k$): $2^{2k-1}/e \le d^*_k \le 2^{2k-1}$.
• Majority Dominance ($d_k$): $2k/e \le d_k \le \binom{2k}{k}$.
• Transitive Bipartite ($b_k$): $\Theta(k) \le b_k \le \binom{2k}{k}$.
• Special Case ($k=2$): For $k=2$, the bounds are tight: $b_2 = d_2 = 6$ (implying $b_2(n) \sim n/6$).

C. Random $k$-Majority Tournaments (Section 4)

The authors investigate the size of the largest transitive set in tournaments generated by random permutations.

• Proposition 1.3: For random 2-majority tournaments, the expected size of the largest transitive set is $O(n^{2/3})$. This implies the exponent $r_2 \le 2/3$.
• Conjecture 1.4: The authors conjecture that for general $k$, the exponent $r_k = O(1/k)$. If true, this would match the lower bound derived in Theorem 1.1, suggesting the bounds are asymptotically tight for random instances.

4. Significance

1. Resolution of a Long-standing Gap: The paper resolves a significant discrepancy in the known bounds for $k$-majority tournaments. By improving the exponent from $O(1/k)$ (in the denominator) to a much tighter dependence, it demonstrates that these restricted tournaments are "Ramsey-rich" to a much higher degree than previously thought.
2. Methodological Advancement: The introduction of the bipartite variant ($T_{t,t}$) and the specific analysis of "consistency" and "majority dominance" provides a powerful new toolkit for analyzing Ramsey properties in structured tournaments. The recursive partitioning technique based on permutation types is likely applicable to other problems in extremal combinatorics.
3. Connection to Random Structures: By linking the deterministic lower bounds to the behavior of random $k$-majority tournaments, the paper bridges the gap between worst-case and average-case analysis in this domain. The conjecture that random instances achieve the deterministic lower bound suggests that the constructed worst-case examples might not be the true limit of the structure's complexity.
4. Implications for Voting Theory: Since $k$-majority tournaments model voting paradoxes (McGarvey's theorem), these results provide deeper insights into the structural stability of voting outcomes derived from multiple preference orders.

In summary, Shapira and Yuster provide a definitive improvement on the Ramsey properties of $k$-majority tournaments, proving that they contain transitive substructures of size $n^{\Omega(1/k)}$, a massive improvement over previous polynomial bounds, and establishing the existence of the limiting exponent.