Trees that contain all small trees

Anamay Tengse
Gowtham Raghunath Kurri
Friday, 7 Jun 2019, 17:15 to 18:15
A-201 Seminar Room
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.