The structure of almost all graphs in a hereditary property

DOI10.1016/J.JCTB.2010.10.001MaRDI QIDQ631643zbMATH OpenOpenAlexFDO

Authors Noga Alon, József Balogh, Béla Bollobás, Robert Morris

Publication date 14 March 2011

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.1942

zbMATH Keywords

entropyhereditary propertystructure of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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.

Recommendations

• The unlabelled speed of a hereditary graph property
• A jump to the Bell number for hereditary graph properties
• The speed of hereditary properties of graphs
• The structure of hereditary properties and colourings of random graphs
• Generalized chromatic numbers of random graphs
• Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
• Hereditary and monotone properties of combinatorial structure
• On the size of hereditary classes of graphs

Cites work

• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• A jump to the Bell number for hereditary graph properties
• Almost all Berge Graphs are Perfect
• Almost all \(H\)-free graphs have the Erdős-Hajnal property
• Almost all hypergraphs without Fano planes are bipartite
• Almost all triangle-free triple systems are tripartite
• Almost all triple systems with independent neighborhoods are semi-bipartite
• An extremal problem for random graphs and the number of graphs with large even-girth
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs. II: Extremal graphs
• Excluding induced subgraphs: critical graphs
• Excluding induced subgraphs: quadrilaterals
• Hereditary Properties of Triple Systems
• Hereditary properties of hypergraphs
• Hereditary properties of ordered graphs
• Hereditary properties of partitions, ordered graphs and ordered hypergraphs
• How many ways can one draw a graph?
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• On the density of families of sets
• On the entropy values of hereditary classes of graphs
• On the number of graphs without 4-cycles
• Projections of Bodies and Hereditary Properties of Hypergraphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The asymptotic number of triple systems not containing a fixed one
• The fine structure of octahedron-free graphs
• The number of \(K_{m,m}\)-free graphs
• The number of \(K_{s,t}\)-free graphs
• The number of graphs without forbidden subgraphs
• The speed of hereditary properties of graphs
• The typical structure of graphs without given excluded subgraphs
• The unlabelled speed of a hereditary graph property
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

Cited in

(48)

• Almost all string graphs are intersection graphs of plane convex sets
• Perfect graphs of fixed density: counting and homogeneous sets
• Locally bounded coverings and factorial properties of graphs
• The unlabelled speed of a hereditary graph property
• Regular partitions of gentle graphs
• Structure and enumeration theorems for hereditary properties in finite relational languages
• Jumps in speeds of hereditary properties in finite relational languages
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Classes of graphs without star forests and related graphs
• Asymptotic probabilities of extension properties and random l-colourable structures
• Hereditary classes of graphs: a parametric approach
• On the complexity of finite subgraphs of the curve graph
• The structure of hereditary properties and colourings of random graphs
• The structure of hereditary properties and 2-coloured multigraphs
• Hereditarily infinite-dimensional property for asymptotic dimension and graphs with large girth
• Structured Codes of Graphs
• The penultimate rate of growth for graph properties
• The structure of typical eye-free graphs and a Turán-type result for two weighted colours
• Shadows of ordered graphs
• The structure and the number of \(P_7\)-free bipartite graphs
• The structure and the number of \(P_7\)-free bipartite graphs
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• The fine structure of octahedron-free graphs
• A note on the speed of hereditary graph properties
• On the typical structure of graphs in a monotone property
• Sign rank versus Vapnik-Chervonenkis dimension
• Implicit representation of sparse hereditary families
• The typical structure of sparse \(K_{r+1}\)-free graphs
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• Graphs of large chromatic number
• \(\mathrm{VC}_{\ell }\)-dimension and the jump to the fastest speed of a hereditary \(\mathcal {L}\)-property
• A jump to the Bell number for hereditary graph properties
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• The f-factor problem for graphs and the hereditary property
• Counting \(r\)-graphs without forbidden configurations
• Random perfect graphs
• For most graphs H, most H-free graphs have a linear homogeneous set
• The decomposability of additive hereditary properties of graphs
• Almost all string graphs are intersection graphs of plane convex sets
• Deciding the Bell number for hereditary graph properties
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• Induced \(C_5\)-free graphs of fixed density: counting and homogeneous sets
• Boundary properties of factorial classes of graphs
• Almost all triple systems with independent neighborhoods are semi-bipartite
• Forbidding induced even cycles in a graph: typical structure and counting
• Maximal graphs with respect to hereditary properties
• The speed of hereditary properties of graphs
• The typical structure of graphs with no large cliques

This page was built for publication: The structure of almost all graphs in a hereditary property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q631643)