by Warren D. Smith with extra contributions/improvements by Geoff Exoo
Puzzle #27 – A quantity like the "Ramsey numbers" but defined for directed rather than undirected graphs. Let R(n) denote the smallest number Q such that every tournament with ≥Q players (i.e, complete directed graph on ≥Q nodes) contains an acyclic n-player subtournament. Re-expressed in voting-theory language: R(n) is the smallest number Q of candidates in a ranked-ballot election, such that it is guaranteed that at least one subset containing at least n of those candidates can be unambiguously ranked in relation to one another! Find values of R(n), upper and lower bounds, and asymptotic behavior. In particular, prove that R(n) grows exponentially with n.
Answer: This is a difficult problem. The table gives the best upper and lower bounds I know:
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
R(n) | 0 | 1 | 2 | 4 | 8 | 14 | 28 | 32-54 | 48-108 | 84-216 |
n | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
R(n) | 108-432 | 112-864 | 200-1728 | 272-3456 | 368-6912 | 444-13824 | 620-27648 | 660-55296 | 972-110592 | 1260-221184 |
Obviously: R(n)≥n.
Increasingness:
R(n)≥R(n-1)
because the n-player acyclic tournament contains an (n-1)-player one.
Slightly less obviously:
R(n)≥R(n-1)+2 for n≥3
because add two new vertices A,B
to a tournament without acyclic (n-1)-node subtournaments,
(A is "above" everybody, B is "below," except that B beats A)
to get one without acyclic n-noders.
An upper bound:
R(n)≤2R(n-1)
because: among the R=R(n) players, find a player with the most-extreme
maximum or minimum score (whichever is furthest
from the mean). Then an n-player acyclic subtournament consists of that player
(whom we suppose wlog has maximum score) plus the largest
acyclic subsubtournament among all the players he beat –
and there must be at least ceiling((R-1)/2) of them.
This also may be proven (albeit less constructively) in a divide-and-conquer manner. An immediate consequence of R(7)≤54 is an exponential upper bound
A lower bound: Consider a random V-player tournament (each game result determined by a coin flip). The expected number of n-player acyclic subtournaments, is E=2^{(1-n)n/2}(V-n+1)(V-n+2)...(V-1)V. If V is too small, then E<1, in which case there must exist some tournament below or equal to the expectation, i.e. having zero n-player acyclic subtournaments. Hence R(n) must be greater than any such V. In other words, we have demonstrated the lower bound
Improvement I: By using "improved randomness" we can improve the first lower bound above by a multiplicative factor asymptotic to √2.
Improvement II: What works a further factor of √2 better is to use the Lovasz Local Lemma, (LLL), one convenient form of which (R.L.Graham, B.L.Rothschild, J.Spencer: Ramsey Theory, Wiley 1980, p.77 & 80) is this: Suppose you have some events A_{1}, A_{2},..., A_{q} with dependency graph Γ whose maximum valency is Δ. If e·Prob(A_{j})<1/(Δ+1) for all j, 1≤j≤q, where e=2.71828..., then
Theorem: For any constant C>1 we have
Proof: Again use the random tournament on R nodes. Index the n-node subsets from 1 to q=(R choose n). Let A_{j} be the event that that subset is an acyclic subtournament. A_{i} is independent of A_{j} unless the two subsets share ≥2 nodes. So the maximum valency of the dependency graph is
Gap: Unfortunately there is, when n→∞, a huge gap between our lower and upper bounds on R(n). (Both grow exponentially, but with different growth factors. The upper bound is asymptotically roughly the square of the lower bound.) The lower bound, is however, effectively true in the sense that tournaments with a factor C more vertices than our lower bounds on R(n), usually contain acyclic n-node subtournaments, with exceptional tournaments (if any) being exponentially (in C) rare.
Better lower bounds for small n: can be obtained by construction and examination of specific tournaments. The "examination" part has been done exhaustively by computer for all the n≥7 in the table below. Particularly important are the "QRgraph(P)" tournaments also found in the answer to puzzle 21: these have P players and player i beats player j if i-j is a nonzero square in the finite field with P elements (and P is a prime power of the form 4k-1). The computer has a particularly easy time examining these, because, since they have an "arc-transitive automorphism group," the computer may assume wlog that the arc 0→1 is exactly the top two players in the acyclic subtournament. One also tends to suspect that such highly-symmetric tournaments will result in large lower bounds on R(n) because, due to their symmetry, "every arc is the same," and hence the construction, intuitively speaking, "has no exploitable weak spots." For the same reason, the undirected QRgraph(P) for prime-power P of form 4k+1 often yield good lower bounds on undirected graph Ramsey numbers.
Another interesting highly symmetric kind of tournament is FRgraph(P,M). These have P players and player i beats player j if i-j is either a nonzero fourth power, or one times M, in the finite field with P elements, where P is a prime power such that a genuine noncontradictory tournament is generated. (This construction works for P of the form 8k+5.)
My computer performed exhaustive examinations of QRgraph(P) for all prime P of form 4k-1 with P≤600 plus some additional P up to 700; of FRgraph(P,M) for all prime P of form 8k+5 and all M with P≤200; and of 99 random circulant tournaments mod P for each odd P≤121.
n | R(n)≥ | The tournament that shows it |
---|---|---|
3 | 4 | The 3-cycle – also known as QRgraph(3). |
4 | 8 | QRgraph(7), i.e. the circulant digraph mod 7 with increments {1,2,4}. This is the unique 7-node tournament demonstrating R(4)≥8. (Also, deleting one node gives the unique 6-node tournament free of acyclic 4-node subtournaments [Sanchez-Flores 1998 P2.1].) |
5 | 14 | FRgraph(13,2), i.e. the circulant digraph mod 13 with increments {1,3,9,2,6,5}. One inextensible 4-node acyclic subtournament is (0,1,2,3), but there also are others, e.g. (0,1,3,6), and you need to examine every one to verify inextensibility in all cases. This is the unique 13-node tournament demonstrating R(5)≥14. (Also, deleting one node gives the unique 12-node tournament free of acyclic 5-node subtournaments [Sanchez-Flores 1998 Thm 3.4].) |
6 | 28 | QRgraph(27), which has this adjacency matrix. This is the unique 27-node tournament free of acyclic 6-node subtournaments [Sanchez-Flores 1994]. (Also, deleting one node gives the unique 26-node tournament free of acyclic 6-node subtournaments [Sanchez-Flores 1998 Thm 4.3]. One might speculate based on 27=3^{3} this that the non-circulant QRgraphs QRgraph(243=3^{5}) and QRgraph(343=7^{3}) also might be spectacularly good, but in fact neither leads to a record bound.) |
7 | 29 | FRgraph(29,2), i.e. the circulant digraph mod 29 with increments {1,2,3,7,11,14,16,17,19,20,21,23,24,25}. One inextensible 6-node acyclic subtournament is (0,1,2,25,21,3). |
7 | 30 | By adding two nodes to QRgraph(27). |
7 | 32 | Cyclic graph mod 31 with increments {2,3,6,10,11,13,15,17,19,22,23,24,26,27,30}. One inextensible 6-node acyclic subtournament is (0,2,13,24,15,26). This is interesting because it outperforms QRgraph(31), which contains acyclic 7-vertex subtournaments. [Sanchez-Flores 1998 claims our example here is unique up to isomorphism among circulant tournaments.] |
8 | 48 | QRgraph(47)=FRgraph(47,2), i.e. increments {1,2,3,4,6,7,8,9,12,14,16,17,18,21,24,25,27,28,32,34,36,37,42} mod 47. One inextensible 7-node acyclic subtournament is (0,1,3,9,37,17,4). [Sanchez-Flores 1998 claims our example here is unique up to isomorphism among circulant tournaments; and based on an exhaustive search of all circulant tournaments with ≤55 nodes, this appears to be the unique largest circulant tournament free of 8-node acyclic subtournaments.] |
9 | 84 | QRgraph(83)=FRgraph(83,3), i.e. increments {0,1,3,4,7,9,10,11,12,16,17,21,23,25,26,27,28,29,30,31,33,36,37,38,40,41, 44,48,49,51,59,61,63,64,65,68,69,70,75,77,78,81} mod 83. One inextensible 8-node acyclic subtournament is (0,1,4,29,65,30,11,41). |
10 | 108 | QRgraph(107). One inextensible 9-node acyclic subtournament is (0,1,4,34,14,37,53,48,90). |
11 | 110 | By adding two nodes to QRgraph(107). |
11 | 112 | Shown by this tournament found by Geoff Exoo using Cayley directed graph from nonAbelian group of order 3*37=111. |
12 | 200 | QRgraph(199). One inextensible 11-node acyclic subtournament is (0,1,2,51,91,64,52,53,116,104,117). |
13 | 272 | QRgraph(271). One inextensible 12-node acyclic subtournament is (0,1,2,63,11,79,140,36,177,64,80,81). |
14 | 368 | QRgraph(367). One inextensible 13-node acyclic subtournament is (0,1,2,15,33,214,324,51,74,106,9,64,16). |
15 | 444 | QRgraph(443). One inextensible 14-node acyclic subtournament is (0,1,4,107,169,371,221,237,272,423,42,351,145,360). |
16 | 588 | QRgraph(587) [suboptimal]. One inextensible 15-node acyclic subtournament is (0,1,10,26,195,189,211,262,511,574,220,290,205,457,279). |
16 | 620 | QRgraph(619). One inextensible 15-node acyclic subtournament is (0,1,5,36,187,564,25,125,226,232,166,431,356,211,436). |
17 | 660 | QRgraph(659). Computed by Geoff Exoo; also Sanchez-Flores 1998 table 2. |
18 | 972 | QRgraph(971). Computed by Geoff Exoo; also Sanchez-Flores 1998 table 2. |
19 | 1260 | QRgraph(1259). Computed by Geoff Exoo. |
Previous work: All our tournaments here with ≤28 nodes were constructed by (and what is more impressive, proven optimal, i.e. the lower bound on R they yield is also an upper bound) by E.T.Parker & K.B.Reid: Disproof of a conjecture of Erdös and Moser on Tournaments, J.Combinatorial Theory 9 (1970) 225-238, and then that work was redone in a simpler fashion by V.Neumann-Lara: A short proof of a theorem of Reid and Parker on Tournaments, Graphs & Combinatorics 10 (1994) 363-366 and A. Sanchez-Florez: On tournaments and their largest transitive subtournaments, Graphs & Combinatorics 10 (1994) 367-376. Later Sanchez-Flores wrote "On tournaments and their largest transitive subtournaments", Graphs & Combinatorics 14 (1998) 181-200, which seems to include the latest and greatest results and gives independent confirmation of many of our & Exoo's computations here. Parker and Reid also showed the upper bound R(7)≤55, which [Sanchez-Flores 1998 Thm 4.7] improved to R(7)≤54, from which all our other upper bounds on R(n) for n≥7 follow.
Our lower bound on R(n) in the theorem appears to be new and asymptotically stronger than previous results. However the underlying LLL technique inside its proof was previously known (comes from some combination of P.Erdös, L.Lovasz, and J.Spencer).