Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A random graph with a subcritical number of edges


Author: B. Pittel
Journal: Trans. Amer. Math. Soc. 309 (1988), 51-75
MSC: Primary 05C80
DOI: https://doi.org/10.1090/S0002-9947-1988-0957061-X
MathSciNet review: 957061
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A random graph $ {G_n}(\operatorname{prob} (\operatorname{edge} ) = p)\;(p = c/n,\,0 < c < 1)$ on $ n$ labelled vertices is studied. There are obtained limiting distributions of the following characteristics: the lengths of the longest cycle and the longest path, the total size of unicyclic components, the number of cyclic vertices, the number of distinct component sizes, and the middle terms of the component-size order sequence. For instance, it is proved that, with probability approaching $ {(1 - c)^{1/2}}\exp (\sum\nolimits_{j = 1}^l {{c^j}/2j)} $ as $ n \to \infty $, the random graph does not have a cycle of length $ > l$. Another result is that, with probability approaching $ 1$, the size of the $ \nu $th largest component either equals an integer closest to $ a\;\log (bn/\nu \,{\log ^{5/2}}n)$, $ a = a(c)$, $ b = b(c)$, or is one less than this integer, provided that $ \nu \to \infty $ and $ \nu = o(n/{\log ^{5/2}}n)$.


References [Enhancements On Off] (What's this?)

  • [1] M. Ajtai, J. Komlós, and E. Szemerédi, The longest path in a random graph, Combinatorica 1 (1981), 1-12. MR 602411 (82d:05074)
  • [2] A. D. Barbour, Poisson convergence and random graphs, Math. Proc. Cambridge Philos. Soc. 92 (1982), 349-359. MR 671189 (84d:05141)
  • [3] C. Berge, Principles of combinatorics, Academic Press, New York, 1971. MR 0270922 (42:5805)
  • [4] B. Bollobás, Long paths in sparse random graphs, Combinatorica 2 (1982), 223-228. MR 698649 (84m:05043)
  • [5] B. Bollobás, T. I. Fenner and A. M. Frieze, Long cycles in sparse random graphs, Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honour of Paul Erdös, Academic Press, New York, 1984, pp. 59-64. MR 777164 (86f:05114)
  • [6] B. Bollobás, Random graphs, Academic Press, New York, 1985. MR 809996 (87f:05152)
  • [7] I. M. Curtiss, A note on the theory of moment generating functions, Ann. Math. Statist. 13 (1942), 430-433. MR 0007577 (4:163f)
  • [8] P. Erdös and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6(1959), 290-297. MR 0120167 (22:10924)
  • [9] -, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5(1960), 17-61. MR 0125031 (23:A2338)
  • [10] F. Harary and E. M. Palmer, Graphical enumeration, Academic Press, New York, 1973. MR 0357214 (50:9682)
  • [11] L. Katz, Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26 (1955), 512-517. MR 0070869 (17:48a)
  • [12] J. W. Moon, Counting labelled trees, Canadian Math. Congress, Clowes, London, 1970. MR 0274333 (43:98)
  • [13] A. M. Odlyzko and L. B. Richmond, On the number of distinct block sizes in partitions of a set, J. Combin. Theory Ser. A 38 (1985), 179-181. MR 784712 (86e:05007)
  • [14] B. Pittel, On the probable behavior of some algorithms for finding the stability number of a graph, Math. Proc. Cambridge Philos. Soc. 92 (1982), 511-526. MR 677474 (83k:68064)
  • [15] -, Paths in a random digital tree: limiting distributions, Adv. in Appl. Probab. 18 (1986), 139-155. MR 827333 (87k:68021)
  • [16] A. Rényi, Some remarks on the theory of trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73-85.
  • [17] A. Rényi and G. Szekeres, On the height of trees, J. Austral. Math. Soc. 7 (1967), 497-507. MR 0219440 (36:2522)
  • [18] J. Riordan, The enumeration of trees by height and diameter, IBM J. Res. Develop. 4 (1960), 473-478. MR 0140434 (25:3854)
  • [19] V. N. Sachkov, Probabilistic methods in combinatorial analysis, "Nauka", Moscow, 1978. (Russian) MR 522165 (80g:05002)
  • [20] G. Szekeres, Regular iteration of real and complex functions, Acta Math. 100 (1958), 103-258. MR 0107016 (21:5744)
  • [21] W. F. de la Vega, Long paths in random graphs, Studia Sci. Math. Hungar. 14 (1979), 335-340. MR 685900 (84c:05077)
  • [22] H. S. Wilf, Three problems in combinatorial asymptotics, J. Combin. Theory Ser. A 35 (1983), 199-207. MR 712105 (84i:05015)
  • [23] E. M. Wright, The number of connected sparsely edged graphs, J. Graph Theory 1 (1977), 317-330. MR 0463026 (57:2990)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C80

Retrieve articles in all journals with MSC: 05C80


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0957061-X
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society