University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Algebraic combinatorics

In algebraic combinatorics we might use algebraic methods to solve combinatorial problems, or use combinatorial methods and ideas to study algebraic objects. The unifying feature of the subject is any significant interaction between algebraic and combinatorial ideas.

As a simple example, to solve an enumeration problem one often encodes combinatorial data into an algebra of formal power series by means of a generating function. Algebraic manipulations with these power series then provide a systematic way to solve the original counting problem. Methods from complex analysis can be used to obtain asymptotic solutions even when exact answers are intractable.

As another example, group theory and linear algebra are used to understand the structure of graphs. Most graphs have no nontrivial symmetries (automorphisms) -- graphs with many symmetries are highly structured and have applications in design theory, coding theory, and geometry. For any graph, the eigenvalues of its adjacency matrix encode a great deal of structural and enumerative information about it.

The examples above are applications of algebra to combinatorics. Conversely, the most concrete way to understand the ring of symmetric functions is through the combinatorics of Young tableaux. This ring can be used for many things: representation theory of the symmetric and general linear groups; intersection theory on Grassmann or flag manifolds; enumeration of maps (graphs) embedded on surfaces. Thus the combinatorics of Young tableaux (and related objects) describes complicated phenomena in representation theory, geometry, and enumeration.

These examples are far from exhaustive. There are many variations on the above themes, and applications of these ideas to statistical mechanics, high-energy physics, knot theory, algebraic geometry, probability theory, analysis of algorithms, and to many more areas.

We have two weekly Algebraic Combinatorics seminars -- one emphasizing enumeration, and one emphasizing algebraic graph theory. In any year for the past decade, there have been about a dozen Master's and PhD students studying algebraic combinatorics in our department. We regularly offer graduate courses in Algebraic Enumeration, Algebraic Graph Theory, and Combinatorial Designs, and also have a series of topics courses that change from year to year -- some recent topics have been Schubert Calculus, Statistical Mechanics, Knot Theory, and other advanced subjects.

Members:

  • Logan Crew: symmetric functions, graph theory
  • Chris Godsil: Algebraic graph theory
  • Ian Goulden: Combinatorial enumeration
  • David Jackson: Algebraic-enumerative combinatorics, moduli spaces of curves, intersection theory, Integrable Hierarchies
  • Stephen Melczer: Analytic combinatorics, computer algebra
  • Oliver Pechenik: Schubert calculus, symmetric function theory, dynamics
  • Kevin Purbhoo: Algebraic combinatorics, algebraic geometry
  • Bruce Richmond: Asymptotic enumeration
  • David Wagner: Enumerative combinatorics, statistical mechanics, matroid theory
  • Karen Yeats: Combinatorics in quantum field theory