MenuAlgebra and Combinatorics Seminar
Spring 2009
| Date: | January 23, 2009 |
| Time: | 3:00pm |
| Location: | MILN 216 |
| Title: | Organizational Meeting |
| Date: | January 30, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Marcelo Aguiar, TAMU |
| Title: | The Hopf monoid of generalized permutehedra |
| Abstract: | Joyal's notion of species constitutes a good framework for the study of certain algebraic structures associated to combinatorial objects. We briefly review the notion of "Hopf monoid" in the category of species and then illustrate it with several examples. We introduce the Hopf monoid of generalized permutahedra (the latter are certain polytopes recently studied by Postnikov, Reiner and Williams). Our main result is an explicit antipode formula for this Hopf monoid. We explain how reciprocity theorems of Stanley on graphs and of Billera, Jia and Reiner on matroids can be deduced from this result. The talk borrows from joint works with Swapneel Mahajan and with Federico Ardila. Note: this talk may serve as an introduction to the working algebra seminar that will meet on Fridays at 2. |
| Date: | February 6, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | J.M. Landsberg, TAMU |
| Title: | On the geometry of holographic algorithms |
| Abstract: | Many counting problems, such as determining the number of perfect matchings of a planar graph, have algorithms that resolve them "quickly", i.e., in a polynomial number of steps with respect the the input data (e.g. number of edges in the graph). Others can be checked quickly, but there is no known algorithm for solving them quickly, such as counting the number of perfect matchings in an arbitrary graph. Whether or not the lack of a good algorithm for the second class of problems is just due to our ignorance or because no such algorithm exists, is a central, if not the central question in complexity theory. Recently L. Valiant has developed algorithms for quickly solving some such problems, which he calls "holographic algorithms". Jason Morton and I have interpreted some of Valiant's work geometrically, and the range of applicability of our version of Valiant's method hinges on a question in combinatorics that I will present. |
| Date: | February 13, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Aaron Lauve, TAMU |
| Title: | Hopf structures on binary trees (variations on a theme) |
| Abstract: | We discuss several algebraic structures that can be placed on the multiplihedra {Mn}, a family of polytopes defined by Stasheff in the study of higher categories and homotopy theory. The structures we find are best understood by considering the multiplihedra's relationship to two other families of polytopes more familiar to combinatorists: the permutahedra {Pn} and the associahedra {An}. These objects were given the structure of Hopf algebra by Malvenuto-Reutenauer and Loday-Ronco, respectively. In this talk, we give M the structure of P-module and A-Hopf module algebra in a manner respecting the cellular maps from P to M to A. We also give a basis of coinvariants for a second Hopf module structure over A. (This is joint work with F. Sottile and S. Forcey.) |
| Date: | February 19, 2009 |
| Time: | 1:00pm |
| Location: | MILN 317 |
| Speaker: | Sonia Natale, U. Nacional de Córdoba – Argentina |
| Title: | Simple Hopf algebras and finite groups |
| Abstract: | We will discuss the simplicity of some semisimple Hopf algebras arising from finite groups through cocycle deformations. |
| Date: | February 20, 2009 |
| Time: | 1:00pm |
| Location: | MILN 317 |
| Speaker: | Nicolás Andruskiewitsch, U. Nacional de Córdoba – Argentina |
| Title: | On the classification of finite-dimensional pointed Hopf algebras |
| Abstract: | We give an overview of the present state of this problem, illustrated by the main examples coming from the theory of quantum groups. |
| Date: | February 27, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Martin Malandro, Sam Houston State University |
| Title: | Fast Fourier Transforms for Inverse Semigroups |
| Abstract: | The classical fast discrete Fourier transform has found a wealth of applications ranging from seismic analysis to the fast multiplication of large numbers. There is a general theory of Fourier transforms for finite groups, in which the Fourier transform on the cyclic group of order n is the classical Fourier transform. In this talk we will generalize the notion of the Fourier transform to finite inverse semigroups (which are group-like objects that capture local symmetries) and provide a general framework for constructing fast Fourier transforms on these objects. We will also discuss fast Fourier transforms for specific inverse semigroups of interest and potential applications. We will proceed from a representation-theoretic point of view and emphasize the algebra involved in the construction of these algorithms. This talk should be accessible to grad students with an interest in algebra (I will begin by defining the classical discrete Fourier transform, representations, inverse semigroups, etc.) |
| Date: | March 6, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Kyle Petersen, University of Michigan |
| Title: | Promotion and cyclic sieving |
| Abstract: | Let X be a finite set acted upon by a cyclic group C. The cyclic sieving phenomenon (CSP), due to Reiner, Stanton, and White, is the name given to the special situation when there exists a polynomial f that precisely encodes the C-orbit structure of X. (Usually f is a certain q-enumertor for the elements of X.) As a toy example, let X be all 2-subsets of a 4 element set, and let C act by shifting mod 4. There are two orbits: {2,3} → {3,4} → {1,4} → {1,2}, and {1,3} → {2,4}. Now let f = [{4}choose{2}]q = 1 + q + 2q2 + q3 + q4. This is the standard q-analogue of the binomial coefficient: it counts lattice paths in a 2-by-2 box by area. If we plug in powers of 4th roots of unity, that is, powers of i=√-1, we recover the fixed-point set sizes. We get f(i) = 0, f(-1) = 2, f(i3) = 0, f(1) = 6, which tells us there are 2 subsets fixed by two shifts and 6 fixed by four shifts, whereas one or three shifts fix nothing. I will present several examples of the CSP related to Schützenberger's action of jeu de taquin promotion. This can be visualized nicely on rectangular Young tableaux with two or three rows, as shown in joint work with Pylyavskyy and Rhoades. Very recently, in joint work with Serrano, instances of CSPs for certain shifted tableaux and for reduced expressions of the longest element of the hyperoctahedral group have emerged. |
| Date: | March 13, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | John Irving, Saint Mary's University, Nova Scotia |
| Title: | Transitive Factorizations in the Symmetric Group |
| Abstract: | The aim of this talk is to introduce the audience to the combinatorics of "transitive factorizations" of permutations. A transitive factorization is a decomposition of a given permutation into an ordered product of others, where the factors act transitively on the underlying set of symbols. The special case in which the factors are transpositions dates back to Hurwitz, who recognized that this can serve as a combinatorial model for certain branched coverings of Riemann surfaces. Much has been learned since then, but despite many glimpses at beautiful combinatorial structure, still surprisingly little is known about the nature of these factorizations. We will survey various enumerative problems in this area, beginning with Hurwitz's original problem and moving towards recent related work on "star factorizations". |
| Date: | March 27, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Kia Dalili, University of Missouri |
| Title: | Asymptotic behavior of value semi-groups |
| Abstract: | Let ν be a valuation dominating a noetherian local domain, and let S = {ν(r) | r ∈ R} be its value semi-group and Γ = S – S its value group. The possible value groups Γ have been extensively studied and classified classically, the value semi-group S however is much less understood. In this talk we will briefly look at the known results classifying value groups and some well known constraints on the value semi-groups then we will look at growth rate of the value semi-group and its asymptotic behavior to obtain new constraints on possible value semi-groups. This is joint work with S.D. Cutkosky and O. Kashcheyeva. |
| Date: | March 30, 2009 |
| Time: | 2:00pm |
| Location: | MILN 216 |
| Speaker: | Bill Schmitt, George Washington University |
| Title: | The free splice of matroids |
| Abstract: | Given matroids M(A) and N(B) such that the restrictions M|(A ∩ B) and N|(A ∩ B) are equal, an amalgam of M and N is a matroid L on A ∪ B such that L|A = M and L|B = N. Amalgams might not exist, and even when they do, there might be no freest amalgam. In this talk we consider the "twisted" version of this situation, in which the restriction N|(A ∩ B) is equal to the contraction M/(A – B). In this case we define a splice of M and N to be a matroid L on A ∪ B such that L|A = M and L/(A – B) = N. In contrast to the situation for amalgams, it turns out splices always exist and, furthermore, there is a freest splice, which we call the free splice of M and N. (In the case of disjoint A and B, the free splice is the free product, introduced by Henry Crapo and William Schmitt in 2005.) We show how to construct the free splice, as a certain Higg's lift, and give cryptomorphic descriptions of it, in terms of bases, independent set, rank function, flats and cyclic flats. We show that minors of free splices are free splices of higgs lifts of corresponding minors, and we characterize, in terms of cyclic flats, matroids that are irreducible with respect to free splice. We describe the associativity properties of free splice and examine its interaction with some other matroid operations. This is joint work with Joe Bonin. |
| Date: | April 3, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Svetlana Poznanovik, TAMU |
| Title: | Major index for 01-fillings of moon polyominoes |
| Abstract: | It is a classical result by MacMahon that the inversion number and the major index have the same distribution over the set of rearrangements of a fixed multiset. Recently, a major index was defined for matchings and set partitions and it was shown that it has the same distribution with the number of crossings. I will present a definition of a major index for fillings of moon polyominoes with zeros and ones. This statistic, when specialized to certain shapes, reduces to the major index for words and set partitions. Moreover, I will show that it is equally distributed with the number of north-east chains, which are a natural generalization of inversions and crossings. |
| Date: | April 10, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Philip Matchett Wood , Rutgers University |
| Title: | On the probability that a discrete complex random matrix is singular |
| Abstract: | Consider a square matrix with n rows and n columns, where each entry is filled in independently at random +1 or -1, each with probability 1/2. What is the probability that this matrix is singular, as a function of n as n becomes large? Matrices with +/-1 entries serve as a test case for studying discrete random matrices, as opposed to continuous random matrices. Discrete random matrices often appear in practice, for example, when studying a large matrix computation with a computer, since the representation in the computer of the matrix (and any noise) is inherently discrete. The first exponential upper bound on the probability that a +/-1 random matrix is singular was proved by Jeff Kahn, Janos Komlos, and Endre Szemeredi in 1995, and Terence Tao and Van Vu made a another breakthrough in 2006 by using a structural result from additive combinatorics. This talk will discuss a recent improvement on the approach of Tao and Vu that leads to the best know upper bounds on the probability that such a matrix is singular. We will also discuss generalizations to other types of discrete random matrices and mention connections with other problems involving random matrices. Joint work with Jean Bourgain and Van Vu. |
| Date: | April 17, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Daniel Redelmeier, TAMU |
| Title: | Hyperpfaffians and their applications to combinatorics |
| Abstract: | In this talk we will discuss the hyperpfaffian, which is an extension of the pfaffian to either multidimensional arrays or tensor algebras. We will spend the first part of the talk examining the different definitionsused for the hyperpfaffian, as there are several non-equivalent forms. Then we will examine uses of the hyperpfaffian in combinatorics. The first is the Hyperpfaffian-Cactus theorem, which is related to the classical matrix-tree theorem and the later pfaffian-tree theorem. Second we will look at hyperpfaffian orientations, which can be used to count perfect matchings on a hyperpfaffian. Finally we will look at hyperpfaffian rings/ideals, and specifically look at the fact that unlike the pfaffian ideal, the hyperpfaffian ideal is not an algebra with straightening law under reasonable assumptions. |
| Date: | April 21, 2009 |
| Time: | 1:00pm |
| Location: | MILN 317 |
| Speaker: | Igor Pak, University of Minnesota |
| Title: | MacMahon's master theorem and its generalizations |
| Abstract: | MacMahon's Master Theorem is a classical combinatorial result celebrated by its applications to binomial identities. In this talk I will present an algebraic and a direct bijective proof of the theorem. I will then discuss various non-commutative generalizations and how they fit together. |
| Date: | April 24, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Fernando Rodriguez Villegas, University of Texas |
| Title: | Rational and Algebraic Hypergeometric Functions |
| Abstract: | In the late 80's Beukers and Heckmann classified all algebraic hypergeometric functions in one variable. The key ingredient in their proof is the signature of a quadratic form fixed by the monodromy group. I will explain how this quadratic form is related to an old construction due to Bezout and how we may reformulate their result in terms of the p-adic valuation of Taylor coefficients. Using this, in joint work with E. Cattani and A. Dickenstein, we were able to classify rational two-variable hypergeometric functions. |
| Date: | May 1, 2009 |
| Time: | 3:00pm |
| Location: | MILN 317 |
| Speaker: | Joerg Feldvoss, University of South Alabama |
| Title: | Complexity, Varieties, and Representation Type |
| Abstract: | In this talk I will define the complexity of a finite-dimensional module over an associative algebra and explain that for certain algebras over an algebraically closed ground field the complexity can be realized as the dimension of an affine variety. I will present several applications of these concepts which were introduced originally for modular representations of finite groups by Alperin and Carlson in the late seventies and early eighties. Then I will define the representation type of an associative algebra and state the trichotomy theorem of Drozd. If time permits, I will conclude by explaining how to use the affine varieties to prove a wildness criterion for certain self-injective algebras. This is joint work with Sarah Witherspoon. |
