Seminars & Colloquia Calendar
From generalized factorials to greedoids, or the unavoidability of the Vandermonde determinant
Darij Grinberg, Drexel University
Location: Join via WebEx
Date & time: Thursday, 30 April 2020 at 5:00PM - 6:00PM
Abstract: A classical exercise in algebra asks to prove that the product of the pairwise differences between any given n + 1 integers is divisible by the product of the pairwise differences between 0, 1, ..., n. In the late 90s, Manjul Bhargava took this as a starting point for his theory of "generalized factorials", in particular giving a quasi-algorithm for finding the gcd of the products of the pairwise differences between any n + 1 integers in S, where n is a given number and S is a given set of integers.
In this talk, I will explain why this is actually a combinatorial question in disguise, and how to answer it in full generality (joint work with Fedor Petrov). The general setting is a finite set E equipped with weights (every element of E has a weight) and distances (any two distinct elements of E have a distance), where the distances satisfy the ultrametric triangle inequality. The question is then to find a subset of E of given size that has maximum perimeter (i.e., sum of weights of elements plus their pairwise distances). It turns out that all such subsets form a "strong greedoid" -- a type of set system particularly adapted to optimization. Finally, this greedoid will reveal itself as a "Gaussian elimination greedoid" -- which, roughly speaking, means that the problem reduces to linear algebra.
Apart from generalizing a result of Bhargava's, this turns out to be connected to a problem in phylogenetics studied by Moulton, Semple and Steel.