Friday, September 4, 2009 at 4:00 PM in SAS 4201
Christine Heitsch, Georgia Tech
RNA Configurations and Noncrossing Partitions
Under a suitable abstraction, complex biological problems can reveal surprising mathematical structure. We illustrate this phenomena with results motivated by the folding of RNA sequences. Transitioning between RNA configurations by an appropriate local move, we obtain an isomorphism with the lattice of noncrossing partitions. This leads to results counting orbits under the Kreweras complementation map and a new graphical approach to meander enumeration.
Thursday, September 10, 2009 at 4:00 PM in SAS 4201
Cliff Smyth, UNC-Greensboro
Non-crossing pairings
Let P be a polygon with 2n vertices. A pairing of P is a set of chords so that each vertex is contained in exactly one chord. A pairing is non-crossing if no two of its chords cross (i.e. intersect). Let C be a coloring of P, i.e. a partition of the vertices of P into two color classes. We say that P is compatible with C iff none of its chords has both endpoints in just one color class of C.
Let f(C) be the number of non-crossing pairings compatible with C. These numbers arise as the moments of the circular operator, an object of importance in free probability. They also appear in a number of other combinatorial problems involving trees, paths, tilings, etc.
We'll discuss some interesting polynomial formulas for f on "balanced colorings" and some conjectures on maximizing and minimizing f, subject to fixing the number of "runs" of the coloring.
Friday, September 18, 2009 at 4:00 PM in SAS 4201
Camilla Smith, Sweet Briar College
Enumeration of the distinct shuffles of permutations
A shuffle of two words is a word obtained by concatenating the two original words in either order and then sliding any letters from the second word back past letters of the fi rst word, in such a way that the letters of each original word remain spelled out in their original relative order. Examples of shuffles of the words 1234 and 5678 are, for instance, 15236784 and 51236748. In this talk, I enumerate the distinct shuffles of two permutations of any two lengths, where the permutations are written as words in the letters 1,2,3,...,m and 1,2,3,...,n, respectively.
Friday, September 25, 2009 at 4:00 PM in SAS 4201
Sonja Mapes, Duke
Cellular resolutions of monomial ideals and LCM lattices
In the study of cellular resolutions of monomial ideals it is often useful to consider the LCM lattice of the given monomial ideal. In particular, it is known that all ideals with isomorphic LCM lattices have isomorphic minimal resolutions. In this talk I will give the necessary background on free resolutions of monomial ideals and then discuss how studying the parameter space of LCM lattices provides one with new insights into the structure of these resolutions.
Friday, October 2, 2009 at 4:00 PM in SAS 4201
Sami Assaf, MIT
Affine dual equivalence
The k-Schur functions were first introduced by Lapointe, Lascoux and Morse in the hopes of refining the expansion of Macdonald polynomials into Schur functions. Recently, an alternative definition for k-Schur functions was given by Lam, Lapointe, Morse, and Shimozono as the weighted generating function of starred strong tableaux. This definition has been shown to correspond to the Schubert basis for the affine Grassmannian and at t=1 it is equivalent to the k-tableaux characterization of Lapointe and Morse. Using this new definition for k-Schur functions, we prove the symmetry and Schur positivity of k-Schur functions combinatorially using the theory of dual equivalence graphs. Central to our proof is our discovery of an analog of dual equivalence for the affine symmetric group. We also make connections between k-Schur functions and both LLT and Macdonald polynomials by comparing the graphs for these functions.Friday, October 16, 2009 at 4:00 PM in SAS 4201
Gabor Hetyei, UNC-Charlotte
The topology of the poset of bipartitions
Bipartitional relations were introduced by Foata and Zeilberger, who showed these are precisely the relations which give rise to equidistribution of the associated inversion statistic and major index. In this talk we consider the natural partial order on bipartitional relations given by inclusion, and explore the topology of its order complex. We will see that bipartitional relations on a set of size $n$ form a graded lattice of rank $3n-2$. The order complex of this lattice is homotopy equivalent to a sphere of dimension $n-2$. Each proper interval in this lattice has either a contractible order complex, or it is isomorphic to the direct product of Boolean lattices and smaller lattices of bipartitional relations. The main tool in the proofs of these results is discrete Morse theory as developed by Forman, and an application of this theory to order complexes of graded posets, designed by Babson and Hersh.
This is joint work with Christian Krattenthaler.Friday, October 23, 2009 at 4:00 PM in SAS 4201
Mathias Drton, University of Chicago
A Geometric Interpretation of the Characteristic Polynomial of Reflection Arrangements
We consider projections of points onto fundamental chambers of finite real reflection groups. Our main result shows that for groups of type $A_n$, $B_n$, and $D_n$, the coefficients of the characteristic polynomial of the reflection arrangement are proportional to the spherical volumes of the sets of points that are projected onto faces of a given dimension. We also provide strong evidence that the same connection holds for the exceptional, and thus all, reflection groups. These results naturally extend those of De Concini and Procesi, Stembridge, and Denham which establish the relationship for 0-dimensional projections. This work is also of interest for the field of order-restricted statistical inference, where projections of random points play an important role.Friday, October 30, 2009 at 4:00 PM in SAS 4201
Gabor Pataki, UNC Chapel Hill
Basis Reduction, and the Complexity of Branch-and-Bound
The classical branch-and-bound algorithm for the integer feasibility problem is considered inefficient: it may take an exponential number of nodes to prove the infeasibility of a simple integer program. Theoretically efficient algorithms, such as Lenstra's and Kannan's algorithms, and the generalized basis reduction method of Lovasz and Scarf use advanced techniques. The first two of these need to round the polyhedron (i.e. apply a transformation to it to make it look "more spherical); and the last solves a sequence of linear programs to find a direction in which the polyhedron is "thin".
Here we show that branch-and-bound is theoretically efficient, if we apply a unimodular transformation to the constraint matrix to make its columns short, and near orthogonal, i.e. a reduced basis of the generated lattice. The main result is that if the coefficients of the problem are from {1, ..., M} for a large enough M, then for almost all instances the number of subproblems that must be enumerated by branch-and-bound is just {em one}. Besides giving an analysis of branch-and-bound, the solvability result generalizes work of Furst and Kannan on the solvability of subset sum problems.
Joint work with Mustafa Tural at UNC Chapel Hill (now at Telcordia Laboratories).
Friday, November 6, 2009 at 4:00 PM in SAS 4201
Nieves Castro-Gonzalez, Polytechnic University of Madrid
Additive results for the genrealized Drazin inverse and some applications to block matrices
The generalized Drazin inverse appears in numerous applications that include areas such as linear estimation, differential and difference equations, Markov chains and control theory. We present in this talk additive properties for the g-Drazin inverse in a complex Banach algebra. The auxiliary result used in our development involves an expression for the resolvent of a matrix with entries in a Banach algebra. We will comment on the application of the Drazin inverse of a 2x2 complex block matrix in terms of the individual blocks and the generalized Schur complement.Friday, November 13, 2009 at 4:00 PM in SAS 4201
Bojko Bakalov, NC State
W-constraints for simple singularities
Simple singularities are classified by Dynkin diagrams of type ADE. Using Picard-Lefschetz periods, we construct a twisted representation of the lattice vertex algebra V associated to the root lattice of the corresponding finite-dimensional Lie algebra g. By the Frenkel-Kac construction, V is isomorphic to the basic representation of the corresponding affine Kac-Moody algebra, and in particular it admits an action of g by derivations. The kernel of this g-action is a subalgebra of V known as a W algebra. Our main result is that the total descendant potential of the singularity, introduced by Givental, is a highest weight vector for the W algebra. This is joint work with T. Milanov.Friday, November 20, 2009 at 4:00 PM in SAS 4201
Ruth Haas, Smith College
Combinatorics of Involutions and Twisted Involutions in Coxeter GroupsFriday, January 22, 2010 at 4:00 PM in SAS 4201
Alessandro D'Andrea, University of Rome "La Sapienza"
TBAFriday, January 29, 2010 at 4:00 PM in SAS 4201
Rinat KedemTBASaturday, February 6, 2010 at 10:00 AM in TBA
Carla Savage, Bernd Sturmfels, Ed Swartz, Laszlo Szekely, Various Universities
Triangle Lectures in CombinatoricsFriday, February 26, 2010 at 4:00 PM in SAS 4201
Robert Proctor, UNC Chapel Hill
TBAFriday, March 5, 2010 at 4:00 PM in SAS 4201
Antun Milas, University at Albany
TBAFriday, March 12, 2010 at 4:00 PM in SAS 4201
Dijana Jakelic, UNC Wilmington
Finite-dimensional representations of quantum affine algebras at roots of unity
You can add or remove yourself from a seminar mailing list by visiting this link.
Seminar Organizers: Bojko Bakalov and Patricia Hersh