Algebraic combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.
History
The term "algebraic combinatorics" was introduced in the late 1970s.
Scope
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 be
Important topics
Symmetric functions
The ring of symmetric functions is a specific limit of the rings of symmetric polynomials in n indeterminates, as n goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the number n of indeterminates (but its elements are neither polynomials nor functions). Among other things, this ring plays an important role in the representation theory of the symmetric groups.
Association schemes
An
Strongly regular graphs
A strongly regular graph is defined as follows. Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:
- Every two adjacent verticeshave λ common neighbours.
- Every two non-adjacent vertices have μ common neighbours.
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-sized complete graphs,[7][8] and their complements, the Turán graphs.
Young tableaux
A
Matroids
A matroid is a structure that captures and generalizes the notion of linear independence in vector 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 of linear algebra and graph 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 and coding theory.[9][10]
Finite geometries
A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels 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 finite projective and affine spaces because of their regularity and simplicity. Other significant types of finite geometry are finite Möbius or inversive planes and Laguerre planes, which are examples of a general type called Benz planes, and their higher-dimensional analogs such as higher finite inversive geometries.
Finite geometries may be constructed via linear algebra, starting from vector spaces over a finite field; the affine and projective planes so constructed are called Galois geometries. Finite geometries can also be defined purely axiomatically. Most common finite geometries are Galois geometries, since any finite projective space of dimension three or greater is isomorphic 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 the non-Desarguesian planes. Similar results hold for other kinds of finite geometries.
See also
- Algebraic graph theory
- Combinatorial commutative algebra
- Algebraic Combinatorics (journal)
- Journal of Algebraic Combinatorics
- Polyhedral combinatorics
Citations
- ^ Bannai 2012.
- ^ Bannai & Ito 1984.
- ^ Godsil 1993.
- ^ Bailey 2004, p. 387.
- ^ Zieschang 2005b.
- ^ Zieschang 2005a.
- ^ Brouwer & Haemers n.d., p. 101.
- ^ Godsil & Royle 2001, p. 218.
- ^ Neel & Neudauer 2009, pp. 26–41.
- ^ Kashyap, Soljanin & Vontobel 2009.
Works cited
- MR 2047311.. (Chapters from preliminary draft are available on-line.)
- Bannai, Eiichi (2012). "Algebraic Combinatorics" (PDF). School of Mathematical Sciences Shanghai Jiao Tong University. Retrieved 30 January 2022.
- Bannai, Eiichi; Ito, Tatsuro (1984). Algebraic combinatorics I: Association schemes. Menlo Park, CA: The Benjamin/Cummings Publishing Co. MR 0882540.
- Brouwer, Andries E.; Haemers, Willem H. (n.d.). Spectra of Graphs (PDF). p. 101. Archived from the original (PDF) on 16 March 2012.
- Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. Graduate Texts in Mathematics. New York: Springer-Verlag. p. 218. ISBN 978-0-387-95241-3.
- MR 1220704.
- Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal (2–7 August 2009). "Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory" (PDF). BIRS. Retrieved 4 October 2014.
- Neel, David L.; .
- Zieschang, Paul-Hermann (2005a). "Association Schemes: Designed Experiments, Algebra and Combinatorics by Rosemary A. Bailey, Review" (PDF). Bulletin of the American Mathematical Society. 43 (2): 249–253. .
- Zieschang, Paul-Hermann (2005b). Theory of association schemes. Springer. ISBN 3-540-26136-2.
Further reading
- ISBN 052177087-4.
- Hibi, Takayuki (1992). Algebraic combinatorics on convex polytopes. Glebe, Australia: Carslaw Publications. OCLC 29023080.
- Zbl 0351.13009.
- Miller, Ezra; Zbl 1066.13001.
- Zbl 0838.13008.
- Zbl 0856.13020 – via Internet Archive.
- Zeilberger, Doron (2008). "Enumerative and Algebraic Combinatorics" (PDF). The Princeton Companion to Mathematics. Princeton University Press.
External links
- Media related to Algebraic combinatorics at Wikimedia Commons