Seminars & Colloquia Calendar

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.