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

Для академического журнала см. Алгебраическая комбинаторика (журнал) .
Матроид Фано , полученный из плоскости Фано . Матроиды - одна из многих областей, изучаемых в алгебраической комбинаторике .

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

История

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

Объем

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

Важные темы

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

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

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

Схемы ассоциации

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

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

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

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

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

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

Иногда такой граф называют srg ( v , k , λ, μ).

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

Молодые картины

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

Юнга (пл .: Tableaux ) является комбинаторным объектом полезным в теории представлений и Шуберт исчислении . Это обеспечивает удобный способ для описания представлений групп из симметричных и общих линейных групп и изучить их свойство. Таблицы Юнга были представлены Альфредом Янгом , математиком из Кембриджского университета , в 1900 году. Затем они были применены к изучению симметрической группы Георгом Фробениусом в 1903 году. Их теория получила дальнейшее развитие многими математиками, включая Перси Мак-Магона , В. В. Д. Ходжа , Г. де Б. Робинсон , Джан-Карло Рота , Ален Ласку , Марсель-Поль Шютценбергер и Ричард П. Стэнли .

Матроиды

Основная статья: Matroid

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

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

Конечная геометрия

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

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

Конечная геометрия может быть построена с помощью линейной алгебры , начиная с векторных пространств над конечным полем ; Построенные таким образом аффинная и проективная плоскости называются геометриями Галуа . Конечная геометрия также может быть определена чисто аксиоматически. Наиболее распространенными конечными геометриями являются геометрии Галуа, поскольку любое конечное проективное пространство размерности три или больше изоморфно проективному пространству над конечным полем (то есть проективизации векторного пространства над конечным полем). Однако у размерности два есть аффинные и проективные плоскости, которые не изоморфны геометрии Галуа, а именно недезарговы плоскости . Подобные результаты справедливы и для других типов конечных геометрий.

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки