Originator(s): Kierstead-Trotter, P. Charbit, K. Milans, P. Wenger (presented by Kevin Milans - REGS 2009)
Definitions: For vertices u and v in a directed graph, we use uv to denote an edge from u to v. A digraph D is a k-majority digraph if there is a family of k linear orders of V(D) such that uv ∈ E(D) if and only if u precedes v in a strict majority of the linear orders. The majority dimension of a digraph D, denoted dim(D), is the minimum k such that D is a k-majority digraph.
The smallest outdegree among the vertices of D is denoted by δ+(D). A set S of vertices is a dominating set if for each vertex outside S, there is a vertex u ∈ S such that uv ∈ E(D). The domination number of D is the minimum size of a dominating set.
The acyclic chromatic number of a digraph D, written χa(D), is the minimum size of a partition of the vertices into subsets inducing acyclic subdigraphs. (For ordinary graphs, the name for the parameter defined in this way is "vertex arboricity", and "acyclic chromatic number" has a different meaning.)
Background: k-majority digraphs model voting scenarios, where the vertices correspond to options ranked by k voters. When k is odd, the resulting digraph is a tournament (an orientation of a complete graph). McGarvey [M] showed that for every n there is a sufficiently large k such that every n-vertex tournament is a k-majority tournament. Stearns [St] showed that k must be at least Ω(n / log n) for some n-vertex tournaments, and Erdős and Moser [EM] showed that O(n / log n) always suffices.
Domination number for (2k-1)-majority tournaments is related to the problem of "non-transitive dice" [Sa]. The domination number of a tournament exceeds t if every set of t vertices is dominated by some vertex outside it. Given a (2k-1)-majority tournament on n vertices with domination number greater than t, one can design dice with 2k-1 faces by putting the number ni+j on the die associated with a vertex when j is its rank in the ith ordering. For every set T of t dice, there is then some die that has higher expected value than each die in T
Erdős showed that tournaments may have arbitrarily large domination number, but Kierstead and Trotter conjectured that this fails for (2k-1)-majority tournaments. Alon, Brightweek, Kierstead, Kostochka, and Winkler [ABKKW] proved their conjecture and established bounds on the largest domination number.
Question 1: [ABKKW] Let f(k) be the largest domination number among (2k-1)-majority digraphs. What is the asymptotic behavior of f(k)?
Comments: [ABKKW] proved the existence of constants c and c' such that ck/ log k ≤ f(k) ≤ c'k log k. They also proved that f(2)=3 and f(3)≥4.
Question 2: (Pierre Charbit) Is it true that every n-vertex 4-majority digraph has a vertex with outdegree less than n/3?
Comments: Charbit noted that a 4-majority tournament contains no triangle, since uv,vw ∈ E(D) requires u before w in at least two of the orders. Consequently, a "yes" answer here is simply the restriction of the Cacetta-Häggkvist Conjecture to the family of 4-majority digraphs. That conjecture states that every n-vertex digraph without triangles has a vertex with outdegree less than n/3.
Trivially, every n-vertex digraph has minimum outdegree at most (n-1)/2, and this is easy to achieve in 3-majority tournaments. Let D0 be an isolated vertex; for r > 0, obtain Dr by expanding each vertex in a triangle into a copy of Dr-1. The result is a tournament on 3r vertices with δ+(Dr) = (n-1)/2. Moreover, Dr is a 3-majority tournament. A similar recursive construction replacing each vertex in a 4-cycle with the previous iteration yields a 4-majority digraph with δ+(D) = (n-1)/3.
Question 3: (K. Milans) Let gk(n) denote the maximum over all n-vertex k-majority digraphs D of χa(D). What is the asymptotic behavior of gk(n)?
Comments: In the construction of Dr given above, an acyclic subgraph contains vertices from at most two of the copies of Dr-1. This allows one to show that g3(n) ≥ n0.369 when n is a power of 3. Nevertheless, we now know that g3(n) = Θ(n1/2). When k is even, the modified construction for k=4 in Question 2 gives gk(n) ≥ n1-ln(3)/ln(4) ≈ n0.207.
Question 4: (P. Wenger, in REGS 2009) Let h(n) denote the maximum over all n-vertex digraphs D of dim(D). What is the asymptotic behavior of h(n)? What is the asymptotic behavior of majority dimension when the maximum is restricted to particular families of digraphs, such as acyclic digraphs or orientations of trees?
Comments: The concept of majority dimension can be viewed as a digraph analogue of the order dimension of a poset. If t is the edge-chromatic-number of the underlying graph of D, then dim(D) ≤ 2t. To see this, for each color class M in an optimal edge-coloring of the underlying graph, form two linear orders such that u precedes v in both orderings if and only if uv &isin M. Now every edge of D is consistent with exactly t+1 of the 2t orderings, and ordered pairs that are not edges are consistent with t of them.
On the other hand, the number of lists of k linear orders of n vertices is only n!k, while there are 2n(n-1)/2 tournaments on n. Obtaining all tournaments with majority dimension at most h(n) requires n!h(n) ≥ 2n(n-1)/2. Consequently, there is a constant C such that C n/log(n) ≤ h(n) ≤ 2n.
References:
[ABKKW]
Alon, N., Brightwell, G., Kierstead, H. A., Kostochka, A. V., and Winkler, P.;
Dominating sets in k-majority tournaments. J. Comb. Theory Ser. B 96, (2006),
374-387.
[E] Erdős, P. On a problem in graph theory. Math. Gaz. 47 1963 220--223.
[EM] Erdős, P.; Moser, L. On the representation of directed graphs as
unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9
(1964) 125--132.
[M] McGarvey, David C.
A theorem on the construction of voting paradoxes.
Econometrica 21, (1953). 608--610.
[Sa] Savage, Richard P., Jr.
The paradox of nontransitive dice.
Amer. Math. Monthly 101 (1994), no. 5, 429--436.
[St] Stearns, Richard.
The voting problem.
Amer. Math. Monthly 66 1959 761--763.