%0 Generic %1 Alon2009 %A Alon, Noga %A Balogh, Jozsef %A Bollobas, Bela %A Morris, Robert %D 2009 %K imported %T The structure of almost all graphs in a hereditary property %U http://arxiv.org/abs/0905.1942 %X A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of \P is the function n \mapsto |\P_n|, where \P_n denotes the graphs of order n in \P. It was shown by Alekseev, and by Bollobas and Thomason, that if \P is a hereditary property of graphs then |\P_n| = 2^(1 - 1/r + o(1))n^2/2, where r = r(\P) \N is the so-called `colouring number' of \P. However, their results tell us very little about the structure of a typical graph G \P. In this paper we describe the structure of almost every graph in a hereditary property of graphs, \P. As a consequence, we derive essentially optimal bounds on the speed of \P, improving the Alekseev-Bollobas-Thomason Theorem, and also generalizing results of Balogh, Bollobas and Simonovits.

@misc{Alon2009, abstract = { A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of \P is the function n \mapsto |\P_n|, where \P_n denotes the graphs of order n in \P. It was shown by Alekseev, and by Bollobas and Thomason, that if \P is a hereditary property of graphs then |\P_n| = 2^{(1 - 1/r + o(1))n^2/2}, where r = r(\P) \in \N is the so-called `colouring number' of \P. However, their results tell us very little about the structure of a typical graph G \in \P. In this paper we describe the structure of almost every graph in a hereditary property of graphs, \P. As a consequence, we derive essentially optimal bounds on the speed of \P, improving the Alekseev-Bollobas-Thomason Theorem, and also generalizing results of Balogh, Bollobas and Simonovits. }, added-at = {2009-11-08T14:35:05.000+0100}, author = {Alon, Noga and Balogh, Jozsef and Bollobas, Bela and Morris, Robert}, biburl = {https://www.bibsonomy.org/bibtex/2600724c0e9a11580e6ff01465964331b/apford}, description = {The structure of almost all graphs in a hereditary property}, interhash = {a0877ef7d94abd102b1e5b3676e007e4}, intrahash = {600724c0e9a11580e6ff01465964331b}, keywords = {imported}, note = {cite arxiv:0905.1942 Comment: 29 pages}, timestamp = {2009-11-08T14:35:05.000+0100}, title = {The structure of almost all graphs in a hereditary property}, url = {http://arxiv.org/abs/0905.1942}, year = 2009 }