Question

There are (2n+1) teams in a round-robin tournament, in which each team plays every other team exactly once, with no ties. We say that teams x, y, z form a cycle triplet if x beats y , y beats z and z beats x. Determine the maximum number of cyclic triplets possible.

Answer 1

Consider G as a directed graph where there is an edge from A to B if A beats B (symbolised as ≻ since it may be non-transitive). We are looking for 3-cycles in the graph.

Number the teams T1,T2,…,T2n+1 and define a simple rule for victory:

Ti≻Tj⟺i>j, for all i,j|1≤i,j≤2n+1(1)

This rule covers all possible games between teams.

Now it is clear that node T2n+1 has only outbound edges, as it beats all others. Then it cannot possibly be a member of a cycle triplet, so the number of cycle triplets will not be changed by removing T2n+1 and all its outbound edges to obtain graph G′.

In G′, node T2n has only outbound edges, so it cannot possibly be a member of a cycle triplet. Therefore, T2n and all its outbound edges can be removed from G′ to form G′′, and so on. So, by induction (base case an edge or single node), G contains no cycle triplets.

(Or you could consider the adjacency matrix A where Aij={1,i>j0,otherwise and show that it is lower triangular with zeroes on the diagonal, and so Am=0,∀m≥2, i.e. there are no m-cycles.)

b. I am not sure what the maximum is.

Let C(n) be the maximum number of cyclic triangles in tournament of 2n+1 teams.

For n=1 (3 teams): C(1)=1

For n=2 (5 teams): C(2)≥4 through experimentation

hope this answer helpful u