The speaker has obtained his Bachelor's and Master's degrees at Freie Universität
Berlin, and is currently finishing my PhD under supervision of László Kozma.

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this talk, we consider the effect of pattern-avoidance on two optimization problems.

First is the euclidean minimum spanning tree problem: A pattern- avoiding point set in the unit square always has an MST of length O(log n), in contrast to Θ(sqrt(n)) in the general case. Second is the offline dynamic binary search tree problem: Given a pattern-avoiding sequence, a dynamic BST can serve the sequence in linear time. This improves previous almost-linear bounds, and constrasts with the general Θ(n log n). Central tools for our results are the Marcus-Tardos Theorem and so-called twin-width decompositions, both of which can be generalized to geometric settings. We describe these concepts and sketch some proofs.

(Based on joint work with László Kozma and Michal Opler.)

Nidhi Rathi

+49 681 9325 1134

--email hidden