Content deleted Content added
XOR'easter (talk | contribs) →See also: cleanup -- there's no need to say "Journal of X, a journal intended to be a journal" |
|||
| (29 intermediate revisions by 17 users not shown) | |||
Line 1:
{{Short description|Area of combinatorics}}
{{for|the academic journal|Algebraic Combinatorics (journal)}}
[[File:fano plane.svg|thumb|The Fano [[matroid]], derived from the [[Fano plane]]. Matroids are one of many kinds of objects studied in algebraic combinatorics.]]
{{use dmy dates|date=January 2022}}
'''Algebraic combinatorics''' is an area of [[mathematics]] that employs methods of [[abstract algebra]], notably [[group theory]] and [[representation theory]], in various [[combinatorics|combinatorial]] contexts and, conversely, applies combinatorial techniques to problems in [[abstract algebra|algebra]].
==History==
The term "algebraic combinatorics" was introduced in the late 1970s.{{sfn|Bannai|2012}} Through the early or mid-1990s, typical combinatorial objects of interest in algebraic combinatorics either admitted a lot of [[symmetry (mathematics)|symmetries]] ([[association scheme]]s, [[strongly regular graph]]s, posets with a [[Group action (mathematics)|group action]]) or possessed a rich algebraic structure, frequently of representation theoretic origin ([[symmetric function]]s, [[Young tableaux]]). This period is reflected in the area 05E, ''Algebraic combinatorics'', of the [[American Mathematical Society|AMS]] [[Mathematics Subject Classification]], introduced in 1991.
==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 [[enumerative combinatorics|enumerative]] in nature or involve [[matroid]]s, [[polytope]]s, [[partially ordered set]]s, or [[finite geometry|finite geometries]]. On the algebraic side, besides group theory and representation theory, [[lattice theory]] and [[commutative algebra]] are
==Important topics==
===Symmetric functions===
{{main|Ring of symmetric functions}}
Line 18 ⟶ 20:
{{main|Association scheme}}
An [[association scheme]] is a collection of [[binary relation]]s satisfying certain compatibility conditions. Association schemes provide a unified approach to many topics, for example [[combinatorial design]]s and [[coding theory]].
===Strongly regular graphs===
Line 27 ⟶ 29:
* Every two non-adjacent vertices have μ common neighbours.
A graph of this kind is sometimes said to be
Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized [[complete graph]]s,
===Young tableaux===
{{main|Young tableau}}
A [[Young tableau]] (pl.: ''tableaux'') is a [[combinatorics|combinatorial]] object useful in [[representation theory]] and [[Schubert calculus]]. It provides a convenient way to describe the [[group representation]]s of the [[symmetric group|symmetric]] and [[general linear group|general linear]] groups and to study their properties. Young tableaux were introduced by [[Alfred Young (mathematician)|Alfred Young]], a [[mathematician]] at [[University of Cambridge|Cambridge University]], in 1900. They were then applied to the study of the symmetric group by [[Georg Frobenius]] in 1903. Their theory was further developed by many mathematicians, including [[Percy MacMahon]], [[W. V. D. Hodge]], [[Gilbert de Beauregard Robinson|G. de B. Robinson]], [[Gian-Carlo Rota]], [[Alain Lascoux]], [[Marcel-Paul Schützenberger]] and [[Richard P. Stanley]].
===Matroids===
Line 39 ⟶ 41:
A [[matroid]] is a structure that captures and generalizes the notion of [[linear independence]] in [[vector space]]s. 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]].
===Finite geometries===
{{main|Finite geometry}}
A [[finite geometry]] is any [[geometry|geometric]] system that has only a [[finite set|finite]] number of [[point (geometry)|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 [[pixel]]s 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 space|projective]] and [[affine space]]s because of their regularity and simplicity. Other significant types of finite geometry are finite [[Möbius plane|Möbius or inversive
Finite geometries may be constructed via [[linear algebra]], starting from [[vector space]]s over a [[finite field]]; the affine and [[projective plane]]s so constructed are called [[Galois geometry|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 [[isomorphism|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 plane]]s. Similar results hold for other kinds of finite geometries.
== See also ==
* [[Algebraic graph theory]]
* [[Combinatorial commutative algebra]]
* [[Polyhedral combinatorics]]
* [[Algebraic Combinatorics (journal)|''Algebraic Combinatorics'' (journal)]]
* ''[[Journal of Algebraic Combinatorics]]''
* [[International Conference on Formal Power Series and Algebraic Combinatorics]]
== Citations ==
{{Reflist|20em}}
==Works
{{
*{{cite book| title = Association Schemes: Designed Experiments, Algebra and Combinatorics
| last = Bailey | first = Rosemary A. | year = 2004
| author-link = Rosemary A. Bailey
| publisher = Cambridge University Press
| url = http://www.maths.qmul.ac.uk/~rab/Asbook
| isbn = 978-0-521-82446-0 | mr = 2047311
}}. (Chapters from preliminary draft are [http://www.maths.qmw.ac.uk/~rab available on-line].)
*{{Cite web| title = Algebraic Combinatorics
| last = Bannai | first = Eiichi | year = 2012
| publisher = School of Mathematical Sciences Shanghai Jiao Tong University
| url = http://math.sjtu.edu.cn/conference/Bannai/2012/data/bannai.pdf
| access-date = 30 January 2022
}}
*{{cite book| title = Algebraic combinatorics I: Association schemes
| last1 = Bannai | first1 = Eiichi
| last2 = Ito | first2 = Tatsuro
| year = 1984
| publisher = The Benjamin/Cummings Publishing Co. | ___location = Menlo Park, CA
| isbn = 0-8053-0490-8 | mr = 0882540
}}
*{{Cite book| title = Spectra of Graphs
| last1 = Brouwer | first1 = Andries E.
| last2 = Haemers | first2 = Willem H.
| page = 101
| url = http://homepages.cwi.nl/~aeb/math/ipm.pdf | url-status = dead
| archive-url = https://web.archive.org/web/20120316102909/http://homepages.cwi.nl/~aeb/math/ipm.pdf
| date = n.d. | archive-date = 16 March 2012
}}
*{{Cite book| title = Algebraic Graph Theory
| last1 = Godsil | first1 = Chris
| last2 = Royle | first2 = Gordon
| year = 2001
| publisher = Springer-Verlag | ___location = New York
| series = Graduate Texts in Mathematics
| page = 218
| isbn = 978-0-387-95241-3
}}
*{{cite book| title = Algebraic Combinatorics
| last = Godsil | first = Chris D. | year = 1993
| author-link = Chris Godsil
| publisher = Chapman and Hall | ___location = New York
| ISBN = 0-412-04131-6 | mr = 1220704
}}
*{{cite web| title = Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory
| last1 = Kashyap | first1 = Navin
| last2 = Soljanin | first2 = Emina
| last3 = Vontobel | first3 = Pascal
| publisher = [[Banff International Research Station|BIRS]]
| url = https://www.birs.ca/workshops/2009/09w5103/report09w5103.pdf
| date = 2–7 August 2009 | access-date = 4 October 2014
}}
*{{cite journal | title = Matroids you have known
| last1 = Neel | first1 = David L.
| last2 = Neudauer | first2 = Nancy Ann
| author2-link = Nancy Neudauer
| journal = Mathematics Magazine
| year = 2009 | volume = 82 | issue = 1 | pages = 26–41
| url = http://www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf
| doi = 10.4169/193009809x469020
}}
*{{cite journal | title = ''Association Schemes: Designed Experiments, Algebra and Combinatorics'' by Rosemary A. Bailey, Review
| last = Zieschang | first = Paul-Hermann
| journal = Bulletin of the American Mathematical Society
| year = 2005a | volume = 43 | issue = 2 | pages = 249–253
| url = https://www.ams.org/bull/2006-43-02/S0273-0979-05-01077-3/S0273-0979-05-01077-3.pdf
| doi = 10.1090/S0273-0979-05-01077-3
| doi-access = free
}}
*{{cite book| title = Theory of association schemes
| last = Zieschang | first = Paul-Hermann | year = 2005b
| publisher = Springer
| isbn = 3-540-26136-2
}}
{{refend}}
==Further reading==
{{refbegin}}
*{{cite book| title = New Perspectives in Algebraic Combinatorics
| editor1-last = Billera | editor1-first = Louis J. | editor1-link = Louis Billera
| editor2-last = Björner | editor2-first = Anders | editor2-link = Anders Björner
| editor3-last = Greene | editor3-first = Curtis | editor3-link = Curtis Greene
| editor4-last = Simion | editor4-first = Rodica | editor4-link = Rodica Simion
| editor5-last = Stanley | editor5-first = Richard P. | editor5-link = Richard P. Stanley
| year = 1999
| publisher = [[Cambridge University Press]]
| volume = 38 | series = MSRI Publications
| url = http://library.msri.org/books/Book38/index.html
| isbn = 052177087-4
}}
*{{Cite book| title = Algebraic combinatorics on convex polytopes
| last = Hibi | first = Takayuki | year = 1992
| publisher = Carslaw Publications | ___location = Glebe, Australia |isbn=1875399046 |oclc=29023080
}}
*{{cite conference |author-link=Melvin Hochster |first=Melvin |last=Hochster |title=Cohen–Macaulay rings, combinatorics, and simplicial complexes |book-title=Ring Theory II: Proceedings of the Second Oklahoma Conference |publisher=Dekker |series=Lecture Notes in Pure and Applied Mathematics |volume=26 |date=1977 |isbn=0-8247-6575-3 |pages=171–223 |oclc=610144046 |url=https://archive.org/details/ringtheoryiiproc0026ring |zbl=0351.13009}}
*{{Cite book| title = Combinatorial commutative algebra
| last1 = Miller | first1 = Ezra
| last2 = Sturmfels | first2 = Bernd
| author2-link = Bernd Sturmfels
| year = 2005
| publisher = Springer
| volume = 227 | series = [[Graduate Texts in Mathematics]]
| isbn = 0-387-22356-8 |zbl=1066.13001|url={{GBurl|OYBCAAAAQBAJ|pg=PR11}}
}}
*{{Cite book| title = Combinatorics and commutative algebra | edition = 2nd
| last = Stanley | first = Richard P. | year = 1996
| author-link = Richard P. Stanley
| publisher = Birkhäuser
| volume = 41 | series = Progress in Mathematics
| isbn = 0-8176-3836-9 |zbl=0838.13008 |url={{GBurl|tZVCAAAAQBAJ|pg=PR5}}
}}
*{{cite book| title = Gröbner bases and convex polytopes
| last = Sturmfels | first = Bernd | year = 1996
| author-link = Bernd Sturmfels
| publisher = [[American Mathematical Society]]
| volume = 8 | series = University Lecture Series
| url = https://archive.org/details/grobnerbasesconv0000stur | url-access = registration | via = [[Internet Archive]]
| isbn = 0-8218-0487-1 |oclc=907364245 |zbl=0856.13020
}}
*{{Cite book| chapter = Enumerative and Algebraic Combinatorics
| last = Zeilberger | first = Doron | year = 2008
| author-link = Doron Zeilberger
| title = [[The Princeton Companion to Mathematics]]
| publisher = Princeton University Press
| chapter-url = http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf
}}
{{refend}}
==External links==
* {{Commons category-inline}}
[[Category:Algebraic combinatorics|
| |||