Теорема Брукса

[rus4]

В лаборатории Че проходит семинарам по доказательствам из Книги, как вошедшим в книгу Айгнера-Циглера, так и не вошедшим. Вчера Глеб Ненашев рассказал свою версию доказательства Ловаса теоремы Брукса, которого я раньше не знал

Comments

[russhatter]

Спасибо, очень чёткая идея.

[falcao]

Кажется, я после второго чтения уловил способ.

Тут встретилось несколько опечаток.

> степень вершины p строго меньше, чем p

Я так понимаю, должно быть "меньше чем d".

> Если же она соединена только с вершинами H'

Видимо, здесь должна идти речь об H~.

В порядке "оффтопа": мне тут попалась на днях такая задача, решения которой я пока не знаю. На плоскости дано конечное число прямых. Случай, когда все они проходят через одну точку, не рассматривается. Параллельных прямых тоже нет. Каждую прямую окрасили в один из двух цветов (скажем, красный или синий). Верно ли, что среди точек пересечения прямых обязательно найдётся "монохромная"? То есть такая, через которую проходят прямые только одного из цветов?

[rus4]

Спасибо.

верно

[falcao]

ЗдОрово! Спасибо за ссылку!

[falcao]

Заодно хочу спросить ещё об одной серии задач -- может быть, Вы про неё знаете.

Есть плоская фигура единичной площади. Она покрыта конечным числом каких-то "однотипных" фигур (правильных треугольников; квадратов; кругов; etc). Требуется выделить дизъюнктный набор этих фигур, покрывающих достаточно большую по площади часть этой фигуры. Интересуют верхние и нижние оценки. Скажем, в том варианте, в котором мне эта задача попалась, речь шла о правильных треугольниках с долей площади 1/10. Такая оценка у меня не получилась: я смог это доказать только для числа 0,06586. С другой стороны, для 1/6 есть очевидная верхняя оценка.

Буду признателен за любую информацию по этому вопросу.

[anonymous]

Ну, мне как нематематику кажется несколько искусственной и тяжеловесной такая обработка

[rus4]

Спасибо за комментарий.
Я попробую объяснить, почему так излагаю.
Цель не в том, чтобы доказать "как можно короче" (или "как можно длиннее"), а в том, чтобы включить доказательство в контекст, в котором оно возникает естественно. Многие очень короткие и ясные доказательства совершенно не понятно, откуда берутся (пример: доказательство Томассона списочной 5-хроматичности планарного графа). Я специально обращаю внимание на то, что граф заменяется на два, соответствующих стягиванию и удалению антиребра, потому что эта индукция работает в миллионе других случаев, и для осознающего суть хроматического многочлена разума она абсолютна естественна - а дальше уже дело техники, так или иначе всё быстро получится.

[nicka_startcev]

Можно вам задать оффтопический вопрос про ru-learnmaths?

я не математик, не студент.

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

задачи вроде бы несложные, но сравнительно громоздкие. Очень хочется или найти некий волшебный справочник по такого рода задачам, или переложить их на кого-нибудь в обмен, например, на некие мои услуги (программирование, аквариумистика, кулинария, 3д-печать, итп). Куда с этим стОит обращаться?

Например, сейчас меня беспокоит задача по решению 5-угольника. (дано 5 сторон, даны координаты 3 вершин (A,C,D) из пяти (A,B,C,D,E), надо найти 2 угла (C,D)) и я не знаю как к ней подступиться, даже если известно что 5-угольник выпуклый.