В сороковые годы XX века известными математиками П. Эрдёшом и Г. Хадвигером была поставлена одна из самых коротко формулируемых и в то же время одна из самых ярких и трудных задач комбинаторной геометрии — задача о нахождении хроматического числа евклидова пространства R^n, то есть минимального числа цветов, в которые можно так раскрасить точки пространства, чтобы точки, отстоящие друг от друга на расстояние 1, оказались раскрашенными в разные цвета. Эта задача до сих пор не решена даже для n=2, то есть для евклидовой плоскости, хотя простотой и естественностью своей постановки она сразу привлекла внимание всех математиков.

Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям человеческого мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В этом курсе будут обсуждены классические задачи и некоторые недавние результаты и тенденции, например, экстремальная теория графов.

Отрывок из книги математиков Андрея Райгородского и Нелли Литвак, посвященный истории онлайн-рекламы, нобелевскому лауреату Уильяму Викри и стоимости одного клика.

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

Будет рассказано, что такое математическая теория узлов и зачем нужны их инварианты. Задача (трехмерная) о классификации узлов будет сведена к чисто комбинаторной двумерной задаче с помощью изящного инструмента — операций Райдемайстера. Затем будет показано, как вычисляется знаменитый инвариант узлов — полином Александера–Конвея. Будет построен (со всеми доказательствами) еще более знаментый инвариант узлов — полином Джонса, за который в 1992 году австралийский математик Воан Джонс получил медаль Фильдса. Это будет сделано с помощью т.н. скобки Кауфмана, т.е. с помощью соображений, тесно связанных со статистической физикой. Мы научимся вычислять этот полином и докажем ряд его свойств.

В этом курсе будет рассказано о подстановочных системах довольно общего вида и о связанных с ними геометрических конструкциях, называемых фракталами Рози. Например, слово Трибоначчи 121312112131… состоит из цифр {1,2,3} и получается с помощью подстановки 1→12, 2→13, 3→1. Оказывается, что оно в некотором смысле устроено так же, как двумерный тор, разбитый на три части с фрактальной границей. (В то, что на первом рисунке изображена развёртка тора, трудно поверить, но тем не менее это так, и вторая картинка это иллюстрирует).

Ж. Л. Лагранж доказал, что последовательность неполных частных (начиная с некоторого места) периодична, если и только если число x — квадратичная иррациональность. Р. О. Кузьмин доказал, что в последовательности неполных частных почти любого вещественного числа доля d_m равных m неполных частных одинакова (для типичных вещественных чисел). Доля d_m убывает при m→∞ как 1/m^2 и её величина была предсказана Гауссом (ничего не доказавшим). В. И. Арнольда высказал (лет 20 назад) гипотезу, что статистика Гаусса–Кузьмина d_m выполняется также для периодов цепных дробей корней квадратных уравнений x^2+px+q=0 (с целыми p и q): если выписать вместе неполные частные, составляющие периоды всех цепных дробей корней таких уравнений с p^2+q^2≤R^2, то доля неполного частного m среди них будет стремиться к числу d_m при R→∞. В. А. Быковский со своими хабаровскими учениками доказали недавно эту давнюю гипотезу. Несмотря на это, вопрос о статистике не букв, а составленных из них слов [a_k+1, a_k+2,…, a_k+T], которые являются периодами цепных дробей каких-либо корней x уравнений x^2+px+q=0 далеко не решён.

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грехема в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. На самом деле вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грехема.

Классическая теорема Бойяи–Гервина (1830-е годы) утверждает, что любые два многоугольника равной площади равносоставлены друг с другом: первый многоугольник можно разрезать на конечное число многоугольных частей и затем сложить из этих частей второй многоугольник. Ещё Гаусс задавал вопрос, верно ли аналогичное утверждение для многогранников. А именно, его интересовало, можно ли доказать стандартную формулу для объёма пирамиды (одна треть произведения длины высоты на площадь основания) без использования предельного перехода, то есть разбив пирамиду на конечное число кусков, из которых можно сложить прямоугольный параллелепипед.

Сколькими способами можно раскрасить грани кубика, если есть три краски? Два варианта раскраски считаются разными, если один нельзя получить из другого переворачиваниями кубика. Грань красится целиком в один цвет. Описанная выше ситуация довольно типична, и потому нам бы хотелось найти какой-нибудь метод, который позволил бы сводить подобные вопросы к не слишком громоздкому перебору. Удивительным образом, на помощь приходит теория групп и так называемая формула Бернсайда.