Darij Grinberg: Gaussian elimination greedoids from ultrametric spaces: the combinatorics of Bhargava's generalized factorials

Tid: Ti 2020-03-10 kl 11.00 - 11.50

Föreläsare: Darij Grinberg, Drexel University

Plats: Institut Mittag-Leffler, Seminar Hall Kuskvillan


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.

Tillhör: Institutionen för matematik
Senast ändrad: 2020-03-07