Balance in Random Trees

• 作者: Azer Akhmedov Warren Shreve
• 来源期刊: 离散数学期刊(英文)
• 学科: 医学
• 关键词: RANDOM Trees BALANCE Equicolorable GRAPHS
• 年，卷（期）: 2014,（4）
• 页码范围: 97-108
• 页数: 12页
• 分类号: R73

摘要

We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly &#107-balanced for any &#107 &#8805 &#51. Definition: Color the vertices of graph &#71 with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored. &#71 is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.