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

Несколько дней назад сообщество математиков — специалистов в теории графов было взволновано сообщением о том, что выдвинутая Стефеном Хидетниеми (Stephen T. Hedetniemi) в 1966 году гипотеза оказалась неверной. Оказывается, хроматическое число тензорного произведения двух графов может быть меньше минимума хроматических чисел сомножителей, а не всегда равно этому минимуму, как когда-то предположил Хидетниеми. Как построить контрпример к этой гипотезе, придумал молодой московский математик Ярослав Шитов.

Окраска многих животных устроена причудливо и замысловато. На клеточном уровне ее возникновение описывается реакционно-диффузными моделями при помощи систем дифференциальных уравнений. В недавней работе группа ученых из Швейцарии детально изучила механизм формирования окраски глазчатых ящериц Timon lepidus. Оказалось, что это происходит по правилам, характерным для дискретного клеточного автомата, где в роли ячеек автомата выступают отдельные чешуйки кожи ящериц. Математическое моделирование позволило понять, что реакционно-диффузная система может порождать клеточный автомат благодаря особым условиям — в данном случае это подходящие размеры чешуек и толщина кожи ящериц внутри и на границе чешуек.

Рассмотрим сумму двух эрмитовых матриц A и B. Это снова будет эрмитова матрица. В 1912 году Герман Вейль задался таким вопросом: что можно сказать о ее собственных значениях, если известны собственные значения матриц A и В? Во-первых, ясно, что след A+B будет равен сумме следов исходных матриц; во-вторых, наибольшее собственное значение A+B не превосходит суммы наибольших собственных значений A и B. А какие еще есть ограничения? В 1962 году Альфред Хорн выписал ряд неравенств на собственные значения матриц A, B и A+B и сформулировал гипотезу о том, что это полный набор условий. В 1999 году А.А.Клячко свел эту гипотезу к так называемой гипотезе о насыщении. Они же предложили описание неравенств Хорна при помощи диаграмм или «сот», которые имеют самое прямое отношение к теории представлений полной линейной группы GL(n).

Некоторые комбинаторные схемы дают на выходе интересные выпуклые многогранники, имеющие отношение много к чему из современной математики. Перестановки дают пермутоэдр (перестановочный многогранник). Где он может пригодиться? (Конфигурационное пространство шарнирного многоугольника). Скобочные последовательности дают ассоциэдр (многогранник Сташефа). Зачем он нужен? («Чудесная» компактификация де Кончини–Прочезе.) Вторичный многогранник (secondary polytope Гельфанда–Капранова–Зелевинского) связан с совершенно иной комбинаторной схемой, и при этом обобщает предыдущие примеры.

Как мы узнаем, выпуклые многогранники можно складывать и перемножать между собой. Далее, выпуклые многогранники можно умножать на рациональные числа. И наконец, что несколько неожиданно, для выпуклых многогранников можно определить логарифм и экспоненту. Вооружившись этими умениями, мы построим математически богатый замечательный объект — градуированную алгебру над Q — алгебру многогранников Питера Мак Маллена. С помощью этой алгебры мы докажем теорему об f-векторе выпуклого многогранника. Эта алгебра хорошо «отражается» в теории алгебраических торических многообразий.

Курс представляет собой букет из трёх очень старых и трёх очень новых идей. Основной объект — число целых (т.е. с целыми координатами) точек в многограннике. Зачем нужны целые точки? Несколько примеров: многогранник Ньютона, Теорема Бриона — для начала без доказательства, просто в качестве фокуса, а также подсчёт целых метрических ленточных графов. Число целых точек в выпуклом многограннике ведёт себя как полином. Согласно конструкции, в полином, вычисляющий число целых точек, имеет смысл подставлять лишь положительные числа. Чтобы придать смысл отрицательной подстановке, нужны виртуальные многогранники. Двойственность Эрхарта и её естественное обобщение. Секрет фокуса Бриона.

Вот три тесно связанные между собой задачи, которые мы будем обсуждать: Как распрямить плотницкую линейку? Можно ли нарисовать на сфере правильно раскрашенный граф? Верна ли старая гипотеза А. Д. Александрова о характеризации сферы? Попутно будет сформулировано много задач разного уровня сложности (именно исследовательских задач, а не упражнений!). Часть из них — для умеющих и любящих программировать. В курсе будет много картинок.

Рассмотрим прямоугольник, составленный из маленьких правильных шестиугольных плиток. Подкинем для каждой из этих плиток монетку, и, если выпадет орел, объявим ее открытой, а иначе закрытой. С какой вероятностью от левого края прямоугольника до правого можно дойти путем, проходящим только по открытым плиткам? Этим и многими другими схожими вопросами занимается теория протекания. Ответ на вопрос о вероятности пробоя дается (на первый взгляд пугающей) формулой Карди, предсказанной им в 1991 г. из соображений конформной теории поля. Строго эта формула — в гораздо более приятно выглядящей переформулировке Л. Карлесона — была доказана лишь десять лет спустя С. К. Смирновым в его работах 2001-го года (одних из тех, за которые в 2010-м он получил премию Филдса). В нашем курсе мы, хоть и не в деталях, обсудим доказательство этой формулы — опирающееся на такую удивительную вещь, как дискретный комплексный анализ.

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

Квазипериодические функции: что это такое, откуда возникают, проблемы их изучения, как появляется топология и динамические системы. Лекцию читает Новиков Сергей Петрович, академик РАН, доктор физико-математических наук, профессор.

Лекцию читает Новиков Сергей Петрович, академик РАН, доктор физико-математических наук, профессор. Летняя школа «Современная математика», г. Дубна. 20 июля 2003 г.

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

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

Лекция будет посвящена некоторым нестандартным аспектам элементарной симплектической геометрии и линейной алгебры и их применению для нужд квантовой теории рассеяния. Для большинства математиков этот язык непривычен, поэтому все необходимые понятия будут введены самым элементарным образом.

Ж. Л. Лагранж доказал, что последовательность неполных частных (начиная с некоторого места) периодична, если и только если число 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 далеко не решён.

Число В вершин, число Р ребер и число Г граней выпуклого многогранника связаны соотношением В−Р+Г=2. Легко сообразить, что это широко известное утверждение не имеет прямого отношения к выпуклости: если на боку выпуклого многогранника сделать вмятину, то он перестанет быть выпуклым, а количество вершин, ребер и граней сохранится. В то же время для совершенно произвольного многогранника теорема неверна. В данном курсе мы выясним, в каких именно случаях эти утверждения верны и почему на самом деле это — одна и та же теорема. Также мы разберемся, как выглядят аналогичные утверждения для других поверхностей, и не только для поверхностей (а, например, для графов или для многомерной сферы).

В лекции будет сказано, что такое узлы (и их родственники — зацепления, косы, ленты), но вместо соответствующих теорий, будут рассказаны некоторые яркие «внешние» применения этих понятий, т. е. приложения к другим наукам. А именно: Индекс зацепления двух кривых и электромагнетизм; Перестройки по заузленным лентам и опровержения первоначального варианта его знаменитой гипотезы; Косы и оправдание существования позитрона (и вообще антимира); Заузленные ДНК; Простейшее зацепление и расслоение Хопфа.

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

Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. В виде проблемы она была сформулирована в 1852 году — и доказана в 1976-м лишь с помощью компьютера. Такое решение не всем понравилось, и некоторые до сих пор ждут доказательства, которое можно проверить без компьютера. Другие (как великий математик Владимир Воеводский) — наоборот, стали развивать автоматическую проверку правильности доказательств на компьютере… В курсе мы разберем доказательство теоремы о четырёх красках (это простая комбинаторика, доступная любому школьнику), а также обсудим сегодняшнее использование компьютера в математике (надо примерно знать, что такое компьютер).