pith. machine review for the scientific record. sign in

arxiv: math/0702371 · v1 · submitted 2007-02-13 · 🧮 math.CO

Recognition: unknown

Hereditary properties of tournaments

Authors on Pith no claims yet
classification 🧮 math.CO
keywords hereditaryspeedpropertytournamentsexponentialpolynomialundercalled
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.