Augmented trees with high girth

-
Noga Alon , Tel Aviv University
Fine Hall 224

Let G be a graph consisting of a complete binary tree of depth h together with a back edge from each leaf connecting it to one of its ancestors. Suppose further that the girth of G exceeds g. What is the minimum possible depth h=h(g) in such a graph ? This question is motivated by results in a joint paper with Kostochka, Reiniger, West and Zhu, where these graphs are used to provide simple explicit constructions of graphs and hypergraphs of high girth and high chromatic number, as well as tight examples of sparse high girth bipartite graphs with large list-chromatic number.