Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

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

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

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

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

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

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

Меня это удивляет. Я не понимаю.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 108 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →