Dominating sets of random recursive trees

详细信息    查看全文

• 作者：Michele Zito ; Colin Cooper
• 关键词：Random trees ; dominating sets ; algorithms
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2006
• 出版时间：1 October 2006
• 年：2006
• 卷：27
• 期：Complete
• 页码：107-108
• 全文大小：107 K

文摘

The Cauchy-Davenport theorem states that, if p is prime and A, B are nonempty subsets of cardinality r, s in , the cardinality of the sumset A+B={a+b|aA,bB} is bounded below by min(r+s−1,p); moreover, this lower bound is sharp. Natural extensions of this result consist in determining, for each group G and positive integers r,s|G|, the analogous sharp lower bound, namely the function

Important progress on this topic has been achieved in recent years, leading to the determination of μ_G for all abelian groups G. In this note we survey the history of earlier results and the current knowledge on this function.