Algebra, Geometry, and Combinatorics Seminar

Title: Frobenius Coin-Exchange Generating Functions

Abstract: We study variants of the Frobenius coin-exchange problem: Given n positive relatively prime parameters, what is the largest integer that cannot be represented as a nonnegative integral linear combination of the given integers? This problem and its siblings can be understood through generating functions with 0/1 coefficients according to whether or not an integer is representable. In the 2-parameter case, this generating function has an elegant closed form, from which many corollaries follow, including a formula for the Frobenius problem. We establish a similar closed form for the generating function indicating all integers with exactly k representations, with similar wide-ranging corollaries. This is joint work with Leonardo Bardomero.

Prerequisites: None

Title: Feasible regions meets pattern avoidance - The long awaited part three of feasible regions

Abstract: Glebbov, Hoppen and others introduced the notion of feasible regions for permutation patterns. Given a fixed integer k, the feasible region is a region in the real vector space indexed by permutations, defined as follows: for a sequence of permutations with growing size, compute the limit of the proportion of occurrences of each pattern of size k in each permutation, obtaining a vector. The feasible region arises as the limit of such vectors. Many interesting problems were studied in this context, like computing the dimension of the feasible region and its extreme points. Sometimes full descriptions can be given, but an overarching result is missing. If we consider consecutive patterns instead of classical patterns, we get simpler results, and we can totally characterize the feasible region: it is a polytope, and the vertices are given by cycles of a particular graph called overlap graph.

Prerequisites: permutations, convex geometry and polytopes

Title: Refinements and symmetries for volumes of flow polytopes

Abstract: Flow polytopes are an important class of polytopes in combinatorics whose lattice points and volumes have interesting properties and relations. The Chan-Robbins-Yuen (CRY) polytope is a flow polytope with normalized volume equal to the product of consecutive Catalan numbers. Zeilberger proved this by evaluating the Morris constant term identity, but no combinatorial proof is known. There is a refinement of this formula that splits the largest Catalan number into Narayana numbers, which Mészáros gave an interpretation as the volume of a collection of flow polytopes. We introduce a new refinement of the Morris identity with combinatorial interpretations both in terms of lattice points and volumes of flow polytopes. Our results generalize Mészáros's construction and a recent flow polytope interpretation of the Morris identity by Corteel-Kim-Mészáros. We prove the product formula of our refinement following the strategy of the Baldoni-Vergne proof of the Morris identity. Lastly, we study a symmetry of the Morris identity bijectively using the Danilov-Karzanov-Koshevoy triangulation of flow polytopes and a bijection of Mészáros-Morales-Striker. This is joint work with William Shi.

Prerequisites: graphs, some familiarity with hyperplane and vertex description of polytopes, juggling (optional)

Title: Uniform Asymptotic Growth of Symbolic Powers of Ideals

Abstract: Algebraic geometry (AG) is a major generalization of linear algebra which is fairly influential in mathematics. Since the 1980's with the development of computer algebra systems like Mathematica, AG has been leveraged in areas of STEM as diverse as statistics, robotic kinematics, computer science/geometric modeling, and mirror symmetry. Part one of my talk will be a brief introduction to AG, to two notions of taking powers of ideals (regular vs symbolic) in Noetherian commutative rings, and to the ideal containment problem that I study in my thesis. Part two of my talk will focus on stating the main results of my thesis in a user-ready form, giving a "comical" example or two of how to use them. At the risk of sounding like Paul Rudd in Ant-Man, I hope this talk will be awesome.

Prerequisites: polynomial rings, ideals, and quotients

Title: On topological generalizations of Ramsey's theorem.

Abstract: We will talk about characterizations of the Ramsey property as a topological generalization of Ramsey's theorem on colorings of 2-element sets of natural numbers. This will lead to an introduction to the theory of topological Ramsey spaces in which instances of those characterizations are realized. Time permitting, we also will discuss local versions of the Ramsey property and topological Ramsey spaces admitting metric projections where every Baire set has the Ramsey property.

Prerequisites: Basic topology. Some basic combinatorics is desirable but not necessary.

Title: Upper bound theorems: centrally symmetric polytopes vs centrally symmetric spheres

Abstract: If P is a centrally symmetric d-dimensional polytope with N vertices, what is the largest number of edges that P can have as a function of d and N? More generally, what about the largest number of k-dimensional faces for 0<k<d? How do the answers change if we replace a centrally symmetric polytope with a centrally symmetric triangulation of a sphere? I will survey some known results including some very recent progress (joint with Hailun Zheng) on these problems.

Prerequisites: some familiarity with convex sets, convex hulls, and simplicial complexes will be helpful.

Title: Combinatorial cones and the moduli of polarized donuts

Abstract: I will discuss recent work calculating certain topological invariants (i.e. the top-weight cohomology) of the moduli space of principally polarized abelian varieties (i.e. donuts) of dimension g for small values of g. The key idea is that this invariant is encoded combinatorially via a chain complex arising from certain polyhedral cones. This is joint work with Madeline Brandt, Melody Chan, Margarida Melo, Gwyneth Moreland, and Corey Wolfe.

Prerequisites: Group theory (namely symmetric groups and matrix groups), Linear algebra (quadratic forms), Polyhedral Geometry

Title: Integrable systems in symbolic and numerical algebraic geometry

Abstract: The Kadomtsev-Petviashvili (KP) equation is a universal integrable system that

describes nonlinear waves. It is known that algebro-geometric approaches to the KP equation provide solutions coming from a complex algebraic curve, in terms of the Riemann theta function associated with the curve. Reviewing this relation, I will introduce an algebraic object and discuss its algebro-geometric features: the so-called Dubrovin threefold of an algebraic curve, which parametrizes the solutions. Mentioning the relation of this threefold with the Schottky problem, I will report a procedure that is via the threefold and based on numerical algebro-geometric tools, which can be used to deal with this problem from the lens of computations. I will finally focus on the question: what happens to the threefold when the underlying curve degenerates?

Prerequisites: a bit of familiarity of basic algebraic geometry

Title: Symmetries of Surfaces

Abstract: As a geometric group theorist, my favorite type of manifold is a surface and my favorite way to study surfaces is by considering the mapping class group, which is the collection of symmetries of a surface. In this talk, we will think bigger than your average low-dimensional topologist and consider surfaces of infinite type and their associated “big” mapping class groups. I will then discuss some algebraic questions which we can ask about the mapping class group.

Prerequisites: group theory

Title: Isolated points on curves

Abstract: Let C be an algebraic curve over Q, i.e., a 1-dimensional complex manifold defined by polynomial equations with rational coefficients. A celebrated result of Faltings implies that all algebraic points on C come in families of bounded degree, with finitely many exceptions. These exceptions are known as isolated points. We explore how these isolated points behave in families of curves and deduce consequences for the arithmetic of elliptic curves. This talk is on joint work with A. Bourdon, Ö. Ejder, Y. Liu, and F. Odumodu.

Prerequisites: Field theory, particularly for finite extensions of Q. It may be helpful to know about the genus of a Riemann surface, but I will also explain this in the talk.

Title: Method of Moments for Gaussian Mixture Models

Abstract: Density estimation is a classical problem in statistics that asks, “Given a finite number of samples, can I guess which distribution my samples come from?“. The method of moments is one tool for density estimation that equates sample moments to moment equations for a given family of densities. When the underlying distribution is assumed to be a convex combination of Gaussian densities, the resulting moment equations are polynomial in the density parameters. Using tools from algebraic geometry, we examine the varieties stemming from these equations as the number of components increases. We consider special cases of this problem where some of the parameters are known and give a formula for the number of solutions to the corresponding moment variety. These results are then applied to density estimation of mixtures of Gaussian densities in high dimensions, with few components. A background in statistics and algebraic geometry will not be assumed. This is joint work with Carlos Amendola and Jose Israel Rodriguez.

Prerequisites: No formal prerequisites are required. Some knowledge of statistics and algebraic geometry will be helpful but are not necessary.

Title: Does the Simplex Method Dream with Matroids When it Sleeps?

Abstract: Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of modern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). Fast algorithms are indispensable!

George Dantzig's Simplex method is one of the most famous algorithms to solve LPs and SIAM even elected it as one of the top 10 most influential algorithms of the 20th Century. But despite its key importance, many simple easy-to-state mathematical properties of the Simplex method and its geometry remain unknown. The geometry of the simplex method is a topic in the convex-combinatorial geometry of polyhedra. Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra. In this talk, I will look at how two abstractions of simplex method to matroids provide useful insight into the properties of this famous question. The first type of abstraction is a natural embedding of every LP into an oriented matroid and the second abstraction is related to generalizing the pivoting moves to circuits of a matroid.

These is joint work with subsets of the following researchers: S. Kafer (Waterloo), L. Sanità(Eindhoven), I. Adler (UC Berkeley), S. Klee (Seattle U), and Z. Zhang (UC Davis)

Prerequisites: It would be nice but not indispensable if the audience knows the basics of

1) Linear Optmization and the famous Simplex method (I know SFSU has a course!!!!)

2) Basic definition of a matroid (With Federico Ardila a member of your faculty, I imagine a lot of students know what they are already)