Till innehåll på sidan

# 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

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.

Innehållsansvarig:webmaster@math.kth.se
Tillhör: Institutionen för matematik