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

[avva]

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

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

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

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

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

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

Comments

[vzakharov.livejournal.com]

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

[avva.livejournal.com]

почему?

[vzakharov.livejournal.com]

Сложно точно сказать. Мне кажется, что математика красива сама по себе, и без приложений. Мне казалось, что и вам тоже

[avva.livejournal.com]

Конечно. Вы путаете две очень разные вещи, по-моему. Взгляните на второй абзац моего ответа юзеру sowa выше.

[neatfires.livejournal.com]

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

[avva.livejournal.com]

горизонт неограниченно широк, это по-моему очевидно.

[neatfires.livejournal.com]

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

[avva.livejournal.com]

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

[neatfires.livejournal.com]

О. Вот теперь ясно. Хотя я предполагал, что речь идет о вопросах с ответами, раз их поднимают на университетском курсе.