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

застосування методів загальної алгебри в комбінаторних контекстах і, навпаки, комбінаторних технік до алгебричних задач

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

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

ІсторіяРедагувати

В 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] і Річард Стенлі[en].

МатроїдиРедагувати

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

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

Скінченні геометріїРедагувати

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

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

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

Див. такожРедагувати

ПриміткиРедагувати

ЛітератураРедагувати