Hereditary properties of tournaments
| dc.creator | Balogh, József | |
| dc.creator | Bollobás, Béla | |
| dc.creator | Morris, Robert | |
| dc.date | 2007-02-13 | |
| dc.date.accessioned | 2026-07-07T07:46:41Z | |
| dc.date.available | 2026-07-07T07:46:41Z | |
| dc.description | 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. | |
| dc.description | 28 pgs, 2 figures, submitted November 2006 | |
| dc.identifier | https://arxiv.org/abs/math/0702371 | |
| dc.identifier | http://arxiv.org/abs/math/0702371 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123907 | |
| dc.subject | Combinatorics | |
| dc.title | Hereditary properties of tournaments | |
| dc.type | text |