Algebra, Geometry, and Combinatorics Seminar

Title: A geometer’s guide to chromatic polynomials

Abstract: Chromatic polynomials count the number of ways to color a graph’s vertices so that no two adjacent vertices have the same color. One of the great combinatorial conjectures of the 20th century claimed that the chromatic polynomial of any graph is log-concave, meaning that the square of each of its interior coefficients is at least as big as the product of its neighbors. This conjecture remained unsolved for over 50 years until, in a major breakthrough, June Huh finally resolved it in 2012. Huh's work around this conjecture ultimately led to his receiving the Fields Medal in 2022. In this talk, we’ll explore chromatic polynomials, log-concavity, and a recently-discovered method by which we can give a new proof of Huh’s result by viewing it through the lens of classical ideas in convex geometry.

The research that this talk is based on is joint work with quite a few current and former SF State master's students: Jordan Guillory, Rebeca Hernandez Valdez, Anastasia Nathanson, Lauren Nowak, and Patrick O'Melveny.

Title: The generalized Pitman-Stanley polytope

Abstract: The eponymous Pitman-Stanley polytope introduced in 1999 is related to plane partitions of skew shape with entries 0 and 1. It has been well studied because of its connections to probability, parking functions, generalized permutahedra, and flow polytopes. We consider a generalization of this polytope related to plane partitions with entries 0, 1, ... , m. We show that this polytope can also be realized as a flow polytope of a grid graph. We give multiple characterizations of its vertices in terms of plane partitions of skew shape and integer flows. We also study formulas for the volume as well as for the number of lattice points and vertices of this polytope. This is joint work with William Dugan, Maura Hegarty and Alejandro Morales.

Title: What is the Best Way to Slice a Polytope?

Abstract: For literally hundreds of years mathematicians have been fascinated with slicing high-dimensional mathematical objects as a way to get knowledge and intuition of higher dimensions. There are many classical results and conjectures (e.g., Bourgain’s conjecture, recently a theorem, on the relation of volume and area of slices).

This talk is yet a computational contribution to this subject. I will present:

We concentrate on polytopes. Given a d-dimensional convex polytope P, what is the "best’’ slice of P by a hyperplane? Here "best’’ can mean many possible things, analytics e.g., a slice with the  largest volume? Or combinatorial, e.g. a slice with the largest number of vertices? etc. This touches on classical work by Lagrange, Bourgain, Ball, Koldobsky, Milman, and many other mathematicians. Not only we investigate the above optimization theorem but also, as we slice P with hyperplanes, we create many combinatorially different (d-1)-slices, which are also polytopes of course. E.g., for a 3-dimensional regular  cube there are 4 combinatorial types of slices (triangles, quadrilaterals, pentagons, hexagons). We investigate: How many different slices are there for a polytope P? How can we count them all? Can we give lower/upper bounds on their number?  What are extremal cases?

I will explain a powerful new geometric model (a moduli space of slices) and algorithmic framework that answers these problems (and others) in polynomial time when dim(P) is fixed. Moreover, we show  the problems have hard complexity otherwise.  This is joint work with Marie-Charlotte Brandenburg (MPI/KTH) and Chiara Meroni (Harvard/ETH). 

If time allows I will also show open questions that my research group is attacking right now.

Title: Gram Matrices for Isotropic Vectors

Abstract: We investigate determinantal varieties for symmetric matrices that have zero blocks along the main diagonal. In theoretical physics, these arise as Gram matrices for kinematic variables in quantum field theories. We study the ideals of relations among functions in the matrix entries that serve as building blocks for conformal correlators. We introduce computational methods for finding the defining equations of these varieties as well as numerical methods to calculate their degree.

Title: Tropical Fermat-Weber Points over Tree Spaces

Abstract: It is well-known that a tropical Fermat-Weber point with respect to the tropical symmetric metric might not be in a space of phylogenetic trees on m leaves even though all observations in the input are inside of the space.  In this talk we discuss a set of tropical Fermat-Weber points with respect to the tropical symmetric metric over the tree space and its application to the species tree reconstruction under the multi-species coalescent model.  This is joint work with S. Cox, R. Talbut, and J. Sabol.

Title: Spherical friezes

Abstract: A frieze pattern is an array of numbers that obeys simple local algebraic rules. Come build your own frieze pattern, and see how frieze patterns connect to triangulations of polygons. We will explore how a new type of frieze pattern can solve a problem in distance geometry. The speaker proudly holds a Master's in Math from SFSU!