Student Discrete Math Seminar

Please join us Thursdays from 1:10-2:00 in MSB 2112 for the Student Discrete Math Seminar. Although we don't have pizza, the talks are always interesting. Anyone who wants to attend regularly (missing no more than 3 talks) can sign up for a unit (CRN: 69654). If you would like to speak, you can register for 3 units. Talk to Steve Pon or Matt Stamps if you have any questions or would like to speak at the seminar.

Topic Ideas

The most commonly asked question, especially for new graduate students, is: "I would like to speak, but I don't know what to talk about! What can I give a talk on?" Below we have some suggestions. Disclaimers: This list does not in any way attempt to cover all of Discrete Mathematics, but instead focuses on research areas that are more related to UC Davis specialties. In fact, the list does not even exhaust all of the topics that UC Davis does specialize in, but only what we happened to think of at the time. You are encouraged to seek out other topics and papers. Although there has been an attempt to organize and categorize, many papers and books belong in several categories, so take it all with several grains of salt.

The list is a work in progress - check back often for updates.

Quantum Groups and Representation Theory, Crystals

RSK and related algorithms

Finally, perhaps your best resource:

• Steven Pon, spon@math.ucdavis.edu
• Matthew Stamps,
• Eddie Kim,

The following is an old listing of topics. We'll leave it up until we finish the new, more organized list.

• the Edelmann-Greene paper on what we now call Edelmann-Greene insertion (actually maybe some of what i'm (Alex Woo) thinking about is actually in the Billey-Jockhush-Stanley paper),
• the Billey-Warrington paper on 321-hexagon-avoiding permutations. Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations; http://arxiv.org/abs/math.CO/0005052
• There is an extensive list of papers at the lower part of the webpage http://www.math.ucdavis.edu/~vazirani/S05/KL.details.html
• other interesting papers might be Sarah Mason's recent work on a different RSK type algorithm related to nonsymmetric Schur functions. Or some papers on Key polynomials.
• Kevin Purbhoo's paper on root games
• Almost any section of Macdonald's book. You might also look at Fulton's book or Jim Haglund's new book. There are several papers on crystal graphs I can also suggest (for instance, in connection to the Littlewood-Richardson rule).
  Below are listed several papers related to the saturation conjecture/theorem. (In a slightly weird format from cutting/pasting from a bibtex file.) In particular there are several papers involving polytopes, honeycombs, Littelmann paths, galleries, and buildings.
   
• Arkady Berenstein, Andrei Zelevinsky "Tensor product multiplicities, canonical bases and totally positive varieties"
• math.RT/9912012  ( Invent. Math.  143  (2001),  no. 1, 77--128.)      
      [We obtain a family of explicit "polyhedral" combinatorial expressions for multiplicities in the tensor product of two simple finite-dimensional modules over a complex semisimple Lie algebra.  Our answers use a new combinatorial concept of $\ii$-trails which resemble Littelmann's paths but seem to be more tractable.  A remarkable observation by G. Lusztig notes that combinatorics of the canonical basis is closely related to geometry of the totally positive varieties. We formulate this relationship in terms of two mutually inverse transformations:  "tropicalization" and "geometric lifting."]
• Anders S. Buch  "The saturation conjecture (after A. Knutson and T. Tao)"
  math.CO/9810180 (With an appendix by William Fulton. Enseign. Math. (2) 46 (2000), no. 1-2, 43--60. ) [A nice exposition of the hive model and Knutson-Tao's proof of the saturation conjecture (in type A).]
• Joel Kamnitzer  "Mirkovic-Vilonen cycles and polytopes"
  math.AG/0501365        [We give an explicit description of the Mirkovic-Vilonen cycles on the affine Grassmannian for arbitrary complex reductive groups. We also give a combinatorial characterization of the MV polytopes. We prove that a polytope is an MV polytope if and only if it a lattice polytope whose defining
  hyperplanes are parallel to those of the Weyl polytopes and whose 2-faces are rank 2 MV polytopes. As an application, we give a bijection between Lusztig's canonical basis and the set of MV polytopes.]
• M. Kapovich. "Generalized triangle inequalities and their applications", - Madrid, August 22-30, 2006. Eds. Marta Sanz-Solé, Javier Soria, Juan L. Varona, Joan Verdera. Vol. 2, p. 719-742.         [survey article. applications to decomposing tensor products of irreducible representations and the saturation theorem in types beyond A.]
  
• Allen Knutson, Terence Tao  "The honeycomb model of GL(n) tensor products I: proof of the saturation conjecture" math.RT/9807160  ( J. Amer. Math. Soc.  12  (1999),  no. 4, 1055--1090. )
          [We introduce the honeycomb model of BZ polytopes, which calculate Littlewood-Richardson coefficients, the tensor product rule for GL(n).  A particularly well-behaved honeycomb is necessarily integral, which proves the "saturation conjecture", extending results of Klyachko to give a complete answer to which L-R coefficients are positive. This in turn has as a  consequence Horn's conjecture from 1962 characterizing the spectrum of the sum of two Hermitian matrices.  ] 
• Sophie Morier-Genoud's thesis: "Relevement Geometrique de L'involution de Schutzenberger et Applications"         [in French]?  
• Arun Ram  "Alcove walks, Hecke algebras, spherical functions, crystals and column strict tableaux" math.RT/0601343  (Pure and Applied Mathematics Quarterly. Special Issue: In honor of Robert MacPherson.  Vol 2. (2006) 135-183.)         [This paper makes precise the close connection between the affine Hecke algebra, the path model, and the theory of crystals. Section 2 is a basic pictorial exposition of Weyl groups and affine Weyl groups and Section 5 is an exposition of the theory of (a) symmetric functions, (b) crystals and (c) the path model. Sections 3 and 4 give an exposition of the affine Hecke algebra and recent results regarding the combinatorics of spherical functions on p-adic groups (Hall-Littlewood polynomials). The $q$-analogue of the theory of crystals developed in Section 4 specializes to the path model version of the ``classical'' crystal theory. The connection to the affine Hecke algebra and the approach to spherical functions for a $p$-adic group in Nelsen-Ram was made concrete by C. Schwer who told me that ``the periodic Hecke module
  encodes the positively folded galleries'' of Gaussent-Littelmann. This paper is a further development of this point of view.]
• Guy Rousseau :  "Euclidean buildings" Lecture notes from Summer School 2004: Non-positively curved geometries, discrete groups and rigidities http://www-fourier.ujf-grenoble.fr/ECOLETE/ecole2004/Rousseau.pdf
          [Introduction to buildings.  All basic definitions can be found here.]  
• Arkady Berenstein, David Kazhdan
  Lecture notes on Geometric Crystals and their combinatorial analogues
  math.QA/0610567
   
• A path model for geodesics in Euclidean buildings and its applications to representation theory, Michael Kapovich and John J. Millson, arXiv:math.RT/0411182
• {Gaussent, S. and Littelmann, P.}, {L{S} galleries, the path model, and {MV} cycles}, {Duke Math. J.}, {Duke Mathematical Journal}, VOLUME {127}, YEAR {2005}, PAGES {35--88},
• {Littelmann, Peter}, {The path model for representations of symmetrizable {K}ac-{M}oody algebras}, BOOKTITLE = {Proceedings of the International Congress of Mathematicians, Vol.\ 1, 2 (Z\"urich, 1994)}, PAGES = {298--308}, PUBLISHER = {Birkh\"auser}, YEAR = {1995},
• {Littelmann, Peter}, {Paths and root operators in representation theory}, {Ann. of Math. (2)}, VOLUME = {142}, YEAR = {1995}, PAGES = {499--525},
• {Berenstein, Arkady and Zelevinsky, Andrei}, {Canonical bases for the quantum group of type {$A\sb r$} and piecewise-linear combinatorics}, {Duke Math. J.}, VOLUME = {82}, YEAR = {1996}, PAGES = {473--502},
• {Berenstein, A. D. and Zelevinsky, A. V.}, {Tensor product multiplicities and convex polytopes in partition space}, {J. Geom. Phys.}, VOLUME = {5}, YEAR = {1988}, PAGES = {453--472},
• Galleries, Hall-Littlewood polynomials and structure constants of the spherical Hecke algebra, {Christoph Schwer}, {arXiv:math.CO/0506287}
• {De Loera, Jes{\'u}s A. and McAllister, Tyrrell B.}, {Vertices of {G}elfand-{T}setlin polytopes}, {Discrete Comput. Geom.}, VOLUME = {32}, YEAR = {2004}, PAGES = {459--470},
• Knutson, Allen and Tao, Terence and Woodward, Christopher, A positive proof of the {L}ittlewood-{R}ichardson rule using the octahedron recurrence, {Electron. J. Combin.}, VOLUME = {11}, YEAR = {2004},
• Knutson, Allen and Tao, Terence, {The honeycomb model of {${\rm GL}\sb n({\bf C})$} tensor products. {I}. {P}roof of the saturation conjecture}, {J. Amer. Math. Soc.}, VOLUME = {12}, YEAR = {1999}, PAGES = {1055--1090},
• Knutson, Allen and Tao, Terence and Woodward, Christopher, {The honeycomb model of {${\rm GL}\sb n(\mathbb C)$} tensor products. {II}. {P}uzzles determine facets of the {L}ittlewood-{R}ichardson cone}, {J. Amer. Math. Soc.}, VOLUME = {17}, YEAR = {2004}, PAGES = {19--48 (electronic)},
• Knutson, Allen and Tao, Terence , {Honeycombs and sums of {H}ermitian matrices}, {Notices Amer. Math. Soc.}, VOLUME = {48}, YEAR = {2001}, PAGES = {175--186},
• Buch, Anders Skovsted, {The saturation conjecture (after {A}.\ {K}nutson and {T}.\ {T}ao)}, {With an appendix by William Fulton}, {Enseign. Math. (2)}, VOLUME = {46}, YEAR = {2000}, PAGES = {43--60},
•  
• Regular triangulations and the secondary polytope - a good source is chapter 7 of the Gelfand-Kapranoz-Zelevinsky book

Further suggestions are welcome!