The structure of almost all graphs in a hereditary property
| dc.creator | Alon, Noga | |
| dc.creator | Balogh, Jozsef | |
| dc.creator | Bollobas, Bela | |
| dc.creator | Morris, Robert | |
| dc.date | 2009-05-12 | |
| dc.date.accessioned | 2026-07-07T13:14:10Z | |
| dc.date.available | 2026-07-07T13:14:10Z | |
| dc.description | A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of ¶is the function n \mapsto |¶_n|, where ¶_n denotes the graphs of order n in ¶. It was shown by Alekseev, and by Bollobas and Thomason, that if ¶is a hereditary property of graphs then |¶_n| = 2^{(1 - 1/r + o(1))n^2/2}, where r = r(¶) \in \N is the so-called `colouring number' of ¶. However, their results tell us very little about the structure of a typical graph G \in ¶. In this paper we describe the structure of almost every graph in a hereditary property of graphs, ¶. As a consequence, we derive essentially optimal bounds on the speed of ¶, improving the Alekseev-Bollobas-Thomason Theorem, and also generalizing results of Balogh, Bollobas and Simonovits. | |
| dc.description | 29 pages | |
| dc.identifier | https://arxiv.org/abs/0905.1942 | |
| dc.identifier | http://arxiv.org/abs/0905.1942 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/230126 | |
| dc.subject | Combinatorics | |
| dc.title | The structure of almost all graphs in a hereditary property | |
| dc.type | text |