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: