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.
| 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.