Graph Theory : Obtain the number of tournaments with 'N' nodes. Now define a transitive tournament as one where any three nodes (i,j,k) can be arranged in such a way that i-j-k and i-k. Define sub-tournament with node set S as the induced graph on S using the tournament. Now, any tournament with N nodes contains a transitive sub-tournament of size 2(this is just a directed edge). Define a maximal transitive sub-tournament for each tournament, T_k, as M_k, with maximal in the sense of NUMBER OF NODES in M_k. The aim is to upper bound min(|M_k|) where |G| is the number of nodes in the graph G

Question

Graph Theory : Obtain the number of tournaments with 'N' nodes. Now define a transitive tournament as one where any three nodes (i,j,k) can be arranged in such a way that i->j->k and i->k. Define sub-tournament with node set S as the induced graph on S using the tournament. Now, any tournament with N nodes contains a transitive sub-tournament of size 2(this is just a directed edge). Define a maximal transitive sub-tournament for each tournament, T_k, as M_k, with maximal in the sense of NUMBER OF NODES in M_k. The aim is to upper bound min(|M_k|) where |G| is the number of nodes in the graph G

Accepted Answer

The aim is to find an upper bound for the minimum number of nodes in a maximal transitive sub-tournament.

A transitive tournament is one where any three nodes can be arranged in a way that satisfies the transitive property.
A sub-tournament is an induced graph on a subset of nodes from the original tournament.
Every tournament with N nodes contains a transitive sub-tournament of size 2 (a directed edge).
The goal is to find the maximal transitive sub-tournament with the minimum number of nodes.
The aim is to upper bound the minimum number of nodes in the maximal transitive sub-tournament.