Seminars & Colloquia Calendar

Download as iCal file

Experimental Mathematics Seminar

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.