Алгебрична комбінаторика

Матроїд Фано, отриманий з площини Фано. Матроїди — одна з багатьох галузей, які вивчаються в алгебричній комбінаториці.

Алгебрична комбінаторика — це галузь математики, що використовує методи загальної алгебри, особливо теорії груп і теорії представлень, у різних комбінаторних контекстах і, навпаки, застосовує комбінаторні техніки до задач в алгебрі.

Історія

В 1990-х роках типові комбінаторні об'єкти, які розглядалися в алгебричній комбінаториці, або мали велику кількість загальновизнаних симетрій (схема відношень[en], сильно регулярні графи, частково впорядковані множини з дією групи), або мали багату алгебричну структуру, що, як правило, мала теоретичні джерела (симетричні функції, діаграми Юнга). Цей період відбито в розділі 05E, «Алгебрична комбінаторика», математичної предметної класифікації AMS, запропонованої в 1991 році.

Сфера застосування

Алгебричну комбінаторику можна розглядати як галузь математики, де особливо суттєвою є взаємодія комбінаторних і алгебричних методів. Такими комбінаторними темами є перерахування за властивостями або галузі, що залучають матроїди, багатогранники, частково впорядковані множини або скінченні геометрії. З боку алгебри, крім теорії груп і теорії представлень, часто використовуються ґратки і комутативна алгебра. Журнал «Journal of Algebraic Combinatorics[en]», який випускає видавництво Springer-Verlag, є міжнародним журналом для статей з цієї галузі.

Важливі розділи

Симетричні функції

Докладніше: Симетрична функція

Кільце симетричних функцій[en] є своєрідною границею кілець симетричних многочленів від n змінних при n, що прямує до нескінченності. Це кільце слугує універсальною структурою, в якій зв'язки між симетричними многочленами можна виразити без прив'язки до числа змінних (але елементи кільця не є ні многочленами, ні функціями). Крім усього іншого, це кільце відіграє важливу роль у теории представлений симметрических групп[en].

Схеми відношень

Схема відношень[en] — це набір бінарних відношень, які задовольняють певним умовам сумісності. Схеми відношень дають однаковий підхід до багатьох розділів, наприклад, комбінаторних схем і теорії кодування[1][2]. В алгебрі схеми відношень узагальнюють групи, а теорія схем відношень узагальнює теорію характерів лінійних представлень груп[3][4][5].

Сильно регулярні графи

Сильно регулярний граф визначають таким чином. Нехай G = (V,E) — регулярний граф з v вершинами і степенем k. Кажуть, що G сильно регулярний, якщо існують цілі числа λ і μ, такі, що:

  • Будь-які дві суміжні вершини мають λ спільних сусідів.
  • Будь-які дві несуміжні вершини мають μ спільних сусідів.

Графи такого виду іноді позначаються srg(v, k, λ, μ).

Деякі автори виключають графи, які відповідають визначенню тривіально, а саме ті графи, які є об'єднанням (одного і більше) однакових повних графів[6][7], і їх доповнення, що не перетинаються, графи Турана.

Діаграми Юнга

Діаграми Юнга — комбінаторні об'єкти, корисні в теорії представлень і численні Шуберта[en]. Вони дають зручний спосіб опису представлень симетричних груп і повних лінійних груп і дозволяють вивчати властивості цих об'єктів. Діаграми запропонував Альфред Юнг[en], математик Кембриджського університету, в 1900 році. В 1903 році їх застосував для вивчення симетричних груп Фердинанд Фробеніус. Пізніше їх теорію розвинули багато математиків, серед яких Персі Макмагон[en], В. В. Д. Годж, Г. де Б. Робінсон[en], Д.-К. Рота, Ален Ласку[en], М.-П. Шютценберже[en] і Річард Стенлі[en].

Матроїди

Матроїд — це структура, яка вбирає й узагальнює поняття лінійної незалежності у векторних просторах. Є багато еквівалентних шляхів визначення матроїда, і найважливіші з них — у термінах незалежних множин, баз, замкнених множин чи площин, операторів замикання і функцій рангу.

Теорія матроїдів значною мірою запозичує термінологію з лінійної алгебри та теорії графів, переважно в тому, що в ній використовуються абстракції різних центральних понять із цих галузей, з топології, комбінаторної оптимізації, теорії мереж та теорії кодування[8][9].

Скінченні геометрії

Скінченна геометрія — це будь-яка геометрична система, що має лише скінченне число точок.

Звичайна евклідова геометрія не є скінченною, оскільки евклідова пряма містить нескінченно багато точок. Геометрію, засновану на графіці комп'ютерного екрана, де пікселі вважаються точками, можна вважати скінченною геометрією. Хоча існує багато систем, які можна було б вважати скінченними геометріями, переважно увагу приділяють скінченним проєктивним і афінним просторам зважаючи на їх регулярність і простоту. Інші суттєві типи скінченних геометрій — скінченні площини Мебіуса або інверсні площині та площини Лагерра[en], які є прикладами більш загальних об'єктів, званих площинами Бенца[en], і їх аналогами у вищих розмірностях, таких як скінченні інверсійні геометрії[en].

Скінченні геометрії можна побудувати за допомогою лінійної алгебри, починаючи з векторних просторів над скінченними полями. Афінні і проєктивні площини, побудовані таким чином, називають геометріями Галуа. Скінченні геометрії можна також визначити чисто аксіоматично. Найпоширеніші скінченні геометрії — геометрії Галуа, оскільки будь-який скінченний проєктивний простір розмірності три і більше ізоморфний проєктивному простору над скінченним полем. Проте в розмірності два є афінні і проєктивні площини, які не ізоморфні геометріям Галуа, а саме, недезаргові площини. Схожі результати мають місце для інших видів скінченних геометрій.

Див. також

Примітки

  1. ↑ Bannai, Ito, 1984.
  2. ↑ Godsil, 1993.
  3. ↑ Bailey, 2004, с. 387.
  4. ↑ Zieschang, 2005b.
  5. ↑ Zieschang, 2005a.
  6. ↑ Brouwer, Haemers, 2010, с. 116.
  7. ↑ Godsil, Royle, 2001, с. 218.
  8. ↑ Neel, Neudauer, 2009, с. 26–41.
  9. ↑ Kashyap, Soljanin, Vontobel, 2009.

Література

  • Bailey, Rosemary A. (2004), Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge University Press, ISBN 978-0-521-82446-0, MR 2047311, архів оригіналу за 24 жовтня 2017, процитовано 7 грудня 2020.
  • Andries E Brouwer, Willem H Haemers. Spectra of Graphs. — New York, Dordrecht, Heidelberg, London : Springer-Verlag, 2010. — (Universitext) — ISBN 9781461419389. — DOI:10.1007/9781461419396. Архівовано березень 16, 2012 на сайті Wayback Machine.
  • David L. Neel, Nancy Ann Neudauer. Matroids you have known // Mathematics Magazine. — 2009. — Т. 82, вип. 1 (27 грудня). — С. 26—41. — DOI:10.4169/193009809x469020. Архівовано з джерела 20 вересня 2020. Процитовано 2014-10-04.
  • Navin Kashyap, Emina Soljanin, Pascal Vontobel. Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory. — 2009. — 27 грудня. Архівовано з джерела 18 вересня 2020. Процитовано 2014-10-04.
  • Eiichi Bannai, Tatsuro Ito. Algebraic combinatorics I: Association schemes. — Menlo Park, CA : The Benjamin/Cummings Publishing Co., Inc, 1984. — С. xxiv+425. — ISBN 0-8053-0490-8.
  • New Perspectives in Algebraic Combinatorics / L. J. Billera, A. Björner, C. Greene, R. Simion, R. P. Stanley. — MSRI Publications. — Cambridge University Press, 1999. — Т. 38. Архівовано з джерела 8 січня 2020
  • Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics) — ISBN 0-387-95220-9.
  • C. D. Godsil. Algebraic Combinatorics. — New York : Chapman and Hall, 1993. — ISBN 0-412-04131-6.
  • Takayuki Hibi. Algebraic combinatorics on convex polytopes. — Glebe, Australia : Carslaw Publications, 1992.
  • Melvin Hochster[en]. Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975). — New York : Dekker, 1977. — Т. 26. — С. 171—223. — (Lecture Notes in Pure and Appl. Math.)
  • Ezra Miller, Bernd Sturmfels. Combinatorial commutative algebra. — New York, NY : Springer-Verlag, 2005. — Т. 227. — (Graduate Texts in Mathematics) — ISBN 0-387-22356-8.
  • Richard Stanley. Combinatorics and commutative algebra. — 2nd. — Boston, MA : Birkhäuser, 1996. — Т. 41. — (Progress in Mathematics) — ISBN 0-8176-3836-9.
  • Bernd Sturmfels. Gröbner bases and convex polytopes. — Providence, RI : American Mathematical Society, 1996. — Т. 8. — (University Lecture Series) — ISBN 0-8218-0487-1.
  • Doron Zeilberger. The Princeton Companion to Mathematics[en]. — Princeton University Press, 2008. — ISBN 978-0-691-11880-2. Архівовано з джерела 13 березня 2017
  • Zieschang, Paul-Hermann (2005a), Association Schemes: Designed Experiments, Algebra and Combinatorics by Rosemary A. Bailey, Review (PDF), Bulletin of the American Mathematical Society, 43 (02): 249—253, doi:10.1090/S0273-0979-05-01077-3, архів оригіналу (PDF) за 25 липня 2008, процитовано 7 грудня 2020
  • Zieschang, Paul-Hermann (2005b), Theory of association schemes, Springer, с. xii+283, ISBN 3-540-26136-2
  • Zieschang, Paul-Hermann (2006), The exchange condition for association schemes, Israel Journal of Mathematics, 151 (3): 357—380, doi:10.1007/BF02777367, ISSN 0021-2172, MR 2214129