High girth augmented trees are huge

Noga Alon

doi:10.1016/j.jcta.2016.06.004

High girth augmented trees are huge

Noga Alon

Research output: Contribution to journal › Article › peer-review

Abstract

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) 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) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g) is indeed Ackermannian.

Original language	English (US)
Pages (from-to)	7-15
Number of pages	9
Journal	Journal of Combinatorial Theory. Series A
Volume	144
DOIs	https://doi.org/10.1016/j.jcta.2016.06.004
State	Published - Nov 1 2016
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Ackermann Hierarchy
Chromatic number
High girth

Access to Document

10.1016/j.jcta.2016.06.004

Cite this

@article{0540683b928749ad9092cdd0f7928857,

title = "High girth augmented trees are huge",

abstract = "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) 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) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g) is indeed Ackermannian.",

keywords = "Ackermann Hierarchy, Chromatic number, High girth",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2016",

month = nov,

day = "1",

doi = "10.1016/j.jcta.2016.06.004",

language = "English (US)",

volume = "144",

pages = "7--15",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - High girth augmented trees are huge

AU - Alon, Noga

PY - 2016/11/1

Y1 - 2016/11/1

N2 - 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) 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) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g) is indeed Ackermannian.

AB - 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) 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) is at most some version of the Ackermann function. Here we show that this is tight and the growth of h(g) is indeed Ackermannian.

KW - Ackermann Hierarchy

KW - Chromatic number

KW - High girth

UR - https://www.scopus.com/pages/publications/84978878220

UR - https://www.scopus.com/pages/publications/84978878220#tab=citedBy

U2 - 10.1016/j.jcta.2016.06.004

DO - 10.1016/j.jcta.2016.06.004

M3 - Article

AN - SCOPUS:84978878220

SN - 0097-3165

VL - 144

SP - 7

EP - 15

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

High girth augmented trees are huge

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this