Campus Event Calendar

Event Entry

What and Who

Optimization with pattern-avoiding input

Benjamin Berendsohn
Freie Universität, Berlin
AG1 Mittagsseminar (own work)

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  
AG Audience

Date, Time and Location

Tuesday, 20 February 2024
30 Minutes
E1 4


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
passcode not visible

Nidhi Rathi, 02/13/2024 12:52
Nidhi Rathi, 01/31/2024 13:33
Nidhi Rathi, 01/31/2024 13:30 -- Created document.