Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Original Paper

The Number Of Orientations Having No Fixed Tournament

Noga Alon*1, 2 Contact Information and Raphael YusterContact Information

(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 $$
D{\left( {n,T} \right)} = 2^{{t_{{k - 1^{{{\left( n \right)}}} }} }} 
$$ 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 $$
D{\left( {n,T} \right)} = 2^{{{\left\lfloor {n^{2} /4} \right\rfloor }}} 
$$ 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.

Contact Information Noga Alon* (Corresponding author)
Email: nogaa@post.tau.ac.il

Contact Information Raphael Yuster
Email: raphy@research.haifa.ac.il
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb15
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)