Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Численные верхние оценки чисел Рамсея
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория графов
278 calificaciones
De la lección
Теория Рамсея
На заключительной лекции мы поговорим про теорию Рамсея. Вы узнаете много нового о знакомствах, о том, сколько раз можно в одном доказательстве применить принцип Дирихле и о том, что доказать существование графа и привести пример такого графа - это зачастую совсем разные по сложности задачи.
Conoce a los instructores
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте выведем из только что доказанной теоремы обещанное явное следствие — как
все таки оценивается число Рамсея.
Давайте еще раз я перепишу теорему, чтобы было легко выводить следствие.
R(s,t) мы доказали, всегда не превосходит R(s − 1,
t) + R(s, t − 1) в предположении,
что они существуют, но это индуктивное предположение, так что все в порядке.
А следствие, которое мы получим, совершенно замечательное,
потому что оказывается, все очень здорово: R(s,
t) не превосходит С из s + t − 2 ну, скажем,
по s − 1 или по t − 1, это совершенно симметрично,
ввиду известного комбинаторного тождества C из n по k = C из (n по (n − k)).
Почему это так: доказательство...
Ну это, естественно, тоже индукция.
Давайте сначала проверим базу индукции: R(1,
t) хотелось бы, чтобы не превосходило С из
1 + t − 2 по 1 − 1.
Но 1 − 1, друзья мои, это же ведь 0.
Поэтому совершенно уже не важно,
что написано у C-шки снизу: С из чего-либо по нулю — это 1.
И это правда, потому что мы знаем, что R(1, t) = 1.
Ну а симметричный случай, конечно, очевиден, потому что, как я сказал,
он симметричен.
Но, если хотите, давайте я его проверю.
Так, я только неудачно написал — здесь, наверное, лучше написать R(s,1).
То есть вместо t мы сейчас подставим 1,
у нас получится С из s − 1 по s − 1, это тоже, конечно,
равно 1, так что мы действительно получили то, чего и так знали.
Все верно, база индукции доказана.
Поскольку каждое из этих чисел, мы знаем, не превосходит 1, значит,
оно автоматически не превосходит и того, чего бы нам хотелось.
Теперь давайте предположим, что для R(s − 1, t) мы уже получили некую оценку,
а именно вот такую, и для R(s, t − 1) мы тоже получили такую оценку — ну,
с подстановкой туда соответствующих величин.
Давайте смотреть: мы знаем, что R(s,t) не превосходит
R(s − 1,t) + R(s,t − 1),
и про каждую из этих величин, согласно предположению индукции,
мы знаем следующее: первый из них оценивается как С из s − 1.
Видите, я вместо s (s − 1) подставил, плюс t − 2 по ну наверное,
s − 2, потому что я вместо s подставляю, опять таки, s − 1.
Ну и прибавить еще одну C-шку: С из s, наоборот,
+ t Ну давайте сразу напишем минус 3, потому что места мало,
понятно — мы вместо t пишем t − 1 и получаем здесь t − 3, соответственно.
Ну а здесь ничего не меняется, s − 1, оно, конечно, никуда не преобразуется,
потому что s у нас то же самое.
Вот. Значит,
применили наше индуктивное предположение,
а теперь надо вспомнить, чему равняется такая сумма двух C-шек.
Это то, что в любом моем стандартном
курсе комбинаторики называется вторым тождеством.
Первое — это то, что С из n по k = C из n по (n − k),
ну а второе тождество — это то, что называется треугольник Паскаля еще.
Это тождество, из которого строится треугольник Паскаля.
Здесь у нас, конечно, написано то же самое s + t − 3, что и вот тут.
И тут s + t − 3, и там s + t − 3.
Ну что, можно это, в свою очередь,
обозначить буквицей a, тогда здесь у нас тоже стоит буквица a та же самая.
Так?
Здесь...
А давайте вот так напишем: вот эта вот k...
Не было у нас еще k?
Не было.
Тогда вот это — k − 1.
То есть у нас получается С из a по k + C из a по (k − 1).
Ну вот это и есть тождество, которое создает треугольник Паскаля,
то есть в итоге мы получаем C из a + 1 по k, то есть,
C из s + t − 3 + 1, то есть − 2 по k,
где k это s − 1, что и требовалось доказать.
Вот смотрите сюда — индукция завершена благополучно.
Все. Это очень просто,
и это следует из треугольника Паскаля, по большому счету.
Вот. Давайте заметим, что, в частности,
конечно, R(3,3) не превосходит ввиду этой
оценки C из 4 по 2, ну а это есть 4!
/ 2!
2!, то есть 6 — мы вернулись к той оценке, с которой начинали.
Получается, что действительно рекурсия,
которую мы сейчас установили в общем случае — это такое абсолютно естественное,
прямое обобщение оценки из школьной задачи про то, что среди любых
шести человек либо трое попарно знакомы, либо трое попарно незнакомы.
Это вот частный случай доказанного нами результата.
Дальше можно специфицировать это на ситуации, когда s = t,
то есть, рассмотреть такое прямое, если угодно,
обобщение числа Рамсея R(3,3) — просто рассматривать одинаковые параметры.
Такие числа Рамсея в науке принято называть диагональными.
Это называется диагональное число Рамсея.
Диагональное число Рамсея.
Ну понятно, почему оно диагональное — оно стоит на диагонали у матрицы,
составленной из чисел, или у таблицы, как хотите, составленной из чисел Рамсея.
На диагонали находятся числа R(s,s).
Ну понятное дело, что R(s,s) не превосходят C
из 2s − 2 по s − 1.
ну а эта C-шка грубо, может быть достаточно грубо оценена сверху величиной
2 в степени 2s − 2, ну просто потому что сумма всех биномиальных коэффициентов...
сумма всех биномиальных коэффициентов — это как раз вот эта вот степень двойки,
вот она здесь написана.
Это сумма всех биномиальных коэффициентов, сумма всей строчки треугольника Паскаля.
Ну значит, каждый из этих биномиальных коэффициентов точно меньше, чем сумма.
Правда, вот этот вот биномиальный коэффициент, как нетрудно проверить,
самый большой,
поэтому в действительности он от этой величины не слишком сильно отличается.
Это тоже несложное упражнение, на котором я сейчас заострять внимание не буду.
Можно еще вот так написать: 4 в степени s − 1.
Вот, товарищи, опять в порядке развлекухи некой давайте я
вам сообщу такой удивительный совершенно факт: оказывается,
что, по большому счету, улучшить вот этот несложный результат,
который мы с вами доказали за вполне ограниченное время, человечеству с 1935
года — а ведь он был получен фактически в 1935 году Эрдешем и Секерешем — то есть,
получается, за прошедшие с тех пор уже 80 лет с лишним вот
человечеству этот результат сильно улучшить не удалось.
Ну, чуть-чуть его улучшить можно, конечно,
если просто аккуратнее посмотреть на асимптотику, как говорят, вот этой C-шки,
то есть посчитать там по формуле Стирлинга, как устроены факториалы.
Тогда получится чуть-чуть поменьше.
Но это все ерунда.
Есть известная проблема.
Давайте я порадую публику проблемой, которую никто не может решить до сих пор.
Известная проблема звучит так: докажите,
что существует такое δ, большее нуля,
существует такая константа δ, большая нуля,
с которой R(s,s) не превосходит 4 − δ в степени s.
Вот даже этого никто не может сделать.
Пусть δ там — одна милионная, и этого не удается доказать.
Есть такой, ну если хотите, исторический анекдот на эту тему.
Ну это, конечно, не анекдот прямо уж, но вот такой забавный факт, что ли.
Замечательный математик Эрдеш, как известно,
любил назначать цены за решение задач.
Он говорил: «Вот эту...
За решение этой моей задачи я бы дал пятьдесят долларов,
а за решение вот этой моей задачи я бы дал тысячу долларов».
Ну, таким образом он как бы оценивал, какая задача сложнее, а какая проще,
расставлял им баллы.
Денег у него своих не было, но были ученики, которые, в принципе,
были готовы давать деньги, и когда Эрдеш уже стал великим математиком, прославился,
и учеников у него были тысячи по всему миру, нашлись такие среди них,
которые стали за эрдешевские задачи реально раздавать людям деньги.
То есть, вот Эрдеш назначает цену, там через двадцать лет задачу кто-нибудь
решает, и денежка ему поступает от богатых учеников Эрдеша.
Вот среди таких учеников есть выдающийся специалист по теории Рамсея.
По-русски его принято вот так вот писать: Рональд Грэхем.
Ну, по-английски, он американец, обычно читается просто Грэм,
там это h не проговаривается никак.
Но факт тот, что вот есть такой замечательный математик.
Он очень много сделал для развития теории Рамсея, и, в частности,
вот за эту задачу он уже назначил цену сам.
Он сказал: «Я подобен Эрдешу, я могу назначать цены за задачи».
И ему показалось в какой-то момент, что это задача нетрудная.
И он, значит, назначил за нее цену в сто долларов.
Он сказал, что вот если вы найдете какое-нибудь δ,
я вам заплачу сто долларов.
И он упрямый тип — он до сих пор так от этой суммы отходить и не хочет.
То есть, 80 лет проблеме, никто не может найти такое δ, с которым это
неравенство выполнено, но он упрямо говорит: «Нет, это задача на сто долларов.
Вот я ее сам решать тоже не буду, я не знаю, как ее решать,
но вам нужна небольшая-небольшая идея.
И я вам заплачу сто долларов».
Ну, анекдот состоит в том, что, возможно, поэтому задача держится так долго.
Если бы он назначил 10 тысяч там или миллион, как некоторые, может быть,
кто-нибудь все-таки бы ее решил.
Но это шутка, конечно.
Не знаю.
Проблема в том, что вот никто такого δ отыскать не умеет, хотя я,
вслед за Грэмом, тоже вполне себе верю, что так и должно быть.
Вот.
Но помимо этой проблемы возникает и следующий вопрос.
Да, товарищи, вы меня можете спросить, вы уж извините,
но хоть какие-то понижения этой функции были?
Да, были.
Но если я сейчас их здесь выпишу, то будет миллион вопросов на форуме.
Вот, ну я, конечно, могу написать.
Ну пусть будет, ну почему нет.
Но вот самый лучший результат, который сейчас известен,
выглядит вот так: ≤ 4 в степени s
− 1 умножить на понижающую функцию какого-то вот
такого вида: ой кошмар, ой кошмар.
Вот такая страшная функция, где γ — это некоторая константа, большая нуля.
Но зато кому-то понятно, если сразу, но вот вы видите,
что понижение достаточно существенное, но никакая δ с ним не сравнится,
или наоборот, оно не сравнится ни с какой δ — оно слабее.
Вот подумайте над этим, те товарищи, кто не очень,
может быть, хорошо сейчас еще помнит...
Уже помнит анализ, или еще знает анализ — подумайте,
что на самом деле эта функция стремится к нулю,
вот эта функция, медленнее, чем любая константа в степени s.
Поэтому такого понижения в этом месте нет.
Но сто долларов автор этого результата не получил.
Зато этот результат опубликован в самом рейтинговом,
самом крутом математическом журнале, который существует на свете.
Это «Анналы математики» — журнал с самым высоким математическим рейтингом.
Там публикация занимает много лет.
И вот человек пробился — сто долларов не получил, зато прославился.
Ну а Грэм стоит на своем: сто доларов, не больше.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
