Algebraic combinatorics is an area ofmathematics that employs methods ofabstract algebra, notablygroup theory andrepresentation theory, in variouscombinatorial contexts and, conversely, applies combinatorial techniques to problems inalgebra.
The term "algebraic combinatorics" was introduced in the late 1970s.[1] Through the early or mid-1990s, typical combinatorial objects of interest in algebraic combinatorics either admitted muchsymmetries (association schemes,strongly regular graphs, posets with agroup action) or possessed a rich algebraic structure, frequently of representation theoretic origin (symmetric functions,Young tableaux). This period is reflected in the area 05E,Algebraic combinatorics, of theAMSMathematics Subject Classification, introduced in 1991.
Algebraic combinatorics has come to be seen more expansively as an area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. Thus the combinatorial topics may beenumerative in nature or involvematroids,polytopes,partially ordered sets, orfinite geometries. On the algebraic side, besides group theory and representation theory,lattice theory andcommutative algebra are commonly used.
Thering of symmetric functions is a specific limit of the rings ofsymmetric polynomials inn indeterminates, asn goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the numbern of indeterminates (but its elements are neither polynomials nor functions). Among other things, this ring plays an important role in therepresentation theory of the symmetric groups.
Anassociation scheme is a collection ofbinary relations satisfying certain compatibility conditions. Association schemes provide a unified approach to many topics, for examplecombinatorial designs andcoding theory.[2][3] In algebra, association schemes generalizegroups, and the theory of association schemes generalizes thecharacter theory oflinear representations of groups.[4][5][6]
Astrongly regular graph is defined as follows. LetG = (V,E) be aregular graph withv vertices and degreek.G is said to bestrongly regular if there are alsointegers λ and μ such that:
A graph of this kind is sometimes said to be a srg(v,k, λ, μ).
Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sizedcomplete graphs,[7][8] and theircomplements, theTurán graphs.
AYoung tableau (pl.:tableaux) is acombinatorial object useful inrepresentation theory andSchubert calculus. It provides a convenient way to describe thegroup representations of thesymmetric andgeneral linear groups and to study their properties. Young tableaux were introduced byAlfred Young, amathematician atCambridge University, in 1900. They were then applied to the study of the symmetric group byGeorg Frobenius in 1903. Their theory was further developed by many mathematicians, includingPercy MacMahon,W. V. D. Hodge,G. de B. Robinson,Gian-Carlo Rota,Alain Lascoux,Marcel-Paul Schützenberger andRichard P. Stanley.
Amatroid is a structure that captures and generalizes the notion oflinear independence invector spaces. There are many equivalent ways to define a matroid, the most significant being in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions.
Matroid theory borrows extensively from the terminology oflinear algebra andgraph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry,topology,combinatorial optimization,network theory andcoding theory.[9][10]
Afinite geometry is anygeometric system that has only afinite number ofpoints.The familiarEuclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where thepixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finiteprojective andaffine spaces because of their regularity and simplicity. Other significant types of finite geometry are finiteMöbius or inversive planes andLaguerre planes, which are examples of a general type calledBenz planes, and their higher-dimensional analogs such as higher finiteinversive geometries.
Finite geometries may be constructed vialinear algebra, starting fromvector spaces over afinite field; the affine andprojective planes so constructed are calledGalois geometries. Finite geometries can also be defined purely axiomatically. Most common finite geometries are Galois geometries, since any finiteprojective space of dimension three or greater isisomorphic to a projective space over a finite field (that is, the projectivization of a vector space over a finite field). However, dimension two has affine and projective planes that are not isomorphic to Galois geometries, namely thenon-Desarguesian planes. Similar results hold for other kinds of finite geometries.
Media related toAlgebraic combinatorics at Wikimedia Commons