|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The structure of almost all graphs in a hereditary property | | Noga Alon
; Jozsef Balogh
; Bela Bollobas
; Robert Morris
; | | Date: |
12 May 2009 | | 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. | | Source: | arXiv, 0905.1942 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER