Darij Grinberg: Gaussian elimination greedoids from ultrametric spaces: the combinatorics of Bhargava's generalized factorials
Time: Tue 2020-03-10 11.00 - 11.50
Location: Institut Mittag-Leffler, Seminar Hall Kuskvillan
Participating: Darij Grinberg, Drexel University
Abstract
Consider a finite set \(E\). Assume that each \(e \in E\) has a "weight" \(w(e) \in \mathbb{R}\) assigned to it, and any two distinct \(e, f \in E\) have a "distance" \(d(e,f) = d(f,e) \in \mathbb{R}\) assigned to them, such that the distances satisfy the ultrametric triangle inequality \(d(a,b) \leq \max\{d(a,c), d(b,c)\}\). How would you find a subset of \(E\) of given size with maximum perimeter (where the perimeter is defined by summing the weights of all elements and their pairwise distances)? It turns out that all such subsets form a greedoid -- an "order-aware" variant of a matroid; moreover, this greedoid is a Gaussian elimination greedoid (an analogue of matroid representability) over any sufficiently large field. The question has its origins in Manjul Bhargava's construction of generalized factorials, but is also a close relative of a problem in phylogenetics studied by Moulton, Semple and Steel. The talk will feature a quick introduction to greedoids; I will also propose an open question about strong greedoids in general.