The sizes of components in random circle graphs

Ramin Imany-Nabiyyi

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 3, page 511-533
  • ISSN: 2083-5892

Abstract

top
We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure of random circle graphs more deeply. As a corollary of one of our results we get the exact, closed formula for the expected value of the total length of all components of the random circle graph. Although the asymptotic distribution for this random characteristic is well known (see e.g. T. Huillet [4]), this surprisingly simple formula seems to be a new one.

How to cite

top

Ramin Imany-Nabiyyi. "The sizes of components in random circle graphs." Discussiones Mathematicae Graph Theory 28.3 (2008): 511-533. <http://eudml.org/doc/270649>.

@article{RaminImany2008,
abstract = {We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure of random circle graphs more deeply. As a corollary of one of our results we get the exact, closed formula for the expected value of the total length of all components of the random circle graph. Although the asymptotic distribution for this random characteristic is well known (see e.g. T. Huillet [4]), this surprisingly simple formula seems to be a new one.},
author = {Ramin Imany-Nabiyyi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {random interval graphs; geometric graphs; geometric probability},
language = {eng},
number = {3},
pages = {511-533},
title = {The sizes of components in random circle graphs},
url = {http://eudml.org/doc/270649},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Ramin Imany-Nabiyyi
TI - The sizes of components in random circle graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 3
SP - 511
EP - 533
AB - We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure of random circle graphs more deeply. As a corollary of one of our results we get the exact, closed formula for the expected value of the total length of all components of the random circle graph. Although the asymptotic distribution for this random characteristic is well known (see e.g. T. Huillet [4]), this surprisingly simple formula seems to be a new one.
LA - eng
KW - random interval graphs; geometric graphs; geometric probability
UR - http://eudml.org/doc/270649
ER -

References

top
  1. [1] L. Fatto and A.G. Konheim, The random division of an interval and the random covering of a circle, SIAM Review 4 (1962) 211-222, doi: 10.1137/1004058. Zbl0107.13503
  2. [2] E. Godehardt and J. Jaworski, On the connectivity of a random interval graphs, Random Structures and Algorithms 9 (1996) 137-161, doi: 10.1002/(SICI)1098-2418(199608/09)9:1/2<137::AID-RSA9>3.0.CO;2-Y Zbl0864.05080
  3. [3] L. Holst and J. Husler, On the random coverage of the circle, J. Appl. Prob. 21 (1984) 558-566, doi: 10.2307/3213617. Zbl0551.60014
  4. [4] T. Huillet, Random covering of the circle: the size of the connected components, Adv. in Appl. Probab. 35 (2003) 563-582, doi: 10.1239/aap/1059486818. Zbl1052.60010
  5. [5] H. Maehara, On the intersection graph of random arcs on a circle, Random Graphs' 87 (1990) 159-173. Zbl0746.05070
  6. [6] M. Penrose, Random Geometric Graphs (Oxford Studies in Probability, 2003), doi: 10.1093/acprof:oso/9780198506263.001.0001. 
  7. [7] A.F. Siegel, Random arcs on the circle, J. Appl. Prob. 15 (1978) 774-789, doi: 10.2307/3213433. Zbl0386.60013
  8. [8] H. Solomon, Geometric Probability (Society for Industrial and Applied Mathematics, Philadelphia, 1976). 
  9. [9] F.W. Steutel, Random division of an interval, Statistica Neerlandica 21 (1967) 231-244, doi: 10.1111/j.1467-9574.1967.tb00561.x. Zbl0168.15707
  10. [10] W.L. Stevens, Solution to a geometrical problem in probability, Ann. Eugenics 9 (1939) 315-320, doi: 10.1111/j.1469-1809.1939.tb02216.x. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.