Organizers: Ben Braun and Carl Lee

Fall 2010

Monday, September 15, 2010
David Cook
University of Kentucky
Title: A quadruple of enumerative methods for plane partitions
Speaker: David Cook
Time / Place: 2:00 p.m., POT 745
Abstract: In this expository talk we will explore four different methods to enumerate plane partitions, all of which are equivalent. Besides direct counting, we will also discuss tiling hexagons by lozenges, finding non-intersecting lattice paths, and perfectly matching bipartite graphs. The latter two give matrices whose determinant and permanent, respectively, provide the desired enumeration. Examples and figures will be plentiful in this introductory level talk. Euler-Mahonian statistics via polyhedral geometry.

Friday, September 24, 2010
Ben Braun
University of Kentucky
Title: Generating Functions for Plane Partitions
Time / Place: 2:00 p.m., POT 845
Abstract: We will discuss generating functions for plane partitions of different types. We will also comment on some historical aspects of plane partitions.

Title: Simplicial Complexes of Triangular Ferrers Boards
Speaker: Matt Zeckner
Time / Place 2:00 p.m., POT 745
Abstract: We study the simplicial complex that arises from non-attacking rook placements on a subclass of Ferrers boards that have a_i rows of length i where a_i>0 and i\leq n for some positive integer n. In particular, we will investigate their homotopy type and homology. This is joint work with Eric Clark.

UK WILDCATS SEMINAR
Title: Reflexive polytopes, Gorenstein polytopes, and combinatorial mirror symmetry
Ben Nill, University of Georgia
Time / Place: 2:00 p.m., POT 745
Abstract: In this talk I will give a survey on Gorenstein polytopes. These are lattice polytopes that exhibit a natural duality. They can also be characterized purely algebraically or via Ehrhart theory. I will start by introducing a big class of important examples: reflexive polytopes - and possibly some new generalizations. The arguably most-studied Gorenstein polytope is the Birkhoff polytope: the polytope of doubly stochastic matrices. I will give a brief view on how a long-standing conjecture by Stanley on the unimodality of its so-called h^*-polynomial has been proved by Athanasiadis and generalized to Gorenstein polytopes by Bruns and Roemer. Finally, I would like to talk about recent results and open questions on Gorenstein polytopes as combinatorial models of topologically mirror-symmetric Calabi-Yau manifolds.

Speaker: David Haws
Title: Optimality of the Neighbor Joining Algorithm and Faces of the Balanced
Time / Place 2:00 p.m., POT 745
Abstract: Balanced minimum evolution (BME) is a statistically consistent distance- based method to reconstruct a phylogenetic tree from an alignment of molecular data. It is a weighted least-squares solution that puts more emphasis on shorter distances than longer ones. In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear function, the dissimilarity map, over the BME vectors. This is equivalent to optimizing the linear functional over the BME polytope which is the convex hull of the BME vectors obtained from Pauplin’s formula applied to all binary trees. The BME method is related to the Neighbor Joining (NJ) algorithm which was shown to be a greedy optimization of the BME principle. The connection between the (NJ) Algorithm and the BME method has been studied previously to understand when the NJ Algorithm returns a BME tree for small number of taxa. We aim to elucidate the structure of the BME polytope and strengthen the connection between the BME method and NJ Algorithm. We prove that any subtree-prune-regraft move from a binary tree to another binary tree corresponds to an edge of the BME polytope. Finally, we show that for any order of joining nodes to form a tree, there exists a distance matrix such that the NJ Algorithm returns the BME tree. Minimum Evolution Polytope

WILDCATS SEMINAR
Title: The boolean complex of a Coxeter system
Speaker: Bridget Tenner, DePaul University
Time / Place: 2:00 p.m., POT 745
Abstract: In any Coxeter group, the set of elements whose principal order ideals are boolean under the Bruhat order defines a cell complex, called the boolean complex. We show that for any Coxeter system of rank n, this boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres, and the number of such spheres can be computed recursively from the Coxeter graph. Specific calculations of this number are given for certain families of Coxeter systems and graphs. The proof of this homotopy equivalence uses discrete Morse theory, and the proof is phrased in terms of finite simple graphs, thought of as unlabeled Coxeter graphs. We hint at the homological structure of this complex as well, which yields combinatorial proofs of many of our identities. This is joint work with Kari Ragnarsson, and with Anders Claesson and Sergey Kitaev.

Title: Characterizing the f-vectors of Simplicial Poset Balls
Speaker: Sam Kolins, Cornell University
Time / Place: 2:00 p.m., POT 745
Abstract: A simplicial cell decomposition of a manifold is a generalization of the idea of a triangulation. The faces of a simplicial cell decomposition are still simplexes but two faces can intersect in a subcomplex of their boundaries instead of just a single face. In particular there can be multiple faces on the same vertex set. The f-vector of a simplicial cell decomposition is the list of the numbers of simplexes of each dimension in the decomposition. In this talk we will discuss attempts to characterize the possible f-vectors of simplicial cell decompositions of various manifolds. Complete characterizations are known in the cases of spheres (Stanley '91 and Masuda '05), products of spheres, and real projective spaces (Murai '10). I will discuss my recent work on characterizing the f-vectors of balls. This involves using tools from commutative algebra to obtain new necessary conditions on the f-vectors, as well as some constructive results. This work gives a complete characterization of the f-vectors of simplicial cell decompositions of balls up through dimension six, though the problem remains open in higher dimensions.

UK WILDCATS SEMINAR
Title: Algebraic models in systems biology
Speaker: Dr. Reinhard Laubenbacher, Virginia Bioinformatics Institute
Time / Place: 3:00 p.m., CB 345
Abstract: Progress in systems biology relies on the use of mathematical and statistical models for system level studies of biological processes. Several different modeling frameworks have been used successfully, including traditional differential equations based models, a variety of stochastic models, agent-based models, and Boolean networks, to name some common ones. This talk will focus on several types of discrete models, and will describe a common mathematical approach to their comparison and analysis, which relies on computer algebra. Hence, we refer to such models as "algebraic models." The talk will present specific examples of biological systems that can be modeled and analyzed in this way.

Wednesday, Dec 1, 2PM
POT 745
Speaker: Peter Huggins, University of Kentucky Department of Statistics
Title: Some geometry and statistics of linear rankings
Abstract: Each year, US News and World Report ranks US colleges according to a linear combination of various measured categories. Yet the choice of weights for the categories is subjective, and there can be many "linear rankings" that arise by choosing different weights. The set of all possible linear rankings for a given set of points (universities) correspond to the vertices of a zonotope. Similarly, the set of all possible un/ordered k-tuples of top k points correspond to the vertices of polytopes we call un/ordered k-set polytopes. After reviewing the underlying geometry, we present a parametric study of university ranking data, and discuss applications to parametric study of shortest paths problems in computational biology. Finally, we propose some new non-parametric tests using k-set polytopes, to test for significant outliers in multivariate integer data (such as ranking data) and discuss asymptotic power. Much of this material is joint work with Lior Pachter.

Title: Degree bounds for type-A weight rings and Gelfand--Tsetlin semigroups
Speaker: Tyrrell McAllister, University of Wyoming
Time / Place: 2:00 p.m., POT 745
Abstract: A weight ring in type A is the coordinate ring of the GIT quotient of the variety of flags in \mathbb{C}^n modulo a twisted action of the maximal torus in SL(n,\mathbb{C}). In joint work with Benjamin J. Howard, we show that any weight ring in type A is generated by elements of degree strictly less than the Krull dimension, which is at worst O(n^2). An historically important example is the ring R of invariants of n-tuples of points in the projective plane, modulo automorphisms of the plane. In this case, we get a linear upper bound of 2n − 8 for the degrees in which R is generated. We also discuss a toric degeneration R' of R to the algebra generated by the lattice points in the cone over a certain Gelfand--Tsetlin polytope. Howard, Millson, Snowden, and Vakil used R' to study the invariants of n-tuples on the projective line. However, we show that, in higher-dimensional projective space, this toric degeneration ceases to be very useful. In contrast to the linear upper bound on the degrees needed to generate R, we find essential generators for R' whose degrees are exponential in n.

Spring 2011

Wednesday, January 19, 2011
3PM POT 745
Speaker: Carl Lee
Title: The cd-Index and the CD-Index
Abstract: I will provide an overview of the cd-index, the CD-index, and the h-vector for convex polytopes. In particular, I will discuss formulas for switching among these, as well as some questions raised by Jonathan Fine about extending the h-vector. The talk will be at an introductory level, and all are welcome!

Title: Finite Field Analogues in Arithmetic Combinatorics
Speaker: Paul Koester
Time / Place: 3:00 p.m., POT 745
Abstract: If you can't solve a real variable or integer variable problem, it often helps to look at an analogous problem over a finite field. This idea has been used extensively over the last decade in arithmetic combinatorics (Szemeredi and Frieman-type theorems), combinatorial geometry (Erdos distance problem), and harmonic analysis (Kakeya and restriction theorems). Often, the finite field analogue proves to be easier to understand, yet can give great insights into the original problem. Sometimes the finite field analogue proves to be more difficult to understand. Sometimes there may be more than one natural finite field analogue of a given problem. We will survey some of the successes of finite field models and some of the difficulties that can arise in finite field models. This talk will be of an expository nature and should be accessible to graduate students.

Wednesday, Feb 2
Speaker: JiYoon Jung
Title: The topology of restricted partition posets
3PM POT 745
Abstract: The d-divisible partition lattice is the collection of all partitions of an n-element set where each block size is divisible by d. Stanley showed that the Mobius function of the d-divisible partition lattice is given (up to a sign) by the number of permutations on n-1 elements where every dth position is a descent. Wachs showed that this lattice has an EL-shelling, and hence obtained as a corollary that the homotopy type of the order complex is a wedge of spheres. Finally, Calderbank, Hanlon and Robinson considered the action of the symmetric group on the top homology group and showed it is a Specht module of a border strip corresponding to the composition (d, ..., d,d-1). Using a different proof approach, we will generalize these results to any descent pattern. This is joint work with Richard Ehrenborg.

Speaker: Adib Bagh
Title: From Nash equilibria in discrete games to Nash equilibria in games over a
Time / Place: 3:00 p.m., POT 745
Abstract: In this talk, we will review the notion of Nash equilibrium and a number of related concepts in game theory. We will then show that the KKM theorem on the simplex, a precursor to most non-algebraic fixed point theorems, can be used to extend existence results in discrete games, where each player has a finite set of strategies, to existence results for continuous games where each player has a continuum of strategies.

Wednesday at 3PM
Speaker: Ben Braun
POT 745
Title: A geometric approach to MacMahon's partition analysis
Abstract: In a recent series of papers, George Andrews and his coauthors revived MacMahon's partition analysis as a viable technique for the study of partition identities. We will show how several of their results can be interpreted from the perspective of lattice point enumeration in rational polyhedral cones. This is joint work with Matthias Beck and Nguyen Le.

Title: Signed Graphs and Their Matroids
Speaker: Xiangqian Zhou, Wright State University
Time / Place: 3:00 p.m., POT 745
Abstract: A matrix over Q is totally unimodular if every square submatrix has determinant 0, 1, or -1. Totally unimodular matrices are of fundamental importance in integer linear programming. A precise characterization of such matrices was given by Seymour (1980) in a paper titled ``Decomposition of Regular Matroids.'' Roughly speaking, such matrices are built from the incidence matrices of graphs, their "transposes", and an exceptional matrix by three types of summing operations. A matrix over Q is dyadic if every square submatrix has determinant in {0, \pm 2^i : i \in Z}. Whittle conjectured that a similar decomposition theorem holds for dyadic matrices, where the basic building blocks are the incidence matrices of signed graphs, their "transposes", and a finite number of exceptional matrices. In this talk, we will give a short survey of Seymour's result and show recent progress on Whittle's conjecture by Geelen, Slilaty and Zhou.

WILDCATS Seminar
Monday, March 7, 4PM
CB 346
Speaker: Jason Morton, Penn State
Title: Pfaffian Circuits
Abstract: Pfaffian circuits are a new, simplified construction of Valiant's holographic algorithms. These algorithms provide in general O(n^r) time solutions to certain counting problems, where 1.19
Title: Face Numbers of Cohen-Macaulay Complexes
Speaker: Jonathan Browder, University of Washington
Time / Place: 3:00 p.m., POT 745
Abstract: One of the most fundamental invariants of a simplicial complex is its f-vector, which lists the number of faces the complex has in each dimension. One of the central challenges of geometric combinatorics is that of characterizing the set of f-vectors for interesting classes of complexes. A characterization of the f-vectors of Cohen-Macaulay complexes was given by Stanley; this result was refined to a characterization of the f-vectors of a-balanced Cohen-Macaulay complexes (Bjorner, Frankl, and Stanley) and a later to a characterization of the f-vectors of Cohen-Macaulay subcomplexes of joins of boundaries of simplices (B., Novik). This talk will present a common generalization of these latter two results (B., Novik), and explore some of the tools used.

Title: Spanning trees and the critical group of simplicial complexes
Speaker: Art Duval, University of Texas El Paso
Time / Place: 4:00 p.m., CB 235
Abstract: Building upon the work of Kalai and Adin, we extend the concept of a spanning tree from graphs to simplicial complexes, which are just higher-dimensional analogs of graphs. For any complex satisfying a mild technical condition, we show that its simplicial spanning trees can be enumerated using reduced Laplacian matrices, generalizing the Matrix-Tree Theorem. We use these higher-dimensional spanning trees to extend the concept of a critical group of a graph (related to the sandpile model and the chip-firing game) to simplicial complexes. As in the graphical case, the critical group of a simplicial complex (if its codimension 1 skeleton has a suitably nice spanning tree) can be computed directly from the reduced Laplacian, and its order is given by a weighted count of the spanning trees. This is joint work with Carly Klivans and Jeremy Martin.

DISSERTATION DEFENSE (Final Doctoral Exam)
Title: Combinatorial aspects of excedances and the Frobenius complex
Speaker: Eric Clark
Time / Place: 11:00 a.m., POT 745
Abstract: In this talk, we will first discuss the topology of the Frobenius complex, the order complex of a poset motivated by the classical Frobenius problem. Specifically, we will determine the homotopy type of the Frobenius complex in certain cases using discrete Morse theory. In the second half of the talk, we will extend the classical excedance statistic of the symmetric group to the affine symmetric group and determine the generating function of its distribution. The proof involves enumerating lattice points in a skew version of the root polytope of type A. There will be a reception for Eric at 4:00 p.m. in POT 745.

Title: When does added symmetry shift a rigid crystal to a flexible crystal?
Speaker: Walter Whiteley
Mathematics and Statistics, York University, Toronto
Time / Place: 3:00 p.m., POT 745
Abstract: Motivated by properties of widely used minerals called Zeolites, there has been a rapid development of work towards predicting flexibility or rigidity of periodic structures. Given data bases for possible artificial zeolites, and the observations that functioning zeolites are flexible - there is a strong interest in ways to test a computer model prior to building the crystals in the lab. Several of these recent papers have given necessary (and sometimes sufficient) conditions for periodic generic frameworks to be infinitesimally rigid. Other recent papers have explored when symmetry in a finite framework shifts the framework from rigid to flexible. Building on these two foundations, recent work with Bernd Schulze (TU Berlin) and Elissa Ross (York University) has examined necessary conditions for rigidity of periodic frameworks with added symmetry. Again, there are circumstances, such as inversive symmetry in a crystal, which convert the count for generic rigidity into an orbit count which guarantees flexibility. We will present an overview of these results, with a few animations and tables, as well as the core technique of orbit rigidity matrices. We conclude with an array of unsolved problems. Related papers are on the arXiv.

DISSERTATION DEFENSE
Title: Topological and Combinatorial Properties of Neighborhood and Chessboard
Speaker Matthew Zeckner
Time / Place: 2:00 p.m., POT 03
Abstract: This defense examines the topological properties of simplicial complexes that arise from two distinct combinatorial objects. In 2003, A. Bjorner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SG_{n,k} is homotopy equivalent to a k-sphere. Further, for n=2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the neighborhood complex of SG_{n,k} contains as a deformation retract the boundary complex of a simplicial polytope. Part one of this dissertation provides a positive answer to this question in the case k=2. In this case it is also shown that, after partially subdividing the neighborhood complex, the resulting complex deformation retracts onto a subcomplex arising as a polyhedral boundary sphere that is invariant under the action induced by the automorphism group of SG_{n,2}. Part two of this defense studies simplicial complexes that arise from non-attacking rook placements on a subclass of Ferrers boards that have a_i rows of length i where a_i>0 and i\leq n for some positive integer n. In particular, enumerative properties of their facets, homotopy type, and homology are investigated.