The structure of almost all graphs in a hereditary property

DOI10.1016/J.JCTB.2010.10.001zbMATH Open1217.05193arXiv0905.1942OpenAlexW2103229001MaRDI QIDQ631643FDOQ631643

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)

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.

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

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

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)

Cites Work

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

Cited In (48)

• 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
• The structure of hereditary properties and colourings of random graphs
• Hereditary classes of graphs: a parametric approach
• Asymptotic probabilities of extension properties and random \(l\)-colourable structures
• On the complexity of finite subgraphs of the curve graph
• Hereditarily infinite-dimensional property for asymptotic dimension and graphs with large girth
• The structure of hereditary properties and 2-coloured multigraphs
• 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
• Title not available (Why is that?)
• The \(f\)-factor problem for graphs and the hereditary property
• Random perfect graphs
• Counting \(r\)-graphs without forbidden configurations
• For most graphs \(H\), most \(H\)-free graphs have a linear homogeneous set
• The decomposability of additive hereditary properties of graphs
• Deciding the Bell number for hereditary graph properties
• Almost all string graphs are intersection graphs of plane convex sets
• Boundary properties of factorial classes of graphs
• Induced \(C_5\)-free graphs of fixed density: counting and homogeneous sets
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• 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
• Almost all string graphs are intersection graphs of plane convex sets
• The typical structure of graphs with no large cliques
• Perfect graphs of fixed density: counting and homogeneous sets

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)