Minimum number of transitive paths in tournament

106 Views Asked by At

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if there exists an edge from $A_i$ to $A_j$ for all $i<j$. The number of transitive paths in $T$ is the sum of the number of transitive paths of each size.

What is the minimum possible number of transitive paths in a tournament $T$ with $n$ vertices?

Any approximations, references, etc. would be appreciated.