Home | People | Seminar | Conferences | Resources

# Algebra and Combinatorics Seminar

### Mondays, Milner 317     3:00-3:50 PM

Cayley Graph of the Free Product Z3 * Z5
The Algebra and Combinatorics seminar is devoted to studying algebra, combinatorics, their interconnection, and their relations to mathematics and applications. The seminar's organizer is Chris Hillar.

 This Week's Seminar / Colloquium December 6 Eugene Mukhin, UIPUI (Note: This is a Thursday and at 2PM) 2:00-3:00 Schubert Calculus and Gaudin model Abstract: It is well known that the dimension of the algebra $O$ of functions on the intersection of Schubert varieties in a Grassmanian of N-dimensional planes is equal to the dimension of a space $V$ of singular vectors of a suitable weight in a suitable product of irreducible gl(N)-modulues. It is also well known that the space $V$ is the space of states of the quantum Gaudin model and the algebra $B$ of observables of the Gaudin model (the Bethe algebra) acts in $V$. We construct a natural algebra isomorphism from $O$ to $B$ and show that $V$ as an $O$-module is isomorphic to $O*$. This result allows us to prove a number of long-standing conjectures in both Schubert calculus and Gaudin model. In particular, we show that the spectrum of the Gaudin model is simple for all values of the parameters of the model and that the corresponding Schubert varieties intersecttransversally for all real values of the parameters.

### History of previous Alg/Comb seminars.

 September 3 Harm Derksen, U. of Michigan Mutations of quivers September 10 Chris Hillar, TAMU Solving word equations in terms of radicals: Towards a noncommutative Abel theorem September 17 Aaron Lauve, TAMU Noncommutative invariants and coinvariants of the symmetric group September 24 Maria Belk, TAMU Problems related to the Kneser-Poulsen conjecture October 1 Felipe Voloch, UT Austin Elements of high order in finite fields October 8 Lionel Levine, UC Berkeley Chip-Firing and Rotor-Routing on Trees October 12 (!!) Jesus de Loera, U.C. Davis (Note: Friday talk) Recent Progress on Computing Volumes of Polytopes October 22 --No Seminar-- October 29 Zach Teitler, TAMU Huebl's "Powers of elements and monomial ideals" November 2 (!!) Charles R. Johnson, College of William & Mary (Note: Friday talk) Eigenvalues, Multiplicities and Graphs November 5 Salah A. Aly, TAMU Algebraic Constructions of Quantum LDPC Codes Derived from Combinatorial Objects and Finite Geometry November 12 Frank Sottile, TAMU A Littlewood-Richardson rule for Grassmannian Permutations November 16 (!!) Lauren Williams, Harvard (Note: Friday talk) Toric geometry and the non-negative part of G/P November 26 Sarah Witherspoon, TAMU When is cohomology finitely generated? December 3 Aaron Lauve, TAMU Towards an explicit basis for a "Catalan dimensional" vector space December 6 Eugene Mukhin, UIPUI (Thursday!!) Schubert Calculus and Gaudin model

Abstracts
September 3
Harm Derksen, U. Michigan
Mutations of quivers

Abstract:
.
TOP

September 10
Chris Hillar, TAMU
Solving word equations in terms of radicals:
Towards a noncommutative Abel theorem

Abstract:
Let G be a uniquely divisible group (UD-group); that is, in G, the
equation g^n = h has a unique solution g given any h and any integer n.
We study the problem of characterizing those word equations W(a,x) = b
which have solutions in terms of radicals. For instance, the equation xax = b
has the solution

x = a^(-1/2) [a^(1/2)ba^(1/2)]^1/2 a^(-1/2),

which can be verified by "plugging" it into the original equation. We describe
what we believe to be the answer to this problem, and outline some of the ideas
in our program (which we hope to complete soon).

Motivation (e.g. the BMV trace conjecture from statistical mechanics) and
several examples will also be discussed. Moreover, the talk should be
accessible to a wide audience. (Based on joint work with Lionel Levine).
TOP
September 17
Aaron Lauve, TAMU
Noncommutative invariants and coinvariants of the symmetric group

Abstract:
The algebras NCSym_n and Sym_n (n>0) are defined to be the
S_n invariants inside Q<X> (resp. Q[X]), the noncommutative
(resp. commutative) polynomial functions on an alphabet X of
cardinality n. The abelianization map Q<X> \mapsto Q[X] realizes
Sym_n as a quotient of NCSym_n. Here, we view it as a subspace. Some
surprising identities on the ordinary generating function for the Bell
numbers appear as an immediate corollary. In case n = \infty, we obtain
new information on the Hopf algebraic structure of NCSym_n.
Time permitting, we outline similar results for Hivert's r-QSym_n algebras
(r,n>0) and their noncommutative analogues.
(Joint work with F. Bergeron)
TOP
September 24
Maria Belk, TAMU
Problems related to the Kneser-Poulsen conjecture

Abstract:
Consider a collection of overlapping balls in Euclidean space. If we change
the positions of the balls, then the volume of the union may change. In the
1950's, Kneser and Poulsen conjectured that if the distances between the
centers do not decrease, then the volume of the union must increase or remain
the same. In 2002, Bezdek and Connelly proved this conjecture for discs on the
Euclidean plane. The conjecture remains open for higher dimensional Euclidean
spaces, as well as for spherical and hyperbolic spaces. In this talk, we will
examine the difficulties involved in extending the proof to these other
settings.
TOP
October 1
Felipe Voloch, UT Austin
Elements of high order in finite fields

Abstract:
We discuss the problem of constructing elements of
high order in finite fields of large degree over their prime field.
We prove that for points on a plane curve, one of the coordinates
has to have high order. We also discuss a conjecture of Poonen for
subvarieties of semiabelian varieties for which our result is a
weak special case.
TOP
October 8
Lionel Levine, UC Berkeley
Chip-Firing and Rotor-Routing on Trees

Abstract:
The sandpile group of a graph G is an abelian group whose order is the number
of spanning trees of G. I will show how to find the decomposition of the sandpile group into
cyclic subgroups when G is a regular tree with the leaves are collapsed to a single vertex. This
result can be used to understand the behavior of the rotor-router model, a deterministic analogue
of random walk studied first by physicists and recently rediscovered by combinatorialists. Several
years ago, Jim Propp simulated a simple process called rotor-router aggregation and found that it
produces a near perfect disk in the integer lattice Z^2. While we can prove that the shape is close
to circular, the theoretical bounds do not match the near perfect circularity seen in simulations. In
the regular tree, on the other hand, I will show how to use the sandpile group to prove that rotor-router
aggregation yields a perfect ball. Joint work with Itamar Landau and Yuval Peres.
TOP
October 12 (Note: Friday talk)
Jesus de Loera, U.C. Davis
Recent Progress on Computing Volumes of Polytopes

Abstract:
Computing the volume of an object is among the most fundamental and basic
operations in geometry. Volume computation has been investigated by several
authors from the algorithmic point of view. While there are a few cases for
which the volume can be computed efficiently (e.g., for convex polytopes in
fixed dimension), it has been proved that computing the volume of polytopes of
varying dimension is "hard" in the sense of complexity. In this talk we
survey why volume computation is relevant in everyone's life, what is currently
know about it, and describe two new results regarding two families of polytopes
well-known to combinatorialists. First, we talk about the first explicit
combinatorial formula for the volume of the polytope of n x n
doubly-stochastic matrices, also known as the Birkhoff polytope. Second, we
show that the famous matroid polytopes (which appear in tropical geometry and
optimization among other places) are in fact tractable polytopes when the rank
of the matroid is assumed to be fixed.

Based on two joint papers (1) with F. Liu and R. Yoshida and (2) D. Haws and M. Koeppe.
TOP
October 22
--No Seminar--

Abstract:
.
TOP

October 29
Zach Teitler, TAMU
Huebl's "Powers of elements and monomial ideals"

Abstract:
I will present work of Reinhold Huebl that appeared in Comm. Alg. in
2005 as "Powers of elements and monomial ideals". An ideal $I$ in a
local ring $(R,m)$ is said to have property NN if $f \in I$, $f^n \in I^{n+1}$ for some $n$ implies $f \in mI$. It is an open question whether
in regular local rings all radical ideals have this property. This
question was studied by Eisenbud and Mazur, among others, in connection
with the proof of Fermat's Last Theorem. In this paper Huebl
characterizes monomial ideals with property NN, in terms of the Newton
polyhedron.
TOP
November 2
Charles R. Johnson, College of William & Mary
Eigenvalues, Multiplicities and Graphs

Abstract: Given an undirected graph G on n vertices, consider the set S(G) of all n-by-n symmetric
matrices with graph G. The diagonal entries of A in S(G) are free (zero or nonzero), except that they
are real. For each A in S(G), there is a list of multiplicities for the eigenvalues of A. We are interested
in the multiplicity lists that occur among matrices in S(G). This has been an area of active research for
a dozen years.

The talk will focus primarily upon trees and will survey known results, including an important structural
result, dating back to the early 60's, beginning with an observation of Parter. These include a combinatorial
characterization of the maximum multiplicity, bounds on the minimum number of distinct eigenvalues and
characterizations of the possible multiplicities for certain classes of trees. We will mention some
outstanding problems at the end.
TOP

November 5
Salah A. Aly, TAMU
Algebraic Constructions of Quantum LDPC Codes Derived from
Combinatorial Objects and Finite Geometry

Abstract: Quantum information is sensitive to noise and needs error correction and recovery
strategies. Quantum error control codes are designed to protect quantum information. In this
talk I construct a class of classical regular Low Density Parity Check (LDPC) codes derived
from combinatorial objects and Latin squares. The parity check matrices of these codes are
constructed by permuting orthogonal Latin squares of order $n$ in block-rows and block-columns.
I show that the constructed LDPC codes are self-orthogonal and their minimum and stopping
distances are bounded. This helps us to construct a family of quantum LDPC codes.I will assume
no prior knowledge of quantum or LDPC codes.
TOP

November 12
Frank Sottile, TAMU
A Littlewood-Richardson rule for Grassmannian Schubert problems

Abstract: The motivating and as yet unsolved question in the modern Schubert
calculus is to give a combinatorial formula for the product of
Schubert classes in the cohomology ring of a flag manifold.
In this talk, I will describe a solution to this problem for a
special, but important class of products.
These are products of Schubert classes pulled back from Grassmannian projections,
and our formula is for the coefficient of the class of a point in such a product.
This rule is joint work with Kevin Purbhoo.
Our rule shows that this intersection number is the number of
certain combinatorial objects we call filtered tableaux,
which are sequences of skew Littlewood-Richardson tableaux
that together fill a shifted shape.
TOP

November 16 (Note: Friday talk)
Lauren Williams, Harvard
Toric geometry and the non-negative part of G/P

Abstract: First I will discuss joint work with Alex Postnikov and David Speyer (arXiv:0706.2501)
in which we use toric geometry to investigate the topology of the totally non-negative part of the
Grassmannian G(k,n)+. G(k,n)+ is a cell complex whose cells C_G can be parameterized in terms
of the combinatorics of certain planar graphs G. To each cell C_G we associate a certain polytope
P(G), which turns out to be a face of a Birkhoff polytope: the face lattice of P(G) can be described
in terms of matchings and unions of matchings of G. We also demonstrate a connection between
the polytopes P(G) and matroid polytopes. We then associate a toric variety to each P(G), and use
our technology to prove that the cell decomposition of G(k,n)+ is in fact a CW complex. A
combinatorial result I proved 2 years ago then implies that the closure of each cell is contractible;
in particular, G(k,n)+ is contractible.

If time permits, I will briefly describe very recent joint work with Konstanze Rietsch in which we
extend the previous work to show that the Lusztig-Rietsch cell decomposition of the totally non-negative
part of any G/P is a CW complex. In the proof, the combinatorics of planar graphs is replaced by
the technology of Lusztig's canonical basis.
TOP

November 26
Sarah Witherspoon, TAMU
When is cohomology finitely generated?

Abstract: The cohomology rings of many types of finite dimensional algebras are finitely
generated (possibly modulo nilpotent elements). Finite generation opens the door to geometric
study of modules. We will survey what is known for finite dimensional Hopf algebras in particular,
including some preliminary new results.

No knowledge of cohomology will be assumed. Any cohomology or rings making an appearance
will be defined or at least described during the talk. (Joint work with
Mitja Mastnak, Julia Pevtsova, and Peter Schauenburg).
TOP

December 3
Aaron Lauve, TAMU
Towards an explicit basis for a "Catalan dimensional" vector space

Abstract:
This talk is an overview of work in progress with Sarah Mason.

We describe a family of differential operators {E(a)} acting on the polynomial ring
R=Q[x1,..,xN,y1,..,yN] in two sets of indeterminants. Inside R sits the determinant
D of the Vandermonde matrix V(y1,...,yN).We are concerned with the subspace H
generated by the E_a's and D. The space H is a piece of the so-called "diagonal
harmonics" studied by F. Bergeron, A. Garsia, M. Haiman and others.

* Surprisingly, H=H(N) has dimension the Nth Catalan number.

* More surprisingly, this inoccuous fact does not have an elementary combinatorial
proof---instead Haiman resorts to an argument on the Hilbert scheme of N points in the plane.

* Most surprisingly, this inoccuous fact was a key step towards a major modern result
in combinatorial representation theory: Haiman's proof of the N! conjecture
(and I.G. Macdonald's positivity conjecture).

In light of the "most" surprising fact above, Sarah and I feel it would be appropriate
to eliminate the "more" surprising fact. My plan is to share our progress towards
exhibiting a combinatorial basis for H. Before doing so, I should first: describe the
problem in complete, combinatorial detail; outline our plan of attack; and explain
why we think we may succeed where Bergeron-Garsia-Haiman failed.

TOP
December 10

Home | People | Seminar | Conferences | Resources