For an $n$-tournament, what's a tight upper bound for the minimum number of transitive sub tournaments needed to edge cover it?

175 Views Asked by At

Given an $n$-tournament, is there a known tight upper bound for the minimum number of transitive sub tournaments needed to edge cover the original tournament?

Context: Studying causal graphs in relativistic quantum information

1

There are 1 best solutions below

2
On

There is a paper “Decomposing oriented graphs into transitive tournaments” by Raphael Yuster (Discrete Mathematics 306:1 (2006) 166 – 170) where is considered a function $f(G)$ denoting the minimum number of transitive subtournaments that decompose an oriented graph $G$ with $n$ vertices (a decomposition is a cover which covers each edge exactly once). It is proved that $f(G)<\tfrac{5}{21}n^2(1 + o(1))$ (or, more precisely, $f(G)\le\tfrac{6946273}{29174348}n^2(1 + o(1)$, see the last page) for each tournament $G$ and there are tournaments $G$ for which $f(G)>n^2/3000$.