Interval graph limits

DOI10.1007/S00026-012-0175-0zbMATH Open1274.60028arXiv1102.2841OpenAlexW2007695797WikidataQ40503072 ScholiaQ40503072MaRDI QIDQ1950423FDOQ1950423

Authors: Persi Diaconis, Susan Holmes, Svante Janson 

Publication date: 13 May 2013

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

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.

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

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

zbMATH Keywords

intersection graphsinterval graphsgraph limits

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

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

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)