×

Tree and forest weights and their application to nonuniform random graphs. (English) Zbl 0930.05031

The tree-weight of a complete \(n\)-graph with weighted edges is the sum, over all spanning trees of the graph, of the products of the weights of the edges in the trees. The authors show that on the set of edge-weight distributions of given total weight, the tree-weight function attains its maximum at the uniform distribution; they also establish an analogous result with respect to the weights of the spanning rooted \(k\)-forests. Their results lead to the conclusion that the number of trees in a random rooted forest can be represented as a sum of \(n\) independent Bernoulli random variables where the success probabilities of the variables can be expressed in terms of the eigenvalues of the Kirchhoff matrix corresponding to the edge weights. The authors also apply their results to investigate the probability that a realisation of a certain sparse random graph model is a spanning tree.

MSC:

05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Barbour, A. (1982). Poisson convergence and random graphs. Math. Proc. Cambridge Philos. Soc. 92 349-359. · Zbl 0498.60016
[2] Beran, R. (1979). Exponential models for directional data. Ann. Statist. 7 1162-1178. · Zbl 0426.62030
[3] Biggs, N. (1974). Algebraic Graph Theory. Cambridge Univ. Press. · Zbl 0284.05101
[4] Bollobás, B. (1985). Random Graphs. Academic Press, New York. · Zbl 0567.05042
[5] Bollobás, B. and Erd os, P. (1976). Cliques in random graphs. Math Proc. Cambridge Philos. Soc. 80 419-427. · Zbl 0344.05155
[6] Chung, F. (1997). Spectral Graph Theory. Amer. Math. Soc., Providence, RI. · Zbl 0867.05046
[7] Chung, F. R. K. and Langlands, R. P. (1996). A combinatorial Laplacian with vertex weights. J. Combin. Theory Ser. A 75 316-327. · Zbl 0866.05039
[8] Durrett, R. (1991). Probability: Theory and Examples. Wadsworth & Brooks/Cole, Belmont, CA. · Zbl 0709.60002
[9] Erd os, P. and Rény i, A. (1959). On random graphs I. Publ. Math. Debrecen 6 290-297. · Zbl 0092.15705
[10] Erd os, P. and Rény i, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungarian Acad. Sci. 5 17-61.
[11] Farrell, E. J. (1981). Tree poly nomials of complete graphs and complete bipartite graphs. Pure Appl. Math. Sci. 13 7-13. · Zbl 0459.05032
[12] Gilbert, E. N. (1959). Random graphs. Ann. Math. Statist. 30 1141-1144. · Zbl 0168.40801
[13] Godsil, C. D. (1981). Matching behaviour is asy mptotically normal. Combinatorica 1 369-376. · Zbl 0504.05047
[14] Godsil, C. D. (1984). Real graph poly nomials. In Progress in Graph Theory 281-293. Academic Press, Toronto. · Zbl 0554.05059
[15] Godsil, C. D. (1993). Algebraic Combinatorics. Chapman & Hall, New York. · Zbl 0784.05001
[16] Grimmett, G. R. (1976). An upper bound for the number of spanning trees of a graph. Discrete Math. 16 323-324. · Zbl 0348.05106
[17] Grimmett, G. R. and McDiarmid, C. J. H. (1975). On colouring random graphs. Math Proc. Cambridge Philos. Soc. 77 313-324. · Zbl 0297.05112
[18] Grone, R. and Merris, R. (1988). A bound for the complexity of a simple graph. Discrete Math. 69 97-99. · Zbl 0645.05030
[19] Harper, L. H. (1967). Sterling behavior is asy mptotically normal. Ann. Math. Statist. 38 410-414. · Zbl 0154.43703
[20] Heilmann, O. J. and Lieb, E. H. (1972). Theory of monomer-dimer sy stems. Comm. Math. Phy s. 25 190-232. · Zbl 0228.05131
[21] Janson, S., Knuth, D. E., Luczak, T. and Pittel, B. (1993). The birth of a giant component. Random Structures Algorithms 4 233-358. · Zbl 0795.05127
[22] Jones, B. D. (1995). Tree components in random graph processes with nonuniform edge probabilities. Ph.D. dissertation, Dept. Statistics, Ohio State Univ.
[23] Kahn, J. (1996). A normal law for matchings. Dept. Mathematics, Rutgers Univ. · Zbl 0963.05111
[24] Kahn, J. (1997). Personal communication.
[25] Karo ński, M. (1995). Random graphs. In Handbook of Combinatorics I 351-380. MIT Press. · Zbl 0845.05082
[26] Kelmans, A. K. (1972). Asy mptotic formulas for the probability of k-connectedness of random graphs. Theory Probab. Appl. 17 243-254. · Zbl 0253.05136
[27] Luczak,T., Pittel, B. and Wierman, J. C. (1994). The structure of a random graph at the point of phase transition. Trans. Amer. Math. Soc. 341 721-748. JSTOR: · Zbl 0807.05065
[28] Marshall, A. W. and Olkin, I. (1979). Inequalities: Theory of Majorization and Its Applications. Academic Press, New York. · Zbl 0437.26007
[29] Maxwell, J. C. (1892). A Treatise on Electricity and Magnetism I, 3rd ed. Clarendon Press, Oxford.
[30] Minc, H. (1978). Permanents. Ency clopedia of Mathematics and Its Applications 6. Addison- Wesley, Reading, MA. · Zbl 0408.15016
[31] Moon, J. W. (1970). Counting Labelled Trees. Clowes, London. · Zbl 0214.23204
[32] Palmer, E. M. (1985). Graphical Evolution. Wiley, New York. · Zbl 0566.05002
[33] Percival, W. S. (1953). The solution of passive electrical networks by means of mathematical trees. Proceedings of the Institute of Electrical Engineers 100 143-150.
[34] Pitman, J. (1997). Probabilistic bounds on the coefficients of poly nomials with only real zeros. J. Combin. Theory Ser. A 77 279-303. · Zbl 0866.60016
[35] Pittel, B. (1990). On tree census and the giant component in sparse random graphs. In Random Structures and Algorithms 1 311-342. Wiley, New York. · Zbl 0747.05080
[36] Steele J. M. (1987). Gibbs measures on combinatorial objects and the central limit theorem for an exponential family of random trees. Probab. Engrg. Inform. Sci. 1 47-59. · Zbl 1133.60303
[37] Stepanov, V. E. (1969). Combinatorial algebra and random graphs. Theory Probab. Appl. 14 373-399. Stepanov, V. E. (1970a). On the probability of connectedness of a random graph Gm t Theory Probab. Appl. 15 55-56. Stepanov, V. E. (1970b). Phase transitions in random graphs. Theory Probab. Appl. 15 187-203. · Zbl 0239.05124
[38] van Lint, J. H. and Wilson, R. M. (1992). A Course in Combinatorics. Cambridge Univ. Press. · Zbl 0769.05001
[39] Verducci, J. S. (1989). Minimum majorization decomposition. In Contributions to Probability and Statistics (L. J. Gleser, M. D. Perlman, S. J. Press and A. R. Sampson, eds.) 160-173. Springer, New York.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.