Premium
Random interval graphs
Author(s) -
Pippenger Nicholas
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199807)12:4<361::aid-rsa4>3.0.co;2-r
Subject(s) - mathematics , pointwise , combinatorics , random graph , interval (graph theory) , constant (computer programming) , clique , exponential distribution , expected value , distribution (mathematics) , binary logarithm , discrete mathematics , statistics , graph , mathematical analysis , computer science , programming language
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 /∞ and the M / M /∞ models, with arrival rate λ per mean service time. The expected number of vertices is e λ , and the distribution of the N / e λ converges pointwise to an exponential distribution with mean 1 as λ tends to infinity. This implies that the distribution of log N −λ converges pointwise to a distribution with mean −γ (where γ is Euler's constant) and variance π 2 /6. The size K of the largest clique falls in the interval [ e λ−2 log λ, e λ+1] with probability tending to 1 as λ tends to infinity. Thus the distribution of the ratio K /log N converges pointwise to that of the constant e , in contrast to the situation for random graphs generated by unbiased coin flips, in which the distribution of K /log N converges pointwise to that of the constant 2/log 2. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 361–380, 1998