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

[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]

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

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

[kot-begemot.livejournal.com]

Именно.

[avva.livejournal.com]

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

[faceted-jacinth.livejournal.com]

Строго говоря, откидывая "неслучайно выглядящие" результаты вы уменьшаете энтропию генератора (и стойкость криптоалгоритма).

[ex-leopolis-448.livejournal.com]

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

[dzz.livejournal.com]

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

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

[burrru.livejournal.com]

99.99% как физиков, так и математиков не несут никакой прикладной пользы и мало какую теоретическую. Они создают среду - не больше, не меньше. Чернозем.

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

Ну, а самое любопытное, без сомнения, это
http://en.wikipedia.org/wiki/An_Exceptionally_Simple_Theory_of_Everything
Идея абсолютно гениальная! По масштабу превосходит E=mc^2 и вполне наглядная при минимальном математическом образовании.

[posic.livejournal.com]

математики-теоретики на передовой современной науки <...>
1) не понимают даже друг друга зачастую
2) не несут никакой прикладной пользы

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.

[avva.livejournal.com]

Спасибо, это очень интересно (хоть мне и не хватает алгебраических знаний, чтобы даже приблизительно оценить работы Sara Billey, увы).

[inka-kakadu.livejournal.com]

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

[random-kori.livejournal.com]

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

[gaz-v-pol.livejournal.com]

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

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

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

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

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

[neatfires.livejournal.com]

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

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

[plus25c.livejournal.com]

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

[avva.livejournal.com]

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

[ahtolllka.livejournal.com]

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

[markvs.livejournal.com]

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

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

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

[avva.livejournal.com]

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

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

Спасибо!

[gt.livejournal.com]

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

[avva.livejournal.com]

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

[spartach.livejournal.com]

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

[avva.livejournal.com]

Географическое удобство :)

[silly_sad.livejournal.com]

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

[sowa.livejournal.com]

То, что Вы заметили - это отличительное свойство "венгерской", или Erdos-style математики, которая представляет собой огромный аморфный набор плохо мотивированных проблем. Не так давно в ЖЖ в разных журналах была разветвленная дискуссия на тему о том, хорошо это или плохо; см. ссылки в одном из моих последних постов.

Сейчас популярность этого предмета растет. Деньги, получаемые под предлогом приложений к computer science, играют немалую роль.

[avva.livejournal.com]

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

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

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

Для меня, наверное, важная разница заключается в том, что по крайней мере внутри себя они образуют стройную, отнюдь не аморфную структуру.

[parakhod.livejournal.com]

12 лет назад, когда мы ваяли один квест, я, к своему жуткому удивлению, обнаружил, что даже матёрые мехматовцы решают подобные задачи тупым перебором...
Если б не моя старая нелюбовь к математике, может быть и заинтересовался бы. А так, конечно, тема для журнала "Квант". Он жив ещё, интересно?

[algol78.livejournal.com]

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

[silly_sad.livejournal.com]

Готвальд Харди, вами бы гордился. Только применение это всё-таки неприятный и нежелательный побочный эффект.

[potan.livejournal.com]

Это последствия кризиса - от всего начинают ждать применимости в народном хозяйстве.

[vzakharov.livejournal.com]

вот уж от кого не ожидал такого замечания, так от вас

[avva.livejournal.com]

почему?

[turgutmakbak.livejournal.com]

Ну, вот я занимаюсь паттернами. Что сказать? Действительно, бывают статьи, высосаные из пальца, но в общем, если задуматься, о чем собственно, идет речь, то можно получить хорошие и довольно полезные результаты.

Ну, например, избегание паттернов можно рассматривать как частный случай вхождения некоторых классов изоморфизмов подпоследовательностей в последовательности. Тогда речь идет о комбинаторных статистиках и анализе их распределения в духе майора МакМахона и других. (Кстати, публикация глав его "Комбинаторного анализа" лет 100 назад тоже сопровождалась рецензиями типа "непонятно для чего это нужно и куда он с этим идет, но выглядит интересно, так что пусть он уже закончит").

Избегание паттернов, как точно заметил poslushnik, естественным образом возникает в многообразиях Шуберта и т.д. -- вот алгебраическая мотивация.

Кроме того, оно естественным образом возникает и в информатике. Например, еще у Кнута в 1-м или 3-м томе "Искусства программирования" показано, что сортируемость через 1 стек (бесконечной глубины) равносильно избеганию одного паттерна. Сортируемость через два стека -- тоже равносильно избеганию двух паттернов, но там доказательство намного сложнее и использует биекции с планарными картами и т.д.

Короче, мне тут надо уходить с работы через пару минут, но главная мысль моя такова, что у всего можно найти полезность, "если правильно сжижать", как пели Иваси.

[turgutmakbak.livejournal.com]

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

[pollak.livejournal.com]

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

[buddha239.livejournal.com]

Таких кусков выше крыши - но обычно в них и людей, и ресурсов негусто.

ПОВЕРЬТЕ !!!!!

[savvateev.livejournal.com]

Всё, что они делают, имеет самое непосредственное отношение к
практике! Моделирование интернета породило безумное количество
задач, казавшихся сверх-отвлечёнными и абстрактными.

Re: ПОВЕРЬТЕ !!!!!

[(Anonymous)]

Почему никто не написал задачи, связанные с мутациями оснований в ДНК?!