*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 8th October, 3:00 in Fine Hall 224. Speaker: Noga Alon, Tel Aviv University and IAS, Princeton Title: Augmented trees with high girth 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. ----------- Next week: Aurelie Lagoutte Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)