The number of orientations having no fixed tournament

Noga Alon, Raphael Yuster

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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(n,T) = 2tk-1(n) for all sufficiently (very) large n, where t k-1(n) is the maximum possible number of edges of a graphon n vertices with no K k , (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(n,T) = 2[n2/4] already holds for (relatively) small values of n.

Original languageEnglish (US)
Pages (from-to)1-16
Number of pages16
JournalCombinatorica
Volume26
Issue number1
DOIs
StatePublished - Feb 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'The number of orientations having no fixed tournament'. Together they form a unique fingerprint.

Cite this