The structure of almost all graphs in a hereditary property

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

29 pages

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The structure of almost all graphs in a hereditary property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The structure of almost all graphs in a hereditary property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The structure of almost all graphs in a hereditary property will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-337831

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.