Connected components and evolution of random graphs: an algebraic approach
René Schott
and G.Stacey Staples
DOI: 10.1007/s10801-011-0297-1
Abstract
Questions about a graph's connected components are answered by studying appropriate powers of a special “adjacency matrix” constructed with entries in a commutative algebra whose generators are idempotent. The approach is then applied to the Erdös-Rényi model of sequences of random graphs. Developed herein is a method of encoding the relevant information from graph processes into a “second quantization” operator and using tools of quantum probability and infinite-dimensional analysis to derive formulas that reveal the exact values of quantities that otherwise can only be approximated. In particular, the expected size of a maximal connected component, the probability of existence of a component of particular size, and the expected number of spanning trees in a random graph are obtained.
Pages: 141–156
Keywords: keywords random graphs; graph processes; quantum probability
Full Text: PDF
References
1. Accardi, L., Ben Ghorbal, A., Obata, N.: Monotone independence, comb graphs and Bose-Einstein condensation. Infin. Dimens. Anal. Quantum Probab. Relat. Top. 7, 419-435 (2004)
2. Berezin, F.A.: The Method of Second Quantization. Academic Press, New York (1966)
3. Bohman, T., Frieze, A.: Avoiding a giant component. Random Struct. Algorithms 19, 75-85 (2001) J Algebr Comb (2012) 35:141-156
4. Bohman, T., Frieze, A., Wormald, N.: Avoiding a giant component in half the edge set of a random graph. Random Struct. Algorithms 25, 432-449 (2004)
5. Bohman, T., Kim, J.H.: A phase transition for avoiding a giant component. Random Struct. Algorithms 28, 195-214 (2006)
6. Bohman, T., Kravitz, D.: Creating a giant component. Comb. Probab. Comput. 15, 489-511 (2006)
7. Bollobás, B.: The evolution of random graphs. Trans. Am. Math. Soc. 286, 257-274 (1984)
8. Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6, 125-145 (2002)
9. Erdös, P., Rényi, A.: On random graphs. I. Publ. Math. (Debr.) 6, 290-297 (1959)
10. Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61 (1960)
11. Erdös, P., Rényi, A.: On the evolution of random graphs. Bull. Inst. Int. Stat. Tokyo 38, 343-347 (1961)
12. Flaxman, A., Gamarnik, D., Sorkin, G.: Embracing the giant component. Random Struct. Algorithms 27, 277-289 (2005)
13. Frieze, A.M., Łuczak, T.: Edge-disjoint spanning trees in random graphs. Period. Math. Hung. 21, 35-37 (1990)
14. Hashimoto, Y., Hora, A., Obata, N.: Central limit theorems for large graphs: Method of quantum decomposition. J. Math. Phys. 44, 71-88 (2003)
15. Molloy, M.: When does the giant component bring unsatisfiability? Combinatorica 28, 693-734 (2008)
16. Obata, N.: Quantum probabilistic approach to spectral analysis of star graphs. Interdiscip. Inf. Sci. 10, 41-52 (2004)
17. Palmer, E.M., Spencer, J.J.: Hitting time for k edge-disjoint spanning trees in a random graph. Period.
2. Berezin, F.A.: The Method of Second Quantization. Academic Press, New York (1966)
3. Bohman, T., Frieze, A.: Avoiding a giant component. Random Struct. Algorithms 19, 75-85 (2001) J Algebr Comb (2012) 35:141-156
4. Bohman, T., Frieze, A., Wormald, N.: Avoiding a giant component in half the edge set of a random graph. Random Struct. Algorithms 25, 432-449 (2004)
5. Bohman, T., Kim, J.H.: A phase transition for avoiding a giant component. Random Struct. Algorithms 28, 195-214 (2006)
6. Bohman, T., Kravitz, D.: Creating a giant component. Comb. Probab. Comput. 15, 489-511 (2006)
7. Bollobás, B.: The evolution of random graphs. Trans. Am. Math. Soc. 286, 257-274 (1984)
8. Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6, 125-145 (2002)
9. Erdös, P., Rényi, A.: On random graphs. I. Publ. Math. (Debr.) 6, 290-297 (1959)
10. Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61 (1960)
11. Erdös, P., Rényi, A.: On the evolution of random graphs. Bull. Inst. Int. Stat. Tokyo 38, 343-347 (1961)
12. Flaxman, A., Gamarnik, D., Sorkin, G.: Embracing the giant component. Random Struct. Algorithms 27, 277-289 (2005)
13. Frieze, A.M., Łuczak, T.: Edge-disjoint spanning trees in random graphs. Period. Math. Hung. 21, 35-37 (1990)
14. Hashimoto, Y., Hora, A., Obata, N.: Central limit theorems for large graphs: Method of quantum decomposition. J. Math. Phys. 44, 71-88 (2003)
15. Molloy, M.: When does the giant component bring unsatisfiability? Combinatorica 28, 693-734 (2008)
16. Obata, N.: Quantum probabilistic approach to spectral analysis of star graphs. Interdiscip. Inf. Sci. 10, 41-52 (2004)
17. Palmer, E.M., Spencer, J.J.: Hitting time for k edge-disjoint spanning trees in a random graph. Period.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition