A generalization of Turán's theorem to directed graphs

AbstractWe consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on m vertices. For an integer n⩾2, let Tn denote the transitive tournament with vertex set Xn={1,2,3,…,n} and edge set {(i,j):1⩽i<j⩽n}. A subgraph H of Tn is said to be m-locally unipathic when the restriction of H to each m element subset of Xn consisting of m consecutive integers is unipathic. We show that the maximum number of edges in a m-locally unipathic subgraph of Tn is (q2)(m−1)2+q(m−1)r+◀14r2▶ where n= q(m−1+r and ⌈12(m−1)⌉⩽r<⌈32(m−1)⌉. As is the case with Turán's theorem, the extremal graphs for our problem are complete multipartite graphs. Unlike Turán's theorem, the part sizes will not be uniform. The proof of our principal theorem rests on a combinatorial theory originally developed to investigate the rank of partially ordered sets