Tata Institute of Fundamental Research

Trees that contain all small trees

STCS Student Seminar
Speaker: Anamay Tengse
Organiser: Gowtham Raghunath Kurri
Date: Friday, 7 Jun 2019, 17:15 to 18:15
Venue: A-201 Seminar Room

(Scan to add to calendar)
Abstract:  A tree is said to be n-universal if it "contains" all binary trees with at most n leaves. A result of Chung, Graham and Coppersmith from 1981 shows that when this containment is via sub-graphs, an n-universal tree requires size n^Omega(log(n)). Whereas when containment is defined via taking minors, a construction by Hrubes, Wigderson and Yehudayoff from 2010 gives an n-universal tree of size O(n^4). In this talk, we will look at both these results. If time permits, we will also discuss the context in which the latter group studied universal trees.