Title: Analytic Methods and Combinatorial Plants
| Speaker: | Jeremy Chizewer |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.
Abstract: In this talk, I will present the results of my masters thesis. I examine three applications of analytic methods to problems in combinatorics. By coincidence, each problem involves a combinatorial structure named for a plant--AVL trees, cactus graphs, and sunflowers--which we refer to collectively as combinatorial plants.
In our first result, we use a novel decomposition to create a succinct encoding for tree classes satisfying certain properties. This has applications to the study of data structures in computer science. To analyze our encoding, we derive asymptotics for the information-theoretic lower bound on the number of bits needed to store these trees. Our analysis applies to AVL trees (a commonly studied self-balancing binary search tree in computer science) as a special case. Joint work with Stephen Melczer, J. Ian Munro, and Ava Pun.
Next, we study the hat guessing game on cactus graphs and cycles. In this game, a player is placed on each vertex $v$ of a graph $G$ and assigned a colored hat from $h(v)$ possible colors. Each player makes a deterministic guess on their hat color based on the colors assigned to the players on neighboring vertices, and the players win if at least one player correctly guesses his assigned color. Joint work with I.M.J McInnis, Mehrdad Sohrabi and Shriya Kaistha.
Finally, we study the sunflower problem. A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. We study the case where the pairwise intersections of the set family are restricted, proving new bounds.