Русская Википедия:Алгебраическая комбинаторика

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Rq