The UC Berkeley combinatorics seminar |
---|
DATE | SPEAKER | TITLE (click to show abstract) |
August 29th | Alex McDonough, UC Davis |
Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane GraphsEvery finite graph has an associated sandpile group, which can be described in terms of chip-firing. A sandpile torsor algorithm is a map which associates each plane graph (i.e. planar embedding) with a free transitive action of its sandpile group on its spanning trees. We define a notion of consistency, which requires a torsor algorithm to be preserved with respect to a certain class of contractions and deletions. We then show that the rotor-routing sandpile torsor algorithm (which is equivalent to the Bernardi algorithm) is consistent. Furthermore, we demonstrate that there are only three other consistent algorithms, which all have the same structure as rotor-routing. This proves a conjecture of Klivans. Joint work with Ankan Ganguly. |
September 5th | Academic Holiday - No Seminar | |
September 12th | Max Hlavacek, UC Berkeley |
Parking Functions, Bond Lattices, and Unimodal ForestsAbstract: Parking functions are a well-studied combinatorial object with numerous connections to other areas of math. They can be seen in the maximal chains of the noncrossing partition lattice NC_n; Stanley defined a bijection between the two sets in 1996. In 1964, Rota introduced the bond lattice, a subposet of the partition lattice derived from a given graph. When the graph is of a certain form, the bond lattice is a subposet of NC_n, encoding a subset of the parking functions of length n. Our work builds on the work of Ahirwar, Fishel, Gya, Harris, Pham, Vindas Meléndez, and Vo in 2022, who found that the bond lattices of certain triangulation graphs have the same number of maximal chains as there are ordered cycle decompositions on n integers. Anders and Archer further showed in 2019 that each ordered cycle decomposition corresponds to a rooted unimodal forest. Although there exist many bijections between parking functions and rooted forests, our work develops a recursive bijection between parking functions of a triangulation graph and unimodal unordered rooted labelled forests. This project is joint work with Josephine Brooks, Susanna Fishel, Sophie Rubenfeld, and Bianca Teves. |
September 19th | Jesús A. De Loera, UC Davis |
Rado Numbers: A story of combinatorics, computation, and polynomialsIt is indisputable Ramsey-type numbers are among the most mysterious and fascinating in Combinatorics. I discuss methods from algebraic geometry and SAT Boolean solvers to study a family of Ramsey-type numbers arising in arithmetic Ramsey theory: I will focus on the lovely Rado numbers. For a positive integer k and linear equation E, the Rado number R_k(E) is the smallest number n such that every k-coloring of {1,2,...,n} contains a monochromatic solution to the equation E. A very famous example are Schur numbers, which are the Rado numbers for the equation E={x+y=z}. (Incidentally, Issai Schur was Rado’s Ph.D advisor at Berlin). I will discuss computation, bounds, and verification of these numbers. We computed many new exact values for Rado numbers of the form R_3(ax+by+cz = 0) using SAT solvers. In particular, we give a method for computing infinite families of Rado numbers, solving a few open questions. Regarding complexity and verification: Suppose someone suggests to you the value of R_k(E) . How can you certify that this value is correct? We encode the problem as a system of polynomial equations and show that the degrees of Nullstellensatz certificates are actually bounded above by another Ramsey-number arising in a two-player game. The extremal k-colorings are in fact the solutions of this system which says that proving that the proposed value of R_k(E) is not correct may required a doubly exponential certificate. At the heart is how combinatorial algebraic geometry relates to Ramsey numbers. This is joint work with Ph.D candidate Jack Wesley. |
Different time, and place: September 26th, 5 PM, Evans 762 | Esme Bajo, UC Berkeley |
Boundary h*-polynomials of rational polytopesWe will talk about the geometric interpretation of h*-polynomials of rational polytopes and about the history of symmetric decompositions of h*-polynomials. Then we will look at decompositions of h*-polynomials from the perspective of boundaries of polytopes, and see how this perspective reveals properties of reflexive and Gorenstein polytopes. This is joint work with Matthias Beck. |
October 3rd | Volkmar Welker, Philipps-Universität Marburg |
Matroid type complexes with orthogonality relationMatroids generalize independence in vectorspaces. To a matroid one associates its lattice of flats, the independence complex and the poset of direct sum decompositions. What if the vectorspace comes with a non-degenerate form ? We provide an overview on what is known about suitable replacements of these objects. (joint work with Kevin Piterman) |
October 10th | Sogol Jahanbekam, San Jose State University |
Graph coloring, algorithms, and applicationsA coloring over the vertices of a graph G is proper if adjacent vertices of G receive different colors. The smallest number of colors we need to color the vertices of a graph properly is said to be the chromatic number of the graph. In this talk, we talk about the proper coloring of graphs and algorithm complexities for the problem. We then proceed with some applications of the proper coloring of graphs including its applications in 3D-printing, and we conclude by developing an improved algorithm for 3-colorability of graphs with large minimum degree. |
Different day, time, and place: Tuesday October 11th, 2 PM, Evans 891 | Oscar Kivinen, École polytechnique fédérale de Lausanne |
Rational Catalan combinatorics and the small quantum groupRecently, a new geometric interpretation of the small quantum group has been proposed by Bezrukavnikov and his coauthors. The center of the small quantum group turns out to be related to a family of varieties called affine Springer fibers, the geometry of which is intimately related to rational Catalan combinatorics. I will describe some combinatorial answers to geometric and algebraic questions (such as describing the dimension of the center) in this setup, following joint work with Nicolas Hemelsoet and Anna Lachowska. I will also state a number of open questions. |
October 17th | Eugene Gorsky, UC Davis |
Generic curves and non-coprime CatalansGiven a plane curve singularity C, one can define an algebraic variety called the compactified Jacobian of C. We introduce a class of "generic" curves, and describe the homology of the corresponding compactified Jacobians in terms of combinatorics of non-coprime rational q,t-Catalan numbers. As a byproduct, we confirm a conjecture of Cheredinik and Danilenko for generic curves. All notions will be introduced in the talk, this is a joint work with Mikhail Mazin and Alexei Oblomkov. |
October 24th | Emily Clader, San Francisco State Univeristy |
Permutohedral Complexes and Curves With Cyclic ActionThere is a beautiful story connecting the combinatorics of the permutohedron, the algebra of the symmetric group, and the geometry of a particular moduli space of curves first studied by Losev and Manin. I will describe these three seemingly disparate worlds and their connections to one another, and then I will discuss joint work with C. Damiolini, D. Huang, S. Li, and R. Ramadas that generalizes the story by introducing a new family of polytopal complexes and relating it to a new family of moduli spaces. |
October 31st | Freddie Huang, UC Berkeley |
Domino tilings of the generalized Aztec triangleA configuration of the twenty vertex model is an orientation of each side of a triangular lattice such that at each vertex the number of incoming and outgoing edges is equal. This is similar to the six vertex model, which takes place on a square lattice, that has long been of interest to combinatorialists for its connections to alternating sign matrices. Recently Di Francesco and Guitter also uncovered interesting combinatorics for the twenty vertex model which previously was primarily studied by physicists. Later, Di Francesco was also able to relate configurations of the twenty vertex model to domino tilings of a so-called Aztec triangle, and conjectured a product formula for enumerating these configurations. We will define these objects and discuss their enumeration and relation to partitions, and then introduce a generalized Aztec triangle for which we obtain a generalization to Di Francesco's conjecture. Joint work with Sylvie Corteel. |
November 7th | Nicolle González, UC Berkeley |
Excellent Filtrations for Tensor Products of Demazure CrystalsCrystals are certain directed graphs that encode certain algebraic and combinatorial properties of U_q(g)-modules. In particular, for any irreducible highest weight module V(\lambda) we can associate a corresponding highest weight crystal B(\lambda). Demazure modules and their corresponding crystals generalize this construction. Namely, Demazure modules are generated by extremal weight vectors under the action of the Borel. Thus, their corresponding crystals are certain truncations of B(\lambda). Classically, tensor products of irreducible highest weight modules always admit filtrations by Weyl modules, a fact that is reflected in B(\lambda) \otimes B(\mu) decomposing as a disjoint union of highest weight crystals. The analogous question, of tensor products of Demazure modules always admitting a Demazure filtration, is false. In this talk I will discuss under what conditions this filtration is satisfied from a crystal theoretic perspective. Namely, I will explain a sufficient and necessary condition for when tensor products of Demazure crystals remain Demazure. |
Anastasia Chavez, Saint Mary's College of California |
The valuation polytope of the zig-zag posetThe summer 2021 Latinx Mathematical Research Community (LMRC) served as a catalyst for several research projects in various areas of mathematics. This talk will introduce the research of one such project. Geissinger defined the valuation polytope as the set of all [0,1]-valuations on a finite distributive lattice. We study the valuation polytope, \mathcal{V}(Z_n), arising from the height 2 up-down poset on n elements, referred to as the zig-zag poset Z_n. Dobbertin showed that the valuation polytope of any poset can be described as the convex hull of vertices characterized by all the chains of that poset. It follows that the dimension of the valuation polytope is the number of elements of the corresponding poset. We discuss recent combinatorial results of \mathcal{V}(Z_n) such as its normalized volume, unimodular triangulation, facet enumeration, and connection to the root polytope. This is joint work with Federico Ardila, Jessica De Silva, Pamela E. Harris, Jose Luis Herrera Bravo, and Andrés R. Vindas-Meléndez. |
|
November 21st (the talk will be over Zoom, although we will still meet at the usual time and place) | Yifei Li, University of Illinois, Springfield |
A combinatorial Proof of a Tantalizing Symmetry on Catalan ObjectsWe investigate a tantalizing symmetry on Catalan objects. In terms of Dyck paths, this symmetry can be interpreted in the following way: if wn,k,m is the number of Dyck paths of semilength n with k occurrences of UD and m occurrences of UUD, then w2k+1,k,m = w2k+1,k,k+1−m. We give a combinatorial proof of this symmetry which makes use of the cycle lemma and an alternative interpretation of the numbers wn,k,m involving plane trees. In particular, our combinatorial proof expresses the numbers w2k+1,k,m in terms of Narayana numbers, and we generalize this to a relationship between the numbers wn,k,m and a family of generalized Narayana numbers due to Callan. |
Tamsen McGinley, Santa Clara University |
Crystals Graphs, Perforated Tableaux, and Combinatorial ObjectsCrystal graphs of biwords are directed graphs whose nodes are biwords and whose edges are determined by "crystal operators". These are used to model irreducible representations of GL_n. We present a new model for the nodes of a crystal graph, called a "perforated tableaux", on which the crystal operators are easily defined. We show that several well-known combinatorial objects, including semi-standard Young tableaux, Littlewood-Richardson fillings, and the Robinson-Schensted-Knuth correspondence, naturally appear in the setting of perforated tableaux. |
|
Joseph Pappe, UC Davis |
Promotion and Cyclic Sieving Phenomenon for Fans of Dyck PathsUsing chord diagrams, we construct a diagrammatic basis for the space of invariant tensors of certain Type B representations. This basis carries the property that rotation of the chord diagrams intertwines with the natural action of the longest cycle in the symmetric group on the tensor factors. Our approach involves constructing an injection from the set of r-fans of Dyck paths (resp. vacillating tableaux) of length n into the set of chord diagrams on [n] that intertwines promotion and rotation. From this, we give a cyclic sieving phenomenon on r-fans of Dyck paths. This is joint work with Stephan Pfannerer, Anne Schilling, and Mary Claire Simone. |