High girth augmented trees are huge

详细信息    查看全文

• 作者：Noga Alon^a ; ^b ; ^c ; ¹ ; ^{nogaa@tau.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：High girth ; Ackermann Hierarchy ; Chromatic number
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：144
• 期：Complete
• 页码：7-15
• 全文大小：286 K

文摘

Let G be a graph consisting of a complete binary tree of depth h together with one back edge leading from each leaf to one of its ancestors, and suppose that the girth of G exceeds g  . Let h=h(g)$h=h(g)$ be the minimum possible depth of such a graph. The existence of such graphs, for arbitrarily large g, is proved in [2], where it is shown that h(g)$h(g)$ is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g)$h(g)$ is indeed Ackermannian.