Some extremal properties concerning transitivity in graphs (Q2561235): Difference between revisions

A directed graph \(D\) is transitive iff arc \(ac\) is in \(D\) whenever arcs \(ab\) and \(bc\) are in \(D\). We show that for all tournaments \(T_n\) on \(n\) points, with \(0 \left(2^{\binom{n}{2}} \right)\) exceptions, the largest transitive subgraph of \(T_n\) contains fewer than \({1 \over 4}\binom{n}{2}+cn^{3/2}\) arcs for a suitable constant \(c\). Results concerning the size of bipartite subgraphs of tournaments and transitive graphs are also obtained.