Graph limits and hereditary properties

DOI10.1016/J.EJC.2015.07.010zbMATH Open1327.05290arXiv1102.3571OpenAlexW1811797198MaRDI 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

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

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)