Algebraická kombinatorika - Algebraic combinatorics

Akademický časopis viz Algebraická kombinatorika (deník).
Fano matroid, odvozené z Fano letadlo. Matroidy jsou jednou z mnoha studovaných oblastí algebraická kombinatorika.

Algebraická kombinatorika je oblast matematika který využívá metody abstraktní algebra, zejména teorie skupin a teorie reprezentace, v různých kombinační kontexty a naopak aplikuje kombinatorické techniky na problémy v algebra.

Dějiny

Termín „algebraická kombinatorika“ byl představen na konci 70. let.[1] Na počátku 90. let nebo v polovině 90. let typické kombinatorické objekty zájmu v algebraické kombinatorice připouštěly mnoho symetrie (asociační schémata, silně pravidelné grafy, posety s a skupinová akce ) nebo vlastnil bohatou algebraickou strukturu, často reprezentující teoretický původ (symetrické funkce, Mladé obrazy ). Toto období se odráží v oblasti 05E, Algebraická kombinatorika, z AMS Klasifikace matematických předmětů, představený v roce 1991.

Rozsah

Algebraická kombinatorika začala být viděna více expanzivně jako oblast matematiky, kde je interakce kombinatorických a algebraických metod obzvláště silná a významná. Kombinatorická témata tedy mohou být enumerativní v přírodě nebo zapojit matroidy, polytopes, částečně objednané sady nebo konečné geometrie. Na algebraické straně, kromě teorie skupin a reprezentací, teorie mřížky a komutativní algebra jsou běžné.

Důležitá témata

Symetrické funkce

Hlavní článek: Kruh symetrických funkcí

The kruh symetrických funkcí je konkrétní limit prstenů symetrické polynomy v n neurčuje, as n jde do nekonečna. Tento prsten slouží jako univerzální struktura, ve které lze vztahy mezi symetrickými polynomy vyjádřit způsobem nezávislým na počtu n neurčitých (ale jeho prvky nejsou ani polynomy, ani funkce). Mimo jiné tento prsten hraje důležitou roli v teorie reprezentace symetrických skupin.

Asociační schémata

Hlavní článek: Schéma přidružení

An asociační schéma je sbírka binární vztahy splňující určité podmínky kompatibility. Asociační schémata například poskytují jednotný přístup k mnoha tématům kombinatorické vzory a teorie kódování.[2][3] V algebře se asociační schémata zobecňují skupiny a teorie asociačních schémat zobecňuje teorie znaků z lineární reprezentace skupin.[4][5][6]

Silně pravidelné grafy

Hlavní článek: Silně pravidelný graf

A silně pravidelný graf je definována následovně. Nechat G = (PROTI,E) být a běžný graf s proti vrcholy a stupně k. G se říká, že je velmi pravidelné pokud existují také celá čísla λ a μ takové, že:

  • Každé dva sousední vrcholy mají λ společné sousedy.
  • Každé dva nesousedící vrcholy mají μ společných sousedů.

O grafu tohoto druhu se někdy říká, že je to srg (proti, k, λ, μ).

Někteří autoři vylučují grafy, které splňují definici triviálně, konkrétně grafy, které jsou disjunktním spojením jednoho nebo více stejně velkých kompletní grafy,[7][8] a jejich doplňuje, Turánovy grafy.

Mladé obrazy

Hlavní článek: Mladé tablo

A Mladé tablo (pl .: obrazy) je kombinační objekt užitečný v teorie reprezentace a Schubertův počet. Poskytuje pohodlný způsob, jak popsat skupinové reprezentace z symetrický a obecně lineární skupiny a studovat jejich vlastnosti. Mladá tabla představila Alfred Young, a matematik na Cambridge University, v roce 1900. Poté byly aplikovány na studium symetrické skupiny pomocí Georg Frobenius v roce 1903. Jejich teorii dále rozvíjelo mnoho matematiků, včetně Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger a Richard P. Stanley.

Matroidy

Hlavní článek: Matroid

A matroid je struktura, která zachycuje a zobecňuje pojem lineární nezávislost v vektorové prostory. Existuje mnoho ekvivalentních způsobů, jak definovat matroid, nejvýznamnější je z hlediska nezávislých množin, základen, obvodů, uzavřených množin nebo bytů, operátorů uzavření a hodnostních funkcí.

Teorie matroidů si značně půjčuje z terminologie lineární algebra a teorie grafů, do značné míry proto, že jde o abstrakci různých pojmů ústředního významu v těchto oblastech. Matroidy našly uplatnění v geometrii, topologie, kombinatorická optimalizace, teorie sítí a teorie kódování.[9][10]

Konečné geometrie

Hlavní článek: Konečná geometrie

A konečná geometrie je jakýkoli geometrický systém, který má pouze a konečný počet bodů.Známý Euklidovská geometrie není konečný, protože euklidovská čára obsahuje nekonečně mnoho bodů. Geometrie založená na grafice zobrazené na obrazovce počítače, kde pixelů jsou považovány za body, byla by konečnou geometrií. I když existuje mnoho systémů, které lze nazvat konečnými geometriemi, pozornost je většinou věnována konečnému projektivní a afinní prostory kvůli jejich pravidelnosti a jednoduchosti. Jiné významné typy konečné geometrie jsou konečné Möbiova nebo inverzní letadla a Laguerrovy letadla, což jsou příklady obecného typu zvaného Benz letadla a jejich trojrozměrné analogy, například vyšší konečné inverzní geometrie.

Konečné geometrie mohou být konstruovány pomocí lineární algebra, začínající od vektorové prostory přes konečné pole; afinní a projektivní roviny takto konstruované se nazývají Galoisovy geometrie. Konečné geometrie lze také definovat čistě axiomaticky. Nejběžnější konečné geometrie jsou Galoisovy geometrie, protože jakékoli konečné projektivní prostor dimenze tři nebo větší je izomorfní do projektivního prostoru nad konečným polem (tj. Projektivizace vektorového prostoru nad konečným polem). Dimenze dva má však afinní a projektivní roviny, které nejsou izomorfní vůči Galoisovým geometriím, konkrétně nedesarguesiánská letadla. Podobné výsledky platí i pro jiné druhy konečných geometrií.

Viz také

Reference

  1. ^ Algebraická kombinatorika od Eiichi Bannai
  2. ^ Bannai a Ito 1984
  3. ^ Godsil 1993
  4. ^ Bailey 2004, str. 387
  5. ^ Zieschang 2005b
  6. ^ Zieschang 2005a
  7. ^ „Brouwer, Andries E; Haemers, Willem H. Spektrum grafů. p. 101 " (PDF). Archivovány od originál (PDF) dne 16. 3. 2012. Citováno 2014-10-10.
  8. ^ Godsil, Chris; Royle, Gordone. Algebraická teorie grafů. Springer-Verlag New York, 2001, str. 218.
  9. ^ Neel, David L .; Neudauer, Nancy Ann (2009). "Matroidi, které jsi znal" (PDF). Matematický časopis. 82 (1): 26–41. doi:10,4169 / 193009809x469020. Citováno 4. října 2014.
  10. ^ Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal. „Aplikace teorie matroidů a kombinatorické optimalizace na teorii informací a kódování“ (PDF). www.birs.ca. Citováno 4. října 2014.

Další čtení

externí odkazy