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

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

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

Історія

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроїди

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

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

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

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

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

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

Див. також

• Алгебрична теорія графів
• Комбінаторна комутативна алгебра
• Комбінаторика багатогранників
• Геометрична комбінаторика

Література

• 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 (13 грудня). — С. 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. — 13 грудня. Архівовано з джерела 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. 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. — 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