Original Paper
The Number Of Orientations Having No Fixed Tournament
Noga Alon*1, 2
and Raphael Yuster3 
| (1) |
Department of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel |
| (2) |
Institute for Advanced Study, Princeton NJ 08540, USA |
| (3) |
Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel |
Received: 31 December 2002 Revised: 6 February 2004
Let
T be a fixed tournament on
k vertices. Let
D(
n,T ) denote the maximum number of orientations of an
n-vertex graph that have no copy of
T. We prove that

for all sufficiently (very) large
n, where
tk−1(
n) is the maximum possible number of edges of a graphon n vertices with no
Kk, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with
some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying
this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity
lemma and therefore show that in these cases

already holds for (relatively) small values of
n.
Mathematics Subject Classification (2000): 05C20 - 05C30
* Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann
Minkowski Minerva Center for Geometry at Tel Aviv University.