Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- 111 Gregory Hall
- Date
- Oct 3, 2023 1:00 pm
- Speaker
- Mina Nahvi (UIUC)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Phone
- 217-898-4426
- Views
- 23
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: Mina Nahvi (UIUC)
Title: Reconstruction of Trees
The (n-\ell)-deck of an n-vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting \ell vertices. An n-vertex graph is \ell-reconstructible if it is determined by its (n-\ell)-deck, meaning no other graph has the same deck. In this talk, I will share the history of different variations of the Reconstruction Problem with a focus on trees. Furthermore, recent findings on reconstruction of trees will be presented, including our result which proves that every tree with at least 6\ell+11 vertices is \ell-reconstructible.
Joint work with Alexandr V. Kostochka, Douglas B. West, and Dara Zirlin.