The structure of almost all graphs in a hereditary property

DOI10.1016/j.jctb.2010.10.001zbMath1217.05193arXiv0905.1942OpenAlexW2103229001MaRDI QIDQ631643

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

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) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Structured Codes of Graphs, On the complexity of finite subgraphs of the curve graph, Perfect Graphs of Fixed Density: Counting and Homogeneous Sets, For most graphs H , most H -free graphs have a linear homogeneous set, Counting \(r\)-graphs without forbidden configurations, Jumps in speeds of hereditary properties in finite relational languages, Classes of graphs without star forests and related graphs, Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers], Almost all string graphs are intersection graphs of plane convex sets, Locally bounded coverings and factorial properties of graphs, The fine structure of octahedron-free graphs, Graphs of large chromatic number, Shadows of ordered graphs, Almost all triple systems with independent neighborhoods are semi-bipartite, Structure and enumeration theorems for hereditary properties in finite relational languages, Sign rank versus Vapnik-Chervonenkis dimension, The Structure of Typical Eye-Free Graphs and a Turán-Type Result for Two Weighted Colours, Regular partitions of gentle graphs, Random perfect graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, 𝑉𝐶_{ℓ}-dimension and the jump to the fastest speed of a hereditary ℒ-property, Forbidding induced even cycles in a graph: typical structure and counting, The typical structure of graphs with no large cliques, Unnamed Item, The structure and the number of \(P_7\)-free bipartite graphs, The typical structure of sparse $K_{r+1}$-free graphs, The structure and the number of \(P_7\)-free bipartite graphs, Deciding the Bell Number for Hereditary Graph Properties, On the typical structure of graphs in a monotone property, Boundary Properties of Factorial Classes of Graphs, Asymptotic probabilities of extension properties and random \(l\)-colourable structures, Hereditary classes of graphs: a parametric approach, Almost all string graphs are intersection graphs of plane convex sets

Cites Work

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