Продолжим?

Представим себе, что у нас векторное поле v задано не на плоскости, а на какой-то ориентированной поверхности S — сфере, торе, кренделе, и т. д. То есть нам дана поверхность S, и в каждой точке p\in S задан вектор v(p), касательный к S в этой точке. Если брать аналогию с векторным полем как набором скоростей ветра — то ветер не дует ни вверх, ни вниз, а в каждой точке по касательной к Земле в этой точке.

Теперь, если кривая γ «большая», мы не можем сравнивать направления векторов в разных её точках — касательные плоскости в них разные. А вот если она нам задана вместе с картой, целиком кривую содержащей — тогда можно перенести векторное поле на карту, и индекс опять определён. И от выбора карты результат будет зависеть: индекс векторного поля вдоль экватора, посчитанный с помощью карты-северного полушария, отличается от индекса, посчитанного в южном полушарии.
Но индекс особой точки всё ещё определён (ибо маленькая окружность заключена в карте).

Так вот, есть такое замечательное утверждение:

Предложение. Сумма индексов особых точек векторного поля на S, у которого особых точек конечное число — от выбора такого поля не зависит.
Набросок доказательства. Если деформировать поля друг в друга, оставаясь в классе полей с изолированными особыми точками, то сумма остаётся постоянной в процессе деформации. Действительно, в любой момент разрежем поверхность на маленькие кусочки, границы которых в текущий момент не проходят через особые точки поля. Тогда, в силу теоремы о сумме индексов, вся сумма равна сумме индексов по границам кусочков (закрываемых картами, содержащими кусочки целиком). А каждый из таких индексов при малом возмущении не меняется. Так что сумма индексов — локально-постоянная функция; а значит, она и просто константа.

Остаётся убедиться, что любые два поля перетаскиваются одно в другое. Ну и для этого можно сначала соединить любые два векторных поля u и v просто отрезком
u_t(p)=t*u(p) + (1-t)*v(p), t\in [0,1].
А потом, если этот путь от u_0=u к u_1=v не работает (в какой-то момент t у поля u_t есть неизолированные особые точки), возмутить его, заменив на близкий, но «типичный»: наличие неизолированной особой точки это очень, очень сильное вырождение.

А чему равна эта сумма? Ответ очень красивый:

Теорема Пуанкаре-Хопфа. Сумма индексов особых точек векторного поля с изолированными особыми точками на замкнутом ориентированном многообразии M равна эйлеровой характеристике многообразия χ(M).

(Она справедлива для любой размерности M, но у нас пока что индекс точки определён только для поверхности, так что давайте я пока продолжу, как будто M это поверхность.)

Доказательство. Мы уже убедились, что сумма не зависит от выбора поля. Остаётся построить поле, у которого ответ будет точно равен χ(M). Давайте триангулируем M и возьмём поле, у которого особые точки — по одному источнику в центре каждого треугольника, по седловой точке в середине каждого ребра, и по стоку в каждой вершине триангуляции (см. рис. ниже).
Индексы источника и стока равны по +1, у седловой точки он (-1), так что сумма индексов как раз и будет равна эйлеровой характеристике,
В-Р+Г= χ(M).

Собственно, мы только что доказали теорему о причёсывании ежа: эйлерова характеристика сферы равна 2 (классическая формула Эйлера для многогранников, В-Р+Г=2 !), так что сумма индексов особых точек должна быть равна 2. И значит, хотя бы одна особая точка должна быть (сумма пустого множества равна 0).

Warning/disclaimer: уровень сложности начинает повышаться.

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

Пусть у нас есть отображение f:M->M, и у него есть изолированная неподвижная точка p. Тогда рядом с ней можно взять локальные координаты (карту) и рассмотреть векторное поле v_f, «соединяющее» каждую точку x с f(x). У этого поля p будет изолированной особой точкой => можно рассмотреть его индекс.

Определение. Индекс изолированной неподвижной точки p для отображения f — это её индекс для этого векторного поля v_f:
ind_f (p) := ind_{v_f}(p).

Несложно убедиться, что это определение корректно — если мы используем другую карту, индекс будет тем же самым.

Но у нас уже нет глобального векторного поля: если x и f(x) «далеко» друг от друга, то неясно, как именно их соединять. Скажем, если мы на торе — обходить ли «по» или «против» меридиана?

Так что сумма индексов неподвижных точек отображения f уже не обязана быть равна эйлеровой характеристике. А чему она будет равна?

Ответ на этот вопрос даёт формула Лефшеца.

Выглядит она так. Раз отображение f действует на многообразии M — оно действует и на всех k-мерных гомологиях
H_k(M,\R)
(которые мы будем рассматривать с вещественными коэффициентами, так что это векторное пространство).

Слово «гомологии» заслуживает отдельного комментария, но если вы с ними не сталкивались — давайте временно ограничимся тем, что это какие-то векторные пространства, сопоставленные многообразию, и измеряющие, насколько в нём есть что-то нетривиальное «в размерности k». Например, у сферы с g ручками нуль-мерные гомологии это одномерное пространство (порождённое «точкой»), двумерные гомологии это тоже одномерное пространство (порождённое «всей поверхностью»), а вот одномерные гомологии это пространство размерности 2g (порождённые обходами «вдоль» и «поперёк» каждой из ручек — или, что то же самое, «параллелями» и «меридианами» каждого из g торов, как связную сумму которых можно представить поверхность).

Так вот — отображение f действует на каждом из пространств k-мерных гомологий как линейное преобразование. А с линейным преобразованием много чего связано — в частности, можно рассмотреть след
tr (f_* , H_k(M,\R))

Давайте посмотрим на знакопеременную сумму таких следов. Оказывается, это и есть ответ!

Теорема (формула Лефшеца).
\sum_{f(p)=p} ind_f(p) = \sum_{k=0}^n tr(f_* , H_k(M,\R)).

То есть — сумма индексов неподвижных точек отображения определяется тем, как именно оно «перекручивает» многообразие. Красиво, правда?

Пример. Возьмём векторное поле v и «проедем» вдоль него небольшое время t_0 — получив диффеоморфизм f. Его неподвижные точки это в точности особые точки v (если время было достаточно малым, чтобы ни одну периодическую орбиту мы не успели полностью проехать). И индексы у них для отображения и для векторного поля одни и те же. Так что по теореме Пуанкаре–Хопфа сумма их индексов равна эйлеровой характеристике.

С другой стороны, заметим, что f гомотопно тождественному отображению (что f в тождественное отображение «можно перетянуть»). Действительно, достаточно рассмотреть семейство сдвигов вдоль того же векторного поля v за разные времена t. При t=0 это тождественное отображение, а при t=t_0 — наше f. Вот мы непрерывно и перетянули f в id.

А гомотопные отображения одинаково действуют на гомологиях. Так что для такого f его действие на каждых гомологиях просто тождественно, и значит, каждый след это просто размерность соответствующего пространства гомологий. А знакопеременная сумма размерностей пространств гомологий действительно равна эйлеровой характеристике!

P.S. Несколько ссылок про гомологии:
- курс В. А. Васильева «Гомологии, наборы плоскостей и формула включений-исключений» в ЛШСМ-2011: https://www.mathnet.ru/present3568
- книга В. В. Прасолова «Элементы теории гомологий», МЦНМО, 2006 https://old.mccme.ru/free-books/prasolov/homol.pdf
- курс Г. Ю. Паниной в ЛШСМ-2023: https://old.mccme.ru//dubna//2023/courses/panina.html

В пятницу 17 мая в 19:00 мск мы побеседуем в прямом эфире с Сергеем Александровичем Дориченко!

Сергей Александрович является председателем жюри международной олимпиады «Турнир городов», преподавателем математики 179-й школы, создателем журнала «Квантик» и потрясающим популяризатором математики. Мы уверены, что разговор будет интересный 🙂

Узнаем у Сергея Александровича:
— как заинтересовать ребёнка математикой,
— откуда ежегодно на «Турнире городов» так много классных задач, а на «Летней конференции Турнира городов» — так много классных проектов,
— тяжело ли работать в редколлегии журнала «Квант»,
— как в 2011-м году родилась идея создать журнал «Квантик» и как он развился за эти 13 лет,
— действительно ли математика похожа на музыку,
— важно ли интересоваться не только математикой и быть разносторонним человеком,
— и многое другое.

Ссылка на эфир появится в нашем канале в пятницу. Оставляйте в комментариях под этим постом интересующие Вас вопросы!

Подписаться на «Математические кружки»

#мт_интервью

О, и есть запись: https://www.youtube.com/watch?v=XicGYyhC9CQ

А ещё я хочу воспользоваться этим случаем, чтобы посыпать голову пеплом. Все эти годы, когда я хотел найти что-то конкретное из вышедшего в Квантике, я просто пытался гуглить — а если знал год, то переходил по ссылке «Архив» на их главной странице. Что было совсем не всегда удобно.
И все эти годы, на самом виду, там висела ссылка на рубрикатор! По которой я почему-то скользил взглядом… и не пытался посмотреть, «а что там?».

То есть, если хочется перечитать (отличный!) цикл статей Валерии Сироты про экскурсию по Солнечной системе, или найти рассказ Ивана Высоцкого про количество блюд из курицы и рыбы на борту самолёта (1 + 2, применение центральной предельной теоремы, если говорить на языке высокой науки!) — это делается в пару кликов. Кстати, я заодно обнаружил, что в цикле-экскурсии есть и статья про Землю, Луну и приливы — которую я почему-то тогда пропустил.
В общем — пользуйтесь!

https://www.shawprize.org/laureates/2024-mathematical-sciences/

The Shaw Prize in Mathematical Sciences 2024 is awarded to Peter Sarnak, Gopal Prasad Professor, School of Mathematics, Institute for Advanced Study and Eugene Higgins Professor of Mathematics, Princeton University, USA, for his development of the arithmetic theory of thin groups and the affine sieve, by bringing together number theory, analysis, combinatorics, dynamics, geometry and spectral theory.

Про формулу Лефшеца у меня в планах ещё два рассказа, но пока я их пишу — напишу чуть-чуть про другое.

Вот есть проблема 4 красок. Ну и наверное, все знают, что она решена, и решена с заметным применением компьютера для перебора вариантов.

А что, если поменять формулировку вопроса? Раньше у картографа был один набор из 4 цветов, и он пытается раскрасить все страны в эти цвета так, чтобы не было соседних стран, раскрашенных одним цветом.

Представим себе, что сначала картограф спрашивает у каждой страны набор из k цветов, которые эту страну устраивают. А то раскрасишь тут Тридевятое королевство в оранжевый цвет, а король возмутится, что это-де цвет любимой виверны кого-то из его родственников, которая у него все пряники как-то раз сожрала. И всё, несдобровать картографу.

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

Ну и вопрос тот же самый — какое число вариантов цветов k нужно спрашивать картографу, чтобы уж точно получилось раскрасить карту?

Собственно, совершенно необязательно работать именно с картой — такой же вопрос можно задать про любой граф. А именно:

Определение. Граф называется k-выбираемым (k-choosable), если для любого способа сопоставить каждой его вершине набор из k «разрешённых» цветов его вершины можно раскрасить так, чтобы каждая вершина была раскрашена в один из соответствующих цветов, и соседние вершины были бы раскрашены в разные цвета.

Рассматривать такие вопросы предложили в конце 1970-ых Визинг и Эрдёш, Рубин и Тэйлор; см. P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs и В. Г. Визинг, Раскраска вершин графа в предписанные цвета, 1976.

На первый взгляд (особенно, если начинать с задачи четырёх красках) может показаться, что это лишнее усложнение: ведь если наборы цветов в разных вершинах разные, казалось бы, раскрасить будет даже проще? Не будет ли наихудшей ситуацией, если списки цветов во всех вершинах просто одинаковы (ну и тогда наименьшее k будет просто хроматическим числом графа)?

Но оказывается, что нет — наименьшее k может быть (сильно) больше хроматического числа!

Скажем, вот такой пример приводят Эрдёш, Рубин и Тэйлор в своей статье: возьмём 6 вершин, соответствующих графу карты, которую образуют клетки прямоугольника 2x3 — этот граф очевидно, двудольный, их можно раскрасить «шахматным» образом. Так что хроматическое число такого графа равно 2.

Но этот граф не является 2-выбираемым! Действительно, сопоставим каждой из двух клеток центрального столбца наборы {1,2}, так что при правильной раскраске одна из них должна быть раскрашена в цвет 1, а другая в цвет 2.
Теперь пусть в левом столбце верхней клетке соответствует набор {1,3}, нижней {2,3}, а в правом — наоборот. Тогда левый столбец нам помешает раскрасить центральный как « 1 над 2 » (потому что тогда для обеих клеток левого останется только цвет 3), а правый — помешает « 2 над 1 » (потому что тогда такая же проблема будет в правом).

Image credit: P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference in Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer. XXVI, p. 125-157, Utilitas Math., Winnipeg, Man., 1980.

Давайте теперь вернёмся к модифицированной задаче четырёх красок. Что будет, если каждая страна сообщает свой набор из k красок — иными словами, что можно сказать про choice number для всевозможных плоских графов?

Эрдёш, Рубин и Тэйлор всё в той же работе предположили, что для такой постановки правильным ответом будет не k=4, а k=5. И это и впрямь оказалось так!

В 1993 году Margit Voigt построила пример плоского графа с 238 вершинами, которым сопоставлены списки из 4 цветов так, что сделать правильную раскраску невозможно. И это, несмотря на большое количество вершин, вполне обозримая конструкция: несколько относительно небольших графов, которые вклеиваются в оставленные для них места на следующих этапах конструкции. Собственно — вся статья это всего 5 страниц!

И почти одновременно Carsten Thomassen доказывает, что 5 цветов от каждой страны достаточно. Собственно, его заметка 1994 года (всего на полторы страницы!) называется «Every planar graph is 5-choosable», и её аннотация говорит сама за себя:

We prove the statement of the noscript, which was conjectured in 1975 by V. G. Vizing and, independently, in 1979 by P. Erdös, A. L. Rubin, and H. Taylor.

А ещё — несколько лет спустя, в 1996 году пример плоского графа с меньшим числом вершин (всего 63) и сопоставления 4-элементных множеств цветов его вершинам, из которого нельзя выбрать правильную раскраску, построила будущая филдсовская медалистка, а тогда ещё только студентка Мариам Мирзахани (совсем незадолго до того, в 1994 и 1995 годах, выигравшая золото на IMO). И он совсем обозримый — умещается на страницу (см. картинку). Более того, этот же пример несложно правильно раскрасить в 3 цвета — так что из него следует и отрицательный ответ на вопрос «А вот если плоский граф можно раскрасить в 3 цвета, будет ли он обязательно 4-выбираемым?».

References:

[1] M. Voigt, List colourings of planar graphs, Discrete Mathematics
120 (1993), pp. 215-219.

[2] C. Thomassen, Every Planar Graph Is 5-Choosable, Journal of Combinatorial Theory, Series B, 62:1 (1994), pp. 180-181.

[3] Mirzakhani, Maryam. A small non-4-choosable planar graph. Bull. Inst. Combin. Appl., 17 (1996), pp. 15-18.

https://youtu.be/Phscjl0u6TI

в порядке картинок по выходным — ролик “How Kepler Actually Discovered his Laws”

задача Ф.Петрова с ВсОШ-2007: доказать, что цикл длины 100 является списочно раскрашиваемым в 2 цвета — или, другими словами,

если каждой вершине 100-угольника написано по два различных числа, то можно так вычеркнуть по одному числу в каждой вершине, чтобы оставшиеся числа в каждых двух соседних вершинах были различными

доказать это можно так

рассмотрим многочлен
P:=(x1-x2)(x2-x3)(x3-x4)…(x100-x1)

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

а это следует из того, что коэффициент при мономе x1 x2 … x100 ненулевой

(
действительно, пусть для переменной x1 разрешены значения a и b — тогда перейдем от многочлена P(x1,…) к многочлену P(b,…)-P(a,…); потом сделаем то же по следующей переменной и т.д.

если для каждого из выборов значение P нулевое, то мы в итоге получим 0

с другой стороны, эта операция аддитивная, на мономе x1 x2 … x100 она ненулевая, а на всех остальных мономах из P нулевая — так как все они имеют нулевую степень хотя бы по одной переменной

противоречие
)

доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и