узоры в перестановках (математическое)

[avva]

Я не понимаю комбинаторику.

В этом семестре я хожу вольнослушателем на курс "вероятностные методы в комбинаторике" в Тель-Авивском университете (ведет Нога Алон). Просто так, интереса ради; вообще-то я не учусь, а работаю на полную ставку. После первых четырех лекций у меня складывается смешанное отношение к предмету. Методы, которые мы изучаем, очень интересны и красивы; но вопросы, на которые они помогают ответить, кажутся очень слабо мотивированными, и в большинстве случаев не связанными друг с другом и чем-либо еще. Есть исключения - напр. интересные фундаментальные вопросы о графах, числа Ramsey итп. - но это именно исключения.

Пару недель назад у меня никак не получалось решить задачу из домашнего задания, связанную с перестановками строк матрицы (вот условие задачки, вдруг кому интересно: доказать, что существует постоянная c > 0, так что для любого N и любой действительной матрицы NxN, в которой все числа разные, есть перестановка строк, после которой ни в одном столбце нет возрастающей подпоследовательности длиной c*sqrt(N)).

Я стал искать в сети статьи и материалы, связанные с подпоследовательностями в перестановках. И обнаружил, к своему удивлению, что есть целое отдельное поле исследований, называется pattern avoidance in permutations, которое занимается следующим вопросом. Пусть задана перестановка над (1...k) (узор, "паттерн"). Сколько есть перестановок над (1...n), n > k, в которых нет подпоследовательности, повторяющей порядок узора, и что можно о них сказать?

Оказывается, этим вопросом занимается куча людей. В нем есть сложные результаты, гипотезы, нерешенные проблемы, гора статей, ежегодные конференции. Вместе с тем мне не удалось обнаружить ни одного серьезного применения этих результатов или идей из этой области где-либо еще - я не говорю о "реальном мире", конечно - где-либо еще в математике или компьютерных науках. Может, я неправ, и такие серьезные и важные применения есть? Или их нет, и действительно, как это видится мне, это совершенно изолированное поле деятельности, sui generis, интересное лишь постольку, поскольку кому-то интересно знать, сколько перестановок избегают данный узор?

Меня это удивляет. Я не понимаю.

Comments

[squadette.livejournal.com]

может я чего не понимаю, но по-моему это нужно для хороших псевдо-случайных генераторов

и в криптографии

[ex-leopolis-448.livejournal.com]

очень часто и много слышал от знакомых физиков, что математики-теоретики на передовой современной науки зашли в такие глубокие и специализированые дебри, что:
1) не понимают даже друг друга зачастую
2) не несут никакой прикладной пользы

[poslushnik.livejournal.com]

Pattern avoidance naturally appears in Schubert calculus and Kazhdan-Lusztig theory, see for example works of Sara Billey. For example smoothness of Schubert varieties can be characterized by avoidance of certain patterns. Results of this flavor in my opinion are often deep and beautiful.

You are right however that most of pattern avoidance questions studied do not come from any question in other area of mathematics. Such study is indeed not very well motivated.

In general with combinatorics one should distinguish two almost unrelated kinds: algebraic, that studies enumerative questions coming from from other areas, and non-algebraic, often called Erdos-style. The first type of combinatorics is intimately related with many other areas and does not suffer from lack of motivation. The second kind very often is locked in itself. There are notable exceptions however, for example many things Terry Tao does can be viewed (I think) as very high level Erdos-style combinatorics.

[kot-begemot.livejournal.com]

Именно.

[inka-kakadu.livejournal.com]

распознавание образов

[gaz-v-pol.livejournal.com]

Ну, комплексные числа тоже долгое время считались не имеющими применения в хозяйстве, а прошло 300 лет, начали самолёты и подводные лодки строить - оказалось, что гидро- и аэродинамика на языке этих странных чисел описывается проще...

Много лет считали, что теория чисел не имеет и никогда не будет иметь приложений. Кому какое дело до того, как данное большое число разлагается на простые множители? Ан нет, изобрели односторонние функции и стали в криптографии использовать...

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

Может быть, и до узоров в подпоследовательностях дойдёт...

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

[plus25c.livejournal.com]

Теоретическая математика всегда опережала прикладные нужды на несколько сот лет. Удивительно, что вы раньше с этим не столкнулись..

[ahtolllka.livejournal.com]

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

[markvs.livejournal.com]

1. Проще всего спросить самого Ногу. Он точно знает где все это применяется.

2. На конгрессе в Мадриде, 2006, Ричард Стенли делал пленарный доклад про это. Доклад должен быть в сети. Правда, мне он не показался очень интересным, как раз из-за отсутсвия мотивации. Хотя связи с алгоримом RSK там обсуждались.

3. Основные работы Окунькова тоже связаны с перестановками, у него (с Некрасовым) есть применения к физике. Он за это получил премию Филдса (тоже в Мадриде). Есть еще связи со случайными матрицами (а значит - со всей остальной математикой, включая теорию чисел).

[gt.livejournal.com]

Применяется в поточной криптографии и в связи. Например, некоторые паттерны непригодны для кодирования сигнала, если после них идёт что-то типа NRZ.

[dzz.livejournal.com]

Забавно, слышал то же самое про физиков-теоретиков из разных областей, в особенности в отношении квантовой и астрофизики :)

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

[random-kori.livejournal.com]

Я имею некое отношение к науке распознавания образов. Но что-то вот так сходу не могу придумать/вспомнить задачу где такая комбинаторика была бы полезна.
Не могли бы вы привести более конкретный пример? Действительно очень интересно.

[neatfires.livejournal.com]

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

Живя в Израиле, я на этот барьер натыкаюсь на каждом шагу. Например, один мой сокурсник из нерусскоговорящих израильтян, в целом сообразительный и не лишенный воображения, совершенно не понимает смысл существования худ. литературы, любые попытки объяснить наталкиваются на отторжение; то же самое с математикой - ему, вообще-то, нравится, но смысла изучать сложные части матанализа не видит. Все утыкается в вопрос: "а зачем мне это надо, если я буду работать программистом?" И это не единичный случай: здесь вообще практически никто и не думает о том, что можно без какой-либо конкретной цели и временных рамок учиться тому, на что есть время - просто ради интеллектуального развития. Мне кажется, это просто другая грань той же проблемы.

[sereshka.livejournal.com]

Ваше мнение о западной культуре не совсем верно. Такое агенство, как американский NSF (National Science Foundation), например, принципиально отказывается финансировать проекты, имеющие прямое практическое применение. Ваш взгляд, скорее, характиризует позицию частных компаний, но в больших кампаниях, таких как IBM, обязательно есть отдел фундаментальных исследований.

[neatfires.livejournal.com]

Вы правы, не все черно-белое. Я не имел в виду, что на западе вообще нет чистой науки или что там не читают литературу. Просто градация отличается.

[avva.livejournal.com]

А нельзя ли чуть подробнее? Не очень вижу связь между понятной практической проблемой избегать определенных паттернов символов в потоке, и математическим вопросом о подпоследовательностях (т.е. необязательно подряд) внутри перестановки (т.е. обязательно разных символов) фиксированного набора.

[spartach.livejournal.com]

Эх, вот так просто ходить на курс Алона. Здорово!

[avva.livejournal.com]

Я тоже считаю, что вы слишком преувеличиваете.

Возможно, тут играет роль selection bias следующим образом. В советском обществе сугубо прагматичный человек, стремясь добиться высокого статуса, почти всегда присоединялся к идеологической структуре общества - становился комсомольским деятелем, профсоюзным активистом, или наоборот стремился работать в торговле - но так или иначе выходил из рядов, условно говоря, "интеллигенции". Поэтому когда в СССР вы смотрели вокруг, думая о том, кто чем интересуется, то видели в основном людей, которых интересовала не только прагматика. Вся страна отнюдь не записалась в мечтатели, только небольшая ее часть; но почти весь ваш круг общения был из этой части.

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

[avva.livejournal.com]

Честно говоря, не вижу, как и зачем. В псевдо-случайных генераторах важно не повторять паттерны, но это совсем не то же, что избегать данного паттерна в фиксированной перестановке. То, что в математической задаче подпоследовательность может быть "разбросана" внутри перестановки, т.е. не идти подряд, тоже вносит меру случайности, никак не связанной с наличем/отсутствием порядка у псевдо-случайного генератора. Кроме того, я не уверен, что скажем выбранные подряд N случайных чисел от 0 до 1 будут распределены в своем порядке как случайная перестановка из N.

[nechaman]

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

[neatfires.livejournal.com]

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

[neatfires.livejournal.com]

Я уже ответил выше, что не все черно-белое. Но в Союзе гораздо реже случалось, что студент хорошего университета не видит смысла в общем развитии. Там это как-то ровнее шло. Взять ту же литературу - немыслимо представить интеллигента, не читающего книжки. А здесь - пожалуйста, сколько угодно; в лучшем случае томик Стивена Кинга, soft-cover.

[avva.livejournal.com]

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

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

[avva.livejournal.com]

1. Не уверен, что его это интересует, хотя в любом случае наверняка знает, вы правы. Я спрошу у него.

2. Нашел эту статью, спасибо; http://www-math.mit.edu/~rstan/papers.html , сделать поиск на Madrid. Она почти вся о частном случае строго возрастающих/убывающих паттернов, который, понятно, пользуется независимым интересом, и тесно связан с RSK, как вы отметили (я на самом деле не знаю ничего про Young tableux и RSK, хотя давно хочу прочитать; может, соберусь как раз ввиду этого). Об общем случае pattern avoidance - меня именно это больше всего занимает, т.к. тяжелее представить связь с другой математикой, чем в частном случае возрастающей подпоследовательности - Стенли говорит, и упоминает, что о нем существует огромная литература и он бурно растет, но ничего не говорит о приложениях.

Спасибо!

[avva.livejournal.com]

Это не совсем тот случай; речь идет о влиянии и связях внутри самой математики.