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)

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.

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

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

zbMATH Keywords

intersection graphshereditary classes of graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

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

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)