## Abstract

A hereditary graph property is a collection of labeled graphs, closed under isomorphism and also under the taking of induced subgraphs. Its speed is the number of graphs in the property as a function of the number of vertices in the graph. Earlier research has characterized the speeds for hereditary graph properties up to n^{(1+o(1))n}, and described the properties that have those smaller speeds. The present work provides the minimal speed possible above that range, and gives a structural characterization for properties which exhibit such speeds. More precisely, this paper sheds lights on the jump from n^{(1+o(1))n} to the range that includes n^{(1+o(1))n}. A measure jumps when there are two functions with positive distance such that the measure can take no values between those functions. A clean jump occurs when the bounding functions are well-defined and occur as possible values of the measure. It has been known for some time that the density of a graph jumps; recent work on hereditary graph properties has shown that speeds jump for properties with "large" or "small" speeds. The current work shows that there is a clean jump for properties with speed in a middle range. In particular, we show that when the speed of a hereditary graph property has speed greater than n^{cn} for all c < 1, the speed is at least B_{n}, the nth Bell number. Equality occurs only for the property containing all disjoint unions of cliques or its complement.

Original language | English (US) |
---|---|

Pages (from-to) | 29-48 |

Number of pages | 20 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 95 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2005 |

Externally published | Yes |

## Keywords

- Dilworth's Theorem
- Graph properties
- Hereditary
- Monotone
- Posets
- Ramsey Theory
- Size
- Speed

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics