Алгебраическая комбинаторика
Алгебраическая комбинаторика — это область математики , которая использует методы абстрактной алгебры , особенно теории групп и теории представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры .
История [ править ]
Термин «алгебраическая комбинаторика» был введен в конце 1970-х годов. [1] В начале или середине 1990-х типичные комбинаторные объекты, представляющие интерес в алгебраической комбинаторике, либо допускали множество симметрий ( схемы ассоциации , сильно регулярные графы , частично упорядоченные множества с групповым действием ), либо обладали богатой алгебраической структурой, часто теоретического происхождения ( симметричные функции , таблицы Юнга ). Этот период отражен в области 05E «Алгебраическая комбинаторика » AMS Предметной классификации математики , введенной в 1991 году.
Область применения [ править ]
Алгебраическую комбинаторику стали рассматривать более широко как область математики, в которой взаимодействие комбинаторных и алгебраических методов особенно сильно и значимо. Таким образом, комбинаторные темы могут носить перечислительный характер или включать в себя матроиды , многогранники , частично упорядоченные множества или конечную геометрию . С алгебраической стороны, помимо теории групп и теории представлений, теория решеток и коммутативная алгебра обычно используются .
Важные темы [ править ]
Симметричные функции [ править ]
Кольцо симметрических функций является специфическим пределом колец симметричных многочленов от n неопределённостей, когда n стремится к бесконечности. Это кольцо служит универсальной структурой, в которой отношения между симметричными полиномами могут быть выражены способом, не зависящим от числа n неопределенных величин (но его элементы не являются ни полиномами, ни функциями). Помимо прочего, это кольцо играет важную роль в теории представлений симметрических групп .
Схемы ассоциации [ править ]
Схема ассоциации — это набор бинарных отношений, удовлетворяющих определенным условиям совместимости. Схемы ассоциации обеспечивают единый подход ко многим темам, например, к комбинаторным проектам и теории кодирования . [2] [3] В алгебре ассоциативные схемы обобщают группы , а теория ассоциативных схем обобщает теорию характеров линейных представлений групп. [4] [5] [6]
Сильно регулярные графики [ править ]
определяется Сильно регулярный граф следующим образом. Пусть G = ( V , E ) — регулярный граф с v вершинами и степенью k . G называется сильно регулярной, если существуют также целые числа λ и µ такие, что:
- Каждые две соседние вершины имеют λ общих соседей.
- Каждые две несмежные вершины имеют μ общих соседей.
Граф такого типа иногда называют srg( v , k , λ, µ).
Некоторые авторы исключают графы, которые тривиально удовлетворяют определению, а именно те графы, которые представляют собой непересекающееся объединение одного или нескольких полных графов одинакового размера . [7] [8] и их дополнения — графы Турана .
Молодые картины [ править ]
Таблица Юнга (мн.: tableaux ) — комбинаторный объект, полезный в теории представлений и исчислении Шуберта . обеспечивает удобный способ описания групповых представлений симметричных Он и общих линейных групп и изучения их свойств. Таблицы Янга были введены Альфредом Янгом , математиком из Кембриджского университета , в 1900 году. Затем они были применены к изучению симметричной группы Георгом Фробениусом в 1903 году. Их теория получила дальнейшее развитие у многих математиков, в том числе Перси МакМагона , УВД Ходжа , Дж. де Б. Робинсон , Джан-Карло Рота , Ален Ласку , Марсель-Поль Шютценбергер и Ричард П. Стэнли .
Матроиды [ править ]
Матроид — это структура, которая отражает и обобщает понятие линейной независимости в векторных пространствах . Существует множество эквивалентных способов определения матроида, наиболее важным из которых является использование независимых множеств, базисов, схем, замкнутых множеств или квартир, операторов замыкания и функций ранга.
Теория матроидов во многом заимствует терминологию линейной алгебры и теории графов , главным образом потому, что она представляет собой абстракцию различных понятий, имеющих центральное значение в этих областях. Матроиды нашли применение в геометрии, топологии , комбинаторной оптимизации , теории сетей и теории кодирования . [9] [10]
Конечные геометрии [ править ]
Конечная геометрия — это любая геометрическая система, имеющая только конечное число точек .Знакомая евклидова геометрия не конечна, поскольку евклидова прямая содержит бесконечное число точек. Геометрия, основанная на графике, отображаемой на экране компьютера, где пиксели считаются точками, будет конечной геометрией. Хотя существует множество систем, которые можно было бы назвать конечными геометриями, внимание в основном уделяется конечным проективным и аффинным пространствам из-за их регулярности и простоты. Другими важными типами конечной геометрии являются конечные плоскости Мёбиуса или инверсивные плоскости и плоскости Лагерра , которые являются примерами общего типа, называемого плоскостями Бенца , и их многомерные аналоги, такие как высшие конечные инверсивные геометрии .
Конечные геометрии могут быть построены с помощью линейной алгебры , начиная с векторных пространств над конечным полем ; построенные таким образом аффинные и проективные плоскости называются геометриями Галуа . Конечные геометрии также могут быть определены чисто аксиоматически. Наиболее распространенными конечными геометриями являются геометрии Галуа, поскольку любое конечное проективное пространство размерности три или больше изоморфно проективному пространству над конечным полем (то есть проективизации векторного пространства над конечным полем). Однако в измерении два есть аффинные и проективные плоскости, которые не изоморфны геометрии Галуа, а именно недесарговы плоскости . Аналогичные результаты верны и для других видов конечных геометрий.
См. также [ править ]
- Алгебраическая теория графов
- Комбинаторная коммутативная алгебра
- Алгебраическая комбинаторика (журнал)
- Журнал алгебраической комбинаторики
- Полиэдральная комбинаторика
Цитаты [ править ]
- ^ Бонд 2012 .
- ^ Баннаи и Ито 1984 .
- ^ Годсил 1993 .
- ^ Бэйли 2004 , с. 387.
- ^ Цишанг 2005b .
- ^ Цишанг 2005a .
- ^ Брауэр и Хамерс, без даты , с. 101.
- ^ Годсил и Ройл 2001 , с. 218.
- ^ Нил и Нойдауэр 2009 , стр. 26–41.
- ^ Солянин и Фонтобель Кашьяп ,
Цитируемые работы [ править ]
- Бейли, Розмари А. (2004). Схемы ассоциации: спланированные эксперименты, алгебра и комбинаторика . Издательство Кембриджского университета. ISBN 978-0-521-82446-0 . МР 2047311 . . (Главы из предварительного проекта доступны в Интернете .)
- Баннаи, Эйичи (2012). «Алгебраическая комбинаторика» (PDF) . Школа математических наук Шанхайского университета Цзяо Тун . Проверено 30 января 2022 г.
- Баннаи, Эйичи; Ито, Тацуро (1984). Алгебраическая комбинаторика I: Схемы ассоциаций . издательства Benjamin/Cummings Publishing Co. Менло-Парк, Калифорния: ISBN 0-8053-0490-8 . МР 0882540 .
- Брауэр, Андрис Э.; Хемерс, Виллем Х. (nd). Спектры графиков (PDF) . п. 101. Архивировано из оригинала (PDF) 16 марта 2012 года.
- Годсил, Крис; Ройл, Гордон (2001). Алгебраическая теория графов . Тексты для аспирантов по математике. Нью-Йорк: Springer-Verlag. п. 218. ИСБН 978-0-387-95241-3 .
- Годсил, Крис Д. (1993). Алгебраическая комбинаторика . Нью-Йорк: Чепмен и Холл. ISBN 0-412-04131-6 . МР 1220704 .
- Кашьяп, Навин; Солянин, Эмина; Фонтобель, Паскаль (2–7 августа 2009 г.). «Применение теории матроидов и комбинаторной оптимизации к теории информации и кодирования» (PDF) . БИРС . Проверено 4 октября 2014 г.
- Нил, Дэвид Л.; Нойдауэр, Нэнси Энн (2009). «Матроиды, которых вы знали» (PDF) . Журнал «Математика» . 82 (1): 26–41. дои : 10.4169/193009809x469020 .
- Цишанг, Пол-Германн (2005a). « Схемы ассоциации: спланированные эксперименты, алгебра и комбинаторика Розмари А. Бейли, обзор» (PDF) . Бюллетень Американского математического общества . 43 (2): 249–253. дои : 10.1090/S0273-0979-05-01077-3 .
- Цишанг, Пол-Германн (2005b). Теория ассоциативных схем . Спрингер. ISBN 3-540-26136-2 .
Дальнейшее чтение [ править ]
- Биллера, Луис Дж .; Бьёрнер, Андерс ; Грин, Кертис ; Симион, Родика ; Стэнли, Ричард П. , ред. (1999). Новые перспективы в алгебраической комбинаторике . Публикации ИИГС. Том. 38. Издательство Кембриджского университета . ISBN 052177087-4 .
- Хиби, Такаюки (1992). Алгебраическая комбинаторика на выпуклых многогранниках . Глеб, Австралия: Публикации Карслоу. ISBN 1875399046 . ОСЛК 29023080 .
- Хохстер, Мелвин (1977). «Кольца Коэна – Маколея, комбинаторика и симплициальные комплексы» . Теория колец II: материалы второй конференции в Оклахоме . Конспект лекций по чистой и прикладной математике. Том. 26. Деккер. стр. 171–223. ISBN 0-8247-6575-3 . OCLC 610144046 . Збл 0351.13009 .
- Миллер, Эзра; Штурмфельс, Бернд (2005). Комбинаторная коммутативная алгебра . Тексты для аспирантов по математике . Том 227. Спрингер. ISBN 0-387-22356-8 . Збл 1066.13001 .
- Стэнли, Ричард П. (1996). Комбинаторика и коммутативная алгебра . Прогресс в математике. Том. 41 (2-е изд.). Биркхойзер. ISBN 0-8176-3836-9 . Збл 0838.13008 .
- Штурмфельс, Бернд (1996). Базисы Грёбнера и выпуклые многогранники . Серия университетских лекций. Том. 8. Американское математическое общество . ISBN 0-8218-0487-1 . OCLC 907364245 . Zbl 0856.13020 – через Интернет-архив .
- Зейлбергер, Дорон (2008). «Исчислительная и алгебраическая комбинаторика» (PDF) . Принстонский спутник математики . Издательство Принстонского университета.
Внешние ссылки [ править ]
СМИ, связанные с алгебраической комбинаторикой , на Викискладе?
