Gaussian tail for empirical distributions of MST on random graphs

✍ Scribed by Sungchul Lee; Zhonggen Su

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 100 KB
• Volume: 58
• Category: Article
• ISSN: 0167-7152
• DOI: 10.1016/s0167-7152(02)00144-x

✦ Synopsis

Consider the complete graph K n on n vertices and the n-cube graph Q n on 2 n vertices. Suppose independent uniform random edge weights are assigned to each edges in K n and Q n and let T(K n ) and T(Q n ) denote the unique minimal spanning trees on K n and Q n , respectively. In this paper we obtain the Gaussian tail for the number of edges of T(K n ) and T(Q n ) with weight at most t=n.