The probability of an interval graph, and why it matters
Joel E. Cohen, János Komlós, Thomas J. Mueller · Proceedings of symposia in pure mathematics · 1979
An interval graph is the intersection graph of a family of intervals of the real line. Interval graphs have been used for inference in several sciences, including archeology, ecology, genetics, and psychology. In these applications, the strength of inference depends on the probability that a random graph is an interval graph. Using a definition of a random graph due to Erdtls and ~e'n~i [el, we obtain exact probabilities and asymptotic and Monte Carlo estimates of the probabilities, for varying numbers of vertices and edges. We also obtain the asymptotic probability that a randcm graph is a circular arc graph, which is the intersection graph of a family of arcs on the circle. Some mathematical questions arising in scientific inference remain unanswered.