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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

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

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

См. также

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

Примечания

Литература