Graph limits and hereditary properties

DOI10.1016/J.EJC.2015.07.010zbMATH Open1327.05290OpenAlexW1811797198MaRDI QIDQ896080FDOQ896080

Authors Svante Janson 

Publication date 11 December 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

intersection graphshereditary classes of graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Abstract: We collect some general results on graph limits associated to hereditary classes of graphs. As examples, we consider some classes defined by forbidden subgraphs and some classes of intersection graphs, including triangle-free graphs, chordal graphs, cographs, interval graphs, unit interval graphs, threshold graphs, and line graphs.

Recommendations

• scientific article; zbMATH DE number 970795
• The speed of hereditary properties of graphs
• Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
• Hereditary and monotone properties of combinatorial structure
• Graph properties, graph limits, and entropy

Cites work

• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
• A measure-theoretic approach to the theory of dense hypergraphs
• Algorithmic graph theory and perfect graphs
• An analytic approach to stability
• Analytic combinatorics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Finitely forcible graphons
• Forbidden induced subgraphs for line graphs
• Graph Classes: A Survey
• Graph limits and exchangeable random graphs
• Graph properties, graph limits, and entropy
• Graphons, cut norm and distance, couplings and rearrangements
• Interval graph limits
• Large networks and graph limits
• Limits of dense graph sequences
• Line graphs and forbidden induced subgraphs
• Metrics for sparse graphs
• Moments of two-variable functions and the uniqueness of graph limits
• On string graph limits and the structure of a typical string graph
• On the typical structure of graphs in a monotone property
• Quasi-random graphs and graph limits
• Random Fragmentation and Coagulation Processes
• Random Partitions of Sets
• Regularity partitions and the topology of graphons
• The Structure of Random Partitions of Large Integers
• Threshold graph limits and random threshold graphs

Cited in

(12)

• The penultimate rate of growth for graph properties
• Correcting continuous hypergraphs
• Limits of structures and the example of tree semi-lattices
• Hereditarily infinite-dimensional property for asymptotic dimension and graphs with large girth
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• Threshold graph limits and random threshold graphs
• On the typical structure of graphs in a monotone property
• Graphon convergence of random cographs
• Interval graph limits
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• On string graph limits and the structure of a typical string graph

This page was built for publication: Graph limits and hereditary properties

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