Technical Reports

The ICICS/CS Reading Room

UBC CS TR-97-04 Summary

Random Interval Graphs, February 1997 Nicholas Pippenger, 22 pages

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number of customers arriving during a busy period, while the size K of the largest clique (which for interval graphs is equal to the chromatic number) corresponds to the maximum number of customers in the system during a busy period. We obtain the following results for both the M/D/Infinity and the M/M/Infinity models, with arrival rate lambda per mean service time. The expected number of vertices is e^lambda, and the distribution of the N/e^lambda tends to an exponential distribution with mean 1 as lambda tends to infinity. This implies that log N is very strongly concentrated about lambda-gamma (where gamma is Euler's constant), with variance just pi^2/6. The size K of the largest clique is very strongly concentrated about e lambda. Thus the ratio K/log N is strongly concentrated about e, in contrast with the situation for random graphs generated by unbiased coin flips, where K/log N is very strongly concentrated about 2/log 2.

If you have any questions or comments regarding this page please send mail to