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

Поделись знанием:
Перейти к: навигация, поиск

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





История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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

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

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

См. также

Напишите отзыв о статье "Алгебраическая комбинаторика"

Примечания

Литература

  • Andries E Brouwer, Willem H Haemers. [homepages.cwi.nl/~aeb/math/ipm.pdf Spectra of Graphs]. — New York, Dordrecht, Heidelberg, London: Springer-Verlag. — (Universitext). — ISBN 9781461419389. — DOI:10.1007/9781461419396
  • David L. Neel, Nancy Ann Neudauer [www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf Matroids you have known] // Mathematics Magazine. — 2009. — Т. 82, вып. 1. — С. 26–41. — DOI:10.4169/193009809x469020.
  • Navin Kashyap, Emina Soljanin, Pascal Vontobel [www.birs.ca/workshops/2009/09w5103/report09w5103.pdf Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory]. — 2009.
  • Eiichi Bannai, Tatsuro Ito. Algebraic combinatorics I: Association schemes. — Menlo Park, CA: The Benjamin/Cummings Publishing Co., Inc., 1984. — С. xxiv+425. — ISBN 0-8053-0490-8.
  • [library.msri.org/books/Book38/index.html New Perspectives in Algebraic Combinatorics] / L. J. Billera, A. Björner, C. Greene, R. Simion, R. P. Stanley. — MSRI Publications. — Cambridge University Press, 1999. — Т. 38.
  • Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics). — ISBN 0-387-95220-9. — ISBN 0-387-95241-1.
  • C. D. Godsil. Algebraic Combinatorics. — New York: Chapman and Hall, 1993. — ISBN 0-412-04131-6.
  • Takayuki Hibi. Algebraic combinatorics on convex polytopes. — Glebe, Australia: Carslaw Publications, 1992.
  • Melvin Hochster. Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975). — New York: Dekker, 1977. — Т. 26. — С. 171–223. — (Lecture Notes in Pure and Appl. Math.).
  • Ezra Miller, Bernd Sturmfels. Combinatorial commutative algebra. — New York, NY: Springer-Verlag, 2005. — Т. 227. — (Graduate Texts in Mathematics). — ISBN 0-387-22356-8.
  • Richard Stanley[en]. Combinatorics and commutative algebra. — 2nd. — Boston, MA: Birkhäuser, 1996. — Т. 41. — (Progress in Mathematics). — ISBN 0-8176-3836-9.
  • Bernd Sturmfels. Gröbner bases and convex polytopes. — Providence, RI: American Mathematical Society, 1996. — Т. 8. — (University Lecture Series). — ISBN 0-8218-0487-1.
  • Doron Zeilberger. [www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf The Princeton Companion to Mathematics[en]]. — Princeton University Press, 2008. — ISBN 978-0-691-11880-2.


Отрывок, характеризующий Алгебраическая комбинаторика

– Ничего, грустна. Но знаете, кто ее спас? Это целый роман. Nicolas Ростов. Ее окружили, хотели убить, ранили ее людей. Он бросился и спас ее…
– Еще роман, – сказал ополченец. – Решительно это общее бегство сделано, чтобы все старые невесты шли замуж. Catiche – одна, княжна Болконская – другая.
– Вы знаете, что я в самом деле думаю, что она un petit peu amoureuse du jeune homme. [немножечко влюблена в молодого человека.]
– Штраф! Штраф! Штраф!
– Но как же это по русски сказать?..


Когда Пьер вернулся домой, ему подали две принесенные в этот день афиши Растопчина.
В первой говорилось о том, что слух, будто графом Растопчиным запрещен выезд из Москвы, – несправедлив и что, напротив, граф Растопчин рад, что из Москвы уезжают барыни и купеческие жены. «Меньше страху, меньше новостей, – говорилось в афише, – но я жизнью отвечаю, что злодей в Москве не будет». Эти слова в первый раз ясно ыоказали Пьеру, что французы будут в Москве. Во второй афише говорилось, что главная квартира наша в Вязьме, что граф Витгснштейн победил французов, но что так как многие жители желают вооружиться, то для них есть приготовленное в арсенале оружие: сабли, пистолеты, ружья, которые жители могут получать по дешевой цене. Тон афиш был уже не такой шутливый, как в прежних чигиринских разговорах. Пьер задумался над этими афишами. Очевидно, та страшная грозовая туча, которую он призывал всеми силами своей души и которая вместе с тем возбуждала в нем невольный ужас, – очевидно, туча эта приближалась.
«Поступить в военную службу и ехать в армию или дожидаться? – в сотый раз задавал себе Пьер этот вопрос. Он взял колоду карт, лежавших у него на столе, и стал делать пасьянс.
– Ежели выйдет этот пасьянс, – говорил он сам себе, смешав колоду, держа ее в руке и глядя вверх, – ежели выйдет, то значит… что значит?.. – Он не успел решить, что значит, как за дверью кабинета послышался голос старшей княжны, спрашивающей, можно ли войти.
– Тогда будет значить, что я должен ехать в армию, – договорил себе Пьер. – Войдите, войдите, – прибавил он, обращаясь к княжие.
(Одна старшая княжна, с длинной талией и окаменелым лидом, продолжала жить в доме Пьера; две меньшие вышли замуж.)
– Простите, mon cousin, что я пришла к вам, – сказала она укоризненно взволнованным голосом. – Ведь надо наконец на что нибудь решиться! Что ж это будет такое? Все выехали из Москвы, и народ бунтует. Что ж мы остаемся?
– Напротив, все, кажется, благополучно, ma cousine, – сказал Пьер с тою привычкой шутливости, которую Пьер, всегда конфузно переносивший свою роль благодетеля перед княжною, усвоил себе в отношении к ней.
– Да, это благополучно… хорошо благополучие! Мне нынче Варвара Ивановна порассказала, как войска наши отличаются. Уж точно можно чести приписать. Да и народ совсем взбунтовался, слушать перестают; девка моя и та грубить стала. Этак скоро и нас бить станут. По улицам ходить нельзя. А главное, нынче завтра французы будут, что ж нам ждать! Я об одном прошу, mon cousin, – сказала княжна, – прикажите свезти меня в Петербург: какая я ни есть, а я под бонапартовской властью жить не могу.
– Да полноте, ma cousine, откуда вы почерпаете ваши сведения? Напротив…
– Я вашему Наполеону не покорюсь. Другие как хотят… Ежели вы не хотите этого сделать…
– Да я сделаю, я сейчас прикажу.
Княжне, видимо, досадно было, что не на кого было сердиться. Она, что то шепча, присела на стул.
– Но вам это неправильно доносят, – сказал Пьер. – В городе все тихо, и опасности никакой нет. Вот я сейчас читал… – Пьер показал княжне афишки. – Граф пишет, что он жизнью отвечает, что неприятель не будет в Москве.
– Ах, этот ваш граф, – с злобой заговорила княжна, – это лицемер, злодей, который сам настроил народ бунтовать. Разве не он писал в этих дурацких афишах, что какой бы там ни был, тащи его за хохол на съезжую (и как глупо)! Кто возьмет, говорит, тому и честь и слава. Вот и долюбезничался. Варвара Ивановна говорила, что чуть не убил народ ее за то, что она по французски заговорила…
– Да ведь это так… Вы всё к сердцу очень принимаете, – сказал Пьер и стал раскладывать пасьянс.
Несмотря на то, что пасьянс сошелся, Пьер не поехал в армию, а остался в опустевшей Москве, все в той же тревоге, нерешимости, в страхе и вместе в радости ожидая чего то ужасного.
На другой день княжна к вечеру уехала, и к Пьеру приехал его главноуправляющий с известием, что требуемых им денег для обмундирования полка нельзя достать, ежели не продать одно имение. Главноуправляющий вообще представлял Пьеру, что все эти затеи полка должны были разорить его. Пьер с трудом скрывал улыбку, слушая слова управляющего.
– Ну, продайте, – говорил он. – Что ж делать, я не могу отказаться теперь!
Чем хуже было положение всяких дел, и в особенности его дел, тем Пьеру было приятнее, тем очевиднее было, что катастрофа, которой он ждал, приближается. Уже никого почти из знакомых Пьера не было в городе. Жюли уехала, княжна Марья уехала. Из близких знакомых одни Ростовы оставались; но к ним Пьер не ездил.
В этот день Пьер, для того чтобы развлечься, поехал в село Воронцово смотреть большой воздушный шар, который строился Леппихом для погибели врага, и пробный шар, который должен был быть пущен завтра. Шар этот был еще не готов; но, как узнал Пьер, он строился по желанию государя. Государь писал графу Растопчину об этом шаре следующее:
«Aussitot que Leppich sera pret, composez lui un equipage pour sa nacelle d'hommes surs et intelligents et depechez un courrier au general Koutousoff pour l'en prevenir. Je l'ai instruit de la chose.
Recommandez, je vous prie, a Leppich d'etre bien attentif sur l'endroit ou il descendra la premiere fois, pour ne pas se tromper et ne pas tomber dans les mains de l'ennemi. Il est indispensable qu'il combine ses mouvements avec le general en chef».
[Только что Леппих будет готов, составьте экипаж для его лодки из верных и умных людей и пошлите курьера к генералу Кутузову, чтобы предупредить его.
Я сообщил ему об этом. Внушите, пожалуйста, Леппиху, чтобы он обратил хорошенько внимание на то место, где он спустится в первый раз, чтобы не ошибиться и не попасть в руки врага. Необходимо, чтоб он соображал свои движения с движениями главнокомандующего.]
Возвращаясь домой из Воронцова и проезжая по Болотной площади, Пьер увидал толпу у Лобного места, остановился и слез с дрожек. Это была экзекуция французского повара, обвиненного в шпионстве. Экзекуция только что кончилась, и палач отвязывал от кобылы жалостно стонавшего толстого человека с рыжими бакенбардами, в синих чулках и зеленом камзоле. Другой преступник, худенький и бледный, стоял тут же. Оба, судя по лицам, были французы. С испуганно болезненным видом, подобным тому, который имел худой француз, Пьер протолкался сквозь толпу.
– Что это? Кто? За что? – спрашивал он. Но вниманье толпы – чиновников, мещан, купцов, мужиков, женщин в салопах и шубках – так было жадно сосредоточено на то, что происходило на Лобном месте, что никто не отвечал ему. Толстый человек поднялся, нахмурившись, пожал плечами и, очевидно, желая выразить твердость, стал, не глядя вокруг себя, надевать камзол; но вдруг губы его задрожали, и он заплакал, сам сердясь на себя, как плачут взрослые сангвинические люди. Толпа громко заговорила, как показалось Пьеру, – для того, чтобы заглушить в самой себе чувство жалости.
– Повар чей то княжеский…
– Что, мусью, видно, русский соус кисел французу пришелся… оскомину набил, – сказал сморщенный приказный, стоявший подле Пьера, в то время как француз заплакал. Приказный оглянулся вокруг себя, видимо, ожидая оценки своей шутки. Некоторые засмеялись, некоторые испуганно продолжали смотреть на палача, который раздевал другого.
Пьер засопел носом, сморщился и, быстро повернувшись, пошел назад к дрожкам, не переставая что то бормотать про себя в то время, как он шел и садился. В продолжение дороги он несколько раз вздрагивал и вскрикивал так громко, что кучер спрашивал его:
– Что прикажете?
– Куда ж ты едешь? – крикнул Пьер на кучера, выезжавшего на Лубянку.
– К главнокомандующему приказали, – отвечал кучер.
– Дурак! скотина! – закричал Пьер, что редко с ним случалось, ругая своего кучера. – Домой я велел; и скорее ступай, болван. Еще нынче надо выехать, – про себя проговорил Пьер.
Пьер при виде наказанного француза и толпы, окружавшей Лобное место, так окончательно решил, что не может долее оставаться в Москве и едет нынче же в армию, что ему казалось, что он или сказал об этом кучеру, или что кучер сам должен был знать это.
Приехав домой, Пьер отдал приказание своему все знающему, все умеющему, известному всей Москве кучеру Евстафьевичу о том, что он в ночь едет в Можайск к войску и чтобы туда были высланы его верховые лошади. Все это не могло быть сделано в тот же день, и потому, по представлению Евстафьевича, Пьер должен был отложить свой отъезд до другого дня, с тем чтобы дать время подставам выехать на дорогу.
24 го числа прояснело после дурной погоды, и в этот день после обеда Пьер выехал из Москвы. Ночью, переменя лошадей в Перхушкове, Пьер узнал, что в этот вечер было большое сражение. Рассказывали, что здесь, в Перхушкове, земля дрожала от выстрелов. На вопросы Пьера о том, кто победил, никто не мог дать ему ответа. (Это было сражение 24 го числа при Шевардине.) На рассвете Пьер подъезжал к Можайску.
Все дома Можайска были заняты постоем войск, и на постоялом дворе, на котором Пьера встретили его берейтор и кучер, в горницах не было места: все было полно офицерами.
В Можайске и за Можайском везде стояли и шли войска. Казаки, пешие, конные солдаты, фуры, ящики, пушки виднелись со всех сторон. Пьер торопился скорее ехать вперед, и чем дальше он отъезжал от Москвы и чем глубже погружался в это море войск, тем больше им овладевала тревога беспокойства и не испытанное еще им новое радостное чувство. Это было чувство, подобное тому, которое он испытывал и в Слободском дворце во время приезда государя, – чувство необходимости предпринять что то и пожертвовать чем то. Он испытывал теперь приятное чувство сознания того, что все то, что составляет счастье людей, удобства жизни, богатство, даже самая жизнь, есть вздор, который приятно откинуть в сравнении с чем то… С чем, Пьер не мог себе дать отчета, да и ее старался уяснить себе, для кого и для чего он находит особенную прелесть пожертвовать всем. Его не занимало то, для чего он хочет жертвовать, но самое жертвование составляло для него новое радостное чувство.