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

Алгебраическая комбинаторика — это область математики, использующая методы общей алгебры, в особенности теории групп и теории представлений, в различных комбинаторных контекстах и, наоборот, применяющая комбинаторные техники к задачам в алгебре.

Матроид Фано, полученный из плоскости Фано. Матроиды — одна из многих областей, изучаемых в алгебраической комбинаторике.

История

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

Сфера применения

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

Важные разделы

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

Основная статья: Кольцо симметрических функций

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

Схемы отношений

Основная статья: Схема отношений

Схема отношений — это набор бинарных отношений, удовлетворяющих определённым условиям совместимости. Схемы отношений дают единообразный подход ко многим разделам, например, комбинаторным схемам и теории кодирования. В алгебре схемы отношений обобщают группы, а теория схем отношений обобщает теорию характеров линейных представлений групп.

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

Основная статья: Сильно регулярный граф

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

• Любые две смежные вершины имеют λ общих соседей.
• Любые две несмежные вершины имеют μ общих соседей.

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

Некоторые авторы исключают графы, которые удовлетворяют определению тривиально, а именно те графы, которые являются объединением непересекающихся (одного и более) одинаковых полных графов, и их дополнения, графы Турана.

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

Основная статья: Диаграмма Юнга

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

Матроиды

Основная статья: Матроид

Матроид — это структура, которая вбирает и обобщает понятие линейной независимости в векторных пространствах. Имеется много эквивалентных путей определения матроида, и наиболее важные из них — в терминах независимых множеств, баз, замкнутых множеств или плоскостей, операторов замыкания и функций ранга.

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

Конечные геометрии

Основная статья: Конечная геометрия

Конечная геометрия — это любая геометрическая система, имеющая лишь конечное число точек. Привычная Евклидова геометрия не конечна, поскольку евклидова прямая содержит бесконечно много точек. Геометрию, основанную на графике компьютерного экрана, где пиксели считаются точками, можно считать конечной геометрией. Хотя существует много систем, которые можно было бы считать конечными геометриями, в основном внимание уделяется конечным проективным и аффинным пространствам ввиду их регулярности и простоты. Другие существенные типы конечных геометрий — конечные плоскости Мёбиуса или инверсные плоскости и плоскости Лагерра, которые являются примерами более общих объектов, называемых плоскостями Бенца, и их аналогами в более высоких размерностях, таких как конечные инверсионные геометрии.

Конечные геометрии могут быть построены с помощью линейной алгебры, начиная с векторных пространств над конечными полями. Аффинные и проективные плоскости, построенные таким образом, называются геометриями Галуа. Конечные геометрии могут также быть определены чисто аксиоматически. Самые распространенные конечные геометрии — геометрии Галуа, поскольку любое конечное проективное пространство размерности три и более изоморфно проективному пространству над конечным полем. Однако в размерности два имеются аффинные и проективные плоскости, которые не изоморфны геометриям Галуа, а именно, недезарговы плоскости. Похожие результаты имеют место для других видов конечных геометрий.

См. также

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