TY - JOUR

T1 - The structure of almost all graphs in a hereditary property

AU - Alon, Noga

AU - Balogh, József

AU - Bollobás, Béla

AU - Morris, Robert

N1 - Funding Information:
✩ The first author was supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, by an ERC advanced grant, by NSF Grant CCF 0832797 and by the Ambrose Monell Foundation. The second author was supported by NSF CAREER Grants DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 09072 and 08086, and OTKA Grant K76099. The third author was supported by NSF Grants DMS-0505550, CNS-0721983 and CCF-0728928, and ARO Grant W911NF-06-1-0076. The fourth author was supported by a Research Fellowship from Murray Edwards College, Cambridge, ERC Advanced grant DMMCA, and a JSPS fellowship. E-mail addresses: nogaa@tau.ac.il (N. Alon), jobal@math.uiuc.edu (J. Balogh), B.Bollobas@dpmms.cam.ac.uk (B. Bollobás), rob@impa.br (R. Morris).

PY - 2011/3

Y1 - 2011/3

N2 - 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→|Pn|, where Pn denotes the graphs of order n in P. It was shown by Alekseev, and by Bollobás and Thomason, that if P is a hereditary property of graphs then. |Pn|=2(1-1/r+o(1))(n2), where r=r(P)j{cyrillic,ukrainian}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-Bollobás-Thomason Theorem, and also generalising results of Balogh, Bollobás and Simonovits.

AB - 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→|Pn|, where Pn denotes the graphs of order n in P. It was shown by Alekseev, and by Bollobás and Thomason, that if P is a hereditary property of graphs then. |Pn|=2(1-1/r+o(1))(n2), where r=r(P)j{cyrillic,ukrainian}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-Bollobás-Thomason Theorem, and also generalising results of Balogh, Bollobás and Simonovits.

KW - Entropy

KW - Hereditary property

KW - Structure of graphs

UR - http://www.scopus.com/inward/record.url?scp=78951485718&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78951485718&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2010.10.001

DO - 10.1016/j.jctb.2010.10.001

M3 - Article

AN - SCOPUS:78951485718

SN - 0095-8956

VL - 101

SP - 85

EP - 110

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -