Seminar

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

Algebraic and Enumerative Combinatorics

10 March 11:00 - 11:50

Darij Grinberg - Drexel University

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.
Organizers
Sara Billey
University of Washington
Petter Brändén
KTH Royal Institute of Technology
Sylvie Corteel
Université Paris Diderot, Paris 7
Svante Linusson
KTH Royal Institute of Technology

Program
Contact

Svante Linusson

linusson@math.kth.se

Other
information

For practical matters at the Institute, send an e-mail to administration@mittag-leffler.se