An (n,k)-tournament is a contest with n players held in k rounds such that: (i) Each player plays in each round, and every two players meet at most once. (ii) If a player A meets player B in round i, player C meets player D in round i, and player A meets player C in round j, then player B meets player D in round j. Determine all pairs (n,k) for which there exists an (n,k)-tournament. ------------------------------------- Condition (i) says that a tournament is a sequence of perfect matchings with no edge repetition. => n must be even, If n = 2, k can be at most 1: (R1) A <-> B, (let A,B,... denote players, R1, R2, ... rounds) otherwise we must repeat the edge -- there is just one perfect matching on two vertices. Actually, if there is an (n,k)-tournament, any sublist forms an (n,k')-tournament, where k' can be any number <= k. So the objective is to find the maximum possible number of rounds given a number of players. If n = 4, WLOG: (R1) A <-> B, C <-> D (R2) A <-> C, B <-> D does it satisfy (ii)? I need to visualize the condition. (Ri) A <-i-> B ^ ^ j j <- implied v V C <-i-> D it means that the union of any two rounds must be composed of 4-cycles. Union of any two rounds is obviously formed by cycles of even length, but we are required to make them cycles of length 4. So the pair (R1), (R2) satisfies the condition, any pair of different parfect matchings does. So for n = 4, the maximum number of rounds is three: (R1) A <-> B, C <-> D (R2) A <-> C, B <-> D (R3) A <-> D, B <-> C and there cannot be more because the graph is already full. In general, the obvious upper bound is k <= n-1 because a player can have only n-1 different opponents. Is the upper bound always achievable? What about n = 6? WLOG (R1) A-B, C-D, E-F (I have simplified the notation) (R2) ... there is no way of decomposing 6 players into 4-cycles So in general, if n = 2 (mod 4), the maximum k is 1. But for n = 0 (mod 4), it is still possible that k can be up to n-1. Let's try n = 8 WLOG (R1) A-B, C-D, E-F, G-H WLOG (R2) A-C, B-D, E-G, F-H (R3) two ideas a) keep the same 4-cycles, just duplicating the n=4 case A-D, B-C, E-H, F-G b) using different 4-cycles, so WLOG A-E, then B-F (by R1) C-G (by R2) D-H (by R2) in summary: A-E, B-F, C-G, D-H is it actually compatible with (R1) and (R2)? Yes, it is a pretty regular pattern: Something like +4 mod 8. R1 is almost like +1, and R2 almost like +2 This way: if we think of the players indexed by binary A = 000, B = 001, C = 010, D = 011, E = 100, F = 101, G = 110, H = 111, then * (R1) switches the last bit * (R2) switches the middle bit * (R3) switches the first bit Is it also compatible with the option (a)? Check: A -a- D -b- H -a- E -b- A Yes, this is a 4-cycle, so the other will be also 4-cycle. Could I represent (a) by switching some bits in binary? * it would make it easier to show the compatibility. * like switching both the middle and last bit Yes, it works, confirmed. For a general round, I can take any non-empty set of binary indices. Switching the set defines a matching, and any two matchings are compatible because binary xor is commutative and associative. This gives 7 rounds -- the maximum possible number. This strategy works in general for any power of 2. Random idea for possible further investigation: * For two graphs on players, write + for XOR of their edges. * We know that R1+R2 are 4-cycles, and R1+R3 are 4-cycles * Also (R1+R2) + (R1+R3) = R2+R3 should be 4-cycles. This view could be useful later. Now, let's see what happens if it is divisible by 4, but not a power of 2: n = 12 First two rounds are WLOG. (R1) A-B, C-D, E-F, G-H, I-J, K-L (R2) A-C, B-D, E-G, F-H, I-K, J-L The third one can be again (a) just using 3-times the case n=4, or (b) by using other 4-cycles, WLOG A-E this forces A-E, B-F, C-G, D-H as in the case n = 8, and the 4 players I, J, K, L, must form the same component again. There is a last option for it: I-L, J-K. Contrary to the case n=8, this is not compatible with (a), so if we have chosen (a), there would be no further available round. Is there any further available round after (b = R3)? I must go outside I,J,K,L. The rest can be invariantly swapped using any of the mentioned binary subset switch, so WLOG (R4): I-A This forces: (R4) A-I, B-J, C-K, D-L by R1,R2. By R3: A-E, I-L, we have (R4) E-L contradicting D-L So, if the case analysis is not mistaken, there can be only 3 rounds. Conjecture: Given n = 2^a * (2b+1), the maximum possible k is k = 2^a-1. We know the lower bound, there is always the construction given by the binary switching. I want to prove the upper bound. (not sure how, yet) What were the reasons for the upper bound for concrete cases? n = 3: no perfect matching n = 6: no grouping into 4-tuples n = 12: case analysis (not helpful) I would like to construct some grouping into 8-tuples for n = 12, like in the previous cases. Or what if we can argue that the binary switches are in a sense the only possible way of constructing the tournament? Could we somehow represent by binary switching the rounds: (R1) A-B, C-D, E-F, G-H, I-J, K-L (R2) A-C, B-D, E-G, F-H, I-K, J-L (R3) A-E, B-F, C-G, D-H, I-L, J-K. Again, A=000, ..., H=111, and the three operations represent switching the last, the middle or the first bit on A,...,H. But on I,J,K, applying all three switches leads to identity, contrary to A,...,H. Anyway, this calls for some group-theory approach. R1, R2, R3 can be seen as involutions on the set of players. The group generated by them is commutative, so every element of the group can be seen as a the sum of a subset of (R1, R2, R3). It seems that every orbit must have the size of a power of two. Can we prove it in general? (maybe there is a theorem for it but my GT knowledge is not good enough) Let's take a player, let's say A. We consider the orbits of A under (R1, R2, R3) (orbit o1), and under (R1, R2) (orbit o2). I would like to claim that either |o2| = |o1|, or |o2| = 2|o1|. In other words, R3 either maps o1 to itself, or it maps every element of o1 outside o1. Let's assume that a player X in o1 is mapped to Y in o1. I want to prove that then every element of o1 must be mapped into o1. It is actually true. Let's consider an element Z in o1. There is a subset of (R1, R2) mapping Z to X, let's call the corresponding group action Rz. Then Z -Rx-> X -R3-> Y, so also Z -R3-> ? -Rx-> Y Since Y is in o1, then the preimage of Y in Rx is also in o1, so R3 maps every element of o1 to o1. This proof can be straightforwardly generalized to any list of (compatible) rounds in any tournament. Note that it proves that every orbit is doubled or remains the same after adding a new (compatible) round. Since the initial orbits (without any rounds) has all sizes 1, we can conclude that every orbit with any list of rounds in any tournament has the size of a power of two. This should solve the problem: For every orbit 'o', the number of rounds is at most |o|-1 because a given player from 'o' must be paired with a different player in 'o' in every round. Assume there are 2^a * (2b+1) players. Whenever we decompose the players to orbits of sizes of powers of two, there must be an orbit of size at most 2^a (it is obvious, the proof can be done by contradiction, assuming size of every orbit is divisible by 2^(a+1) ) Problem solved!