Interval graph limits

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.

Review text

The authors investigate a graph limit theory for dense interval graphs. This theory developed departs from 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, they fix a \(W\) and change underlying distribution of the coordinates \(x\) and \(y\). The main theorem is stated that a sequence of graphs \(G_n\) converges if the empirical measures \(\mu_n\) converge to a limiting probability \(\mu\) in the usual weak star topology, provided \(\mu\) satisfies a technical condition. They also show a continuity result for chromatic number and clique number of interval graphs. Some results on uniqueness of the limit description are given for general graph limits.

Recommendations

Cites work

Cited in

(17)

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)