Interval graph limits

DOI10.1007/S00026-012-0175-0MaRDI QIDQ1950423zbMATH OpenOpenAlexWikidataFDO

Authors Persi Diaconis, Susan Holmes, Svante Janson

Publication date 13 May 2013

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

Full work available at URL https://arxiv.org/abs/1102.2841, http://europepmc.org/articles/pmc4578824

zbMATH Keywords

graph limitsintersection graphsinterval graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Searching and sorting (68P10)

Abstract: We work out the graph limit theory for dense interval graphs. The theory developed departs from the usual description of a graph limit as a symmetric function $W(x,y)$ on the unit square, with $x$ and $y$ uniform on the interval $(0,1)$. Instead, we fix a $W$ and change the underlying distribution of the coordinates $x$ and $y$. We find choices such that our limits are continuous. Connections to random interval graphs are given, including some examples. We also show a continuity result for the chromatic number and clique number of interval graphs. Some results on uniqueness of the limit description are given for general graph limits.

Recommendations

• Graph limits and hereditary properties
• Limits of dense graph sequences
• Random interval graphs
• On the interval number of random graphs
• Linear embeddings of graphs and graph limits

Cites work

• Algorithmic graph theory and perfect graphs
• An evolution of interval graphs
• Barcodes: The persistent topology of data
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Graph Classes: A Survey
• Graph limits and exchangeable random graphs
• Graphons, cut norm and distance, couplings and rearrangements
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Interval graphs and interval orders
• Interval graphs and maps of DNA
• Limits of dense graph sequences
• Mapping the genome
• Metrics for sparse graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Nonparametric Methods for Doubly Truncated Data
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• On Random Intersection Graphs: The Subgraph Problem
• On rectangle intersection and overlap graphs
• On the complexity of DNA physical mapping
• Poset limits and exchangeable random posets
• Probabilistic Symmetries and Invariance Principles
• Random interval graphs
• Random interval graphs
• Random Intervals
• Random time changes for sock-sorting and other stochastic process limit theorems
• Regularity partitions and the topology of graphons
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Statistical problems involving permutations with restricted positions
• The largest component in a subcritical random graph with a power law degree distribution
• The vertex degree distribution of random intersection graphs
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics
• Topics in Intersection Graph Theory

Cited in

(17)

• Characterization of 2-path signed network
• Linear embeddings of graphs and graph limits
• Differential calculus on graphon space
• Moments of two-variable functions and the uniqueness of graph limits
• A measure theoretic perspective on the space of Feynman diagrams
• Poset limits and exchangeable random posets
• Random graphons and a weak positivstellensatz for graphs
• Graph limits and parameter testing
• Random subcube intersection graphs. I: Cliques and covering
• Graphons and renormalization of large Feynman diagrams
• Action convergence of operators and graphs
• To Fix Those Plots, Use Limits!
• Semantic limits of dense combinatorial objects
• A Model for Birdwatching and other Chronological Sampling Activities
• Dense and nondense limits for uniform random intersection graphs
• Exchangeable interval hypergraphs and limits of ordered discrete structures
• Graph limits and hereditary properties

This page was built for publication: Interval graph limits

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