Hereditary properties of tournaments

Details Hereditary properties of tournaments Hereditary properties of tournaments

2007-02-13

arxiv.org/abs/math/0702371v1

Mathematics

Combinatorics

28 pgs, 2 figures, submitted November 2006

Scientific paper

A collection of unlabelled tournaments P is called a hereditary property if it is closed under isomorphism and under taking induced sub-tournaments. The speed of P is the function n -> |P_n|, where P_n = {T \in P : |V(T)| = n}. In this paper, we prove that there is a jump in the possible speeds of a hereditary property of tournaments, from polynomial to exponential speed. Moreover, we determine the minimal exponential speed, |P_n| = c^(n + o(n)), where c = 1.47... is the largest real root of the polynomial x^3 = x^2 + 1, and the unique hereditary property with this speed.

Affiliated with

Also associated with

No associations

Rating

Hereditary properties of tournaments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hereditary properties of tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hereditary properties of tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409789