Twenty Years of EPT Graphs: From Haifa to Rostock

详细信息    查看全文

• 作者：Martin Charles Golumbic
• 关键词：intersection graphs ; EPT graphs ; path graphs
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2006
• 出版时间：1 October 2006
• 年：2006
• 卷：27
• 期：Complete
• 页码：39-40
• 全文大小：99 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.