(Построение векторного поля по триангуляции поверхности)
Математические байки
Продолжим? Представим себе, что у нас векторное поле v задано не на плоскости, а на какой-то ориентированной поверхности S — сфере, торе, кренделе, и т. д. То есть нам дана поверхность S, и в каждой точке p\in S задан вектор v(p), касательный к S в этой точке.…
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->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
Выглядит она так. Раз отображение 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
Wikipedia
Число Лефшеца
Число Лефшеца — определённая целочисленная характеристика отображения топологического пространства в себя.
Forwarded from Математические кружки | «МТ кружки»
В пятницу 17 мая в 19:00 мск мы побеседуем в прямом эфире с Сергеем Александровичем Дориченко!
Сергей Александрович является председателем жюри международной олимпиады «Турнир городов», преподавателем математики 179-й школы, создателем журнала «Квантик» и потрясающим популяризатором математики. Мы уверены, что разговор будет интересный 🙂
Узнаем у Сергея Александровича:
— как заинтересовать ребёнка математикой,
— откуда ежегодно на «Турнире городов» так много классных задач, а на «Летней конференции Турнира городов» — так много классных проектов,
— тяжело ли работать в редколлегии журнала «Квант»,
— как в 2011-м году родилась идея создать журнал «Квантик» и как он развился за эти 13 лет,
— действительно ли математика похожа на музыку,
— важно ли интересоваться не только математикой и быть разносторонним человеком,
— и многое другое.
Ссылка на эфир появится в нашем канале в пятницу. Оставляйте в комментариях под этим постом интересующие Вас вопросы!
Подписаться на «Математические кружки»
#мт_интервью
Сергей Александрович является председателем жюри международной олимпиады «Турнир городов», преподавателем математики 179-й школы, создателем журнала «Квантик» и потрясающим популяризатором математики. Мы уверены, что разговор будет интересный 🙂
Узнаем у Сергея Александровича:
— как заинтересовать ребёнка математикой,
— откуда ежегодно на «Турнире городов» так много классных задач, а на «Летней конференции Турнира городов» — так много классных проектов,
— тяжело ли работать в редколлегии журнала «Квант»,
— как в 2011-м году родилась идея создать журнал «Квантик» и как он развился за эти 13 лет,
— действительно ли математика похожа на музыку,
— важно ли интересоваться не только математикой и быть разносторонним человеком,
— и многое другое.
Ссылка на эфир появится в нашем канале в пятницу. Оставляйте в комментариях под этим постом интересующие Вас вопросы!
Подписаться на «Математические кружки»
#мт_интервью
Математические байки
В пятницу 17 мая в 19:00 мск мы побеседуем в прямом эфире с Сергеем Александровичем Дориченко! Сергей Александрович является председателем жюри международной олимпиады «Турнир городов», преподавателем математики 179-й школы, создателем журнала «Квантик»…
О, и есть запись: https://www.youtube.com/watch?v=XicGYyhC9CQ
А ещё я хочу воспользоваться этим случаем, чтобы посыпать голову пеплом. Все эти годы, когда я хотел найти что-то конкретное из вышедшего в Квантике, я просто пытался гуглить — а если знал год, то переходил по ссылке «Архив» на их главной странице. Что было совсем не всегда удобно.
И все эти годы, на самом виду, там висела ссылка на рубрикатор! По которой я почему-то скользил взглядом… и не пытался посмотреть, «а что там?».
То есть, если хочется перечитать (отличный!) цикл статей Валерии Сироты про экскурсию по Солнечной системе, или найти рассказ Ивана Высоцкого про количество блюд из курицы и рыбы на борту самолёта (1 + 2, применение центральной предельной теоремы, если говорить на языке высокой науки!) — это делается в пару кликов. Кстати, я заодно обнаружил, что в цикле-экскурсии есть и статья про Землю, Луну и приливы — которую я почему-то тогда пропустил.
В общем — пользуйтесь!
А ещё я хочу воспользоваться этим случаем, чтобы посыпать голову пеплом. Все эти годы, когда я хотел найти что-то конкретное из вышедшего в Квантике, я просто пытался гуглить — а если знал год, то переходил по ссылке «Архив» на их главной странице. Что было совсем не всегда удобно.
И все эти годы, на самом виду, там висела ссылка на рубрикатор! По которой я почему-то скользил взглядом… и не пытался посмотреть, «а что там?».
То есть, если хочется перечитать (отличный!) цикл статей Валерии Сироты про экскурсию по Солнечной системе, или найти рассказ Ивана Высоцкого про количество блюд из курицы и рыбы на борту самолёта (1 + 2, применение центральной предельной теоремы, если говорить на языке высокой науки!) — это делается в пару кликов. Кстати, я заодно обнаружил, что в цикле-экскурсии есть и статья про Землю, Луну и приливы — которую я почему-то тогда пропустил.
В общем — пользуйтесь!
Forwarded from Непрерывное математическое образование
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.
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 может быть (сильно) больше хроматического числа!
Вот есть проблема 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.
Но этот граф не является 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.
Другой пример, показывающий разницу между хроматическим числом и возможностью предписанной раскраски — это полный двудольный граф К_{2,4}. Если мы сопоставим двум вершинам наборы {A,B} и {1,2}, а четырём — всевозможные пары {A,1}, {A,2}, {B,1}, {B,2}, то любой выбор раскрасок для первых двух узлов запретит все цвета для какого-нибудь из последних четырёх.
Второе изображение — из Википедии, показывающее, что у графа K_{3,27} choice number не меньше четырёх.
(Image credit: David Eppstein, Wikipedia, https://commons.wikimedia.org/wiki/File:List-coloring-K-3-27.svg)
Ну и, аналогично, для любого n можно взять полный двудольный граф K_{n,n^n}, повторить рассуждение и увидеть, что choice number этого — двудольного! — графа не меньше, чем n+1.
Второе изображение — из Википедии, показывающее, что у графа K_{3,27} choice number не меньше четырёх.
(Image credit: David Eppstein, Wikipedia, https://commons.wikimedia.org/wiki/File:List-coloring-K-3-27.svg)
Ну и, аналогично, для любого n можно взять полный двудольный граф K_{n,n^n}, повторить рассуждение и увидеть, что choice number этого — двудольного! — графа не меньше, чем n+1.
Please open Telegram to view this post
VIEW IN TELEGRAM
Скриншоты/изображения:
P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs;
M. Voigt, List colourings of planar graphs;
Mirzakhani, Maryam. A small non-4-choosable planar graph.
P. Erdös, A. L. Rubin and H. Taylor, Choosability in graphs;
M. Voigt, List colourings of planar graphs;
Mirzakhani, Maryam. A small non-4-choosable planar graph.
Forwarded from Непрерывное математическое образование
https://youtu.be/Phscjl0u6TI
в порядке картинок по выходным — ролик “How Kepler Actually Discovered his Laws”
в порядке картинок по выходным — ролик “How Kepler Actually Discovered his Laws”
Математические байки
Да, рассуждение Томассена — то, что плоские графы являются 5-выбираемыми — удивительно короткое.
Давайте предположим, что на плоскости нарисован граф, причём все его внутренние грани — треугольники (ясно, что от того, что мы проведём дополнительные рёбра, появятся только дополнительные условия).
Пусть его внешний цикл — v_1 v_2 … v_p ; более того, пусть:
- вершинам v_1 и v_2 предписаны конкретные несовпадающие цвета (пусть это 1 и 2 соответственно);
- всем остальным вершинам внешнего цикла — списки из (хотя бы) трёх цветов;
- ну и вершинам внутри — списки из 5 цветов.
Оказывается, у такого графа всегда существует правильная предписанная раскраска!
(Утверждение более сильное, чем нам нужно — но зато его проще доказывать по индукции.)
Набросок доказательства — мы будем доказывать по индукции по количеству вершин в графе. Если во внешнем цикле есть хотя бы одна «диагональ» — т. е. ребро v_a v_b, соединяющее внутри области две его вершины — то можно по нему разбить граф на две части. Сначала раскрасить ту, на границе которой есть ребро v_1 v_2. Получить раскраску для вершин v_a и v_b, и раскрасить вторую часть.
Если же такой диагонали нет (что, собственно, есть основной случай), то давайте возьмём вершину v_p — соседнюю с v_1 с другой стороны. Для неё формально есть 3 разрешённых цвета — так что хотя бы два из них отличны от цвета 1, который сопоставили вершине v_1. Выберем два таких цвета, x и y.
Теперь — выкинем вершину v_p. Какие-то из внутренних вершин графа тогда станут граничными — пусть это u_1,…,u_r. Из разрешённых им цветов (их было 5) выкинем оба x и y — у каждой из них останется хотя бы 3 цвета; так что можно применить предположение индукции и правильно раскрасить получившийся граф. Остаётся дораскрасить выкинутую вершину v_p — а единственный возможный конфликт, который остался, это ребро v_{p-1} v_p. Ну так раскрасим v_p в тот из цветов x и y, в который не окрашена вершина v_{p-1}. Ура!
Как пишет Томассен,
«The proof is probably the simplest proof of the 5-color theorem for planar graphs.»
Давайте предположим, что на плоскости нарисован граф, причём все его внутренние грани — треугольники (ясно, что от того, что мы проведём дополнительные рёбра, появятся только дополнительные условия).
Пусть его внешний цикл — v_1 v_2 … v_p ; более того, пусть:
- вершинам v_1 и v_2 предписаны конкретные несовпадающие цвета (пусть это 1 и 2 соответственно);
- всем остальным вершинам внешнего цикла — списки из (хотя бы) трёх цветов;
- ну и вершинам внутри — списки из 5 цветов.
Оказывается, у такого графа всегда существует правильная предписанная раскраска!
(Утверждение более сильное, чем нам нужно — но зато его проще доказывать по индукции.)
Набросок доказательства — мы будем доказывать по индукции по количеству вершин в графе. Если во внешнем цикле есть хотя бы одна «диагональ» — т. е. ребро v_a v_b, соединяющее внутри области две его вершины — то можно по нему разбить граф на две части. Сначала раскрасить ту, на границе которой есть ребро v_1 v_2. Получить раскраску для вершин v_a и v_b, и раскрасить вторую часть.
Если же такой диагонали нет (что, собственно, есть основной случай), то давайте возьмём вершину v_p — соседнюю с v_1 с другой стороны. Для неё формально есть 3 разрешённых цвета — так что хотя бы два из них отличны от цвета 1, который сопоставили вершине v_1. Выберем два таких цвета, x и y.
Теперь — выкинем вершину v_p. Какие-то из внутренних вершин графа тогда станут граничными — пусть это u_1,…,u_r. Из разрешённых им цветов (их было 5) выкинем оба x и y — у каждой из них останется хотя бы 3 цвета; так что можно применить предположение индукции и правильно раскрасить получившийся граф. Остаётся дораскрасить выкинутую вершину v_p — а единственный возможный конфликт, который остался, это ребро v_{p-1} v_p. Ну так раскрасим v_p в тот из цветов x и y, в который не окрашена вершина v_{p-1}. Ура!
Как пишет Томассен,
«The proof is probably the simplest proof of the 5-color theorem for planar graphs.»
Forwarded from Непрерывное математическое образование
задача Ф.Петрова с ВсОШ-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 нулевая — так как все они имеют нулевую степень хотя бы по одной переменной
противоречие
)
доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и
если каждой вершине 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 нулевая — так как все они имеют нулевую степень хотя бы по одной переменной
противоречие
)
доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и
Telegram
Непрерывное математическое образование
Пусть карту — или посто граф — можно раскрасить в N цветов (так, что соседние вершины имеют разные цвета).
А если для каждой вершины зафиксирован свой набор из N разрешенных цветов, получится ли выбрать из них правильную раскраску? На первый взгляд может…
А если для каждой вершины зафиксирован свой набор из N разрешенных цветов, получится ли выбрать из них правильную раскраску? На первый взгляд может…
Forwarded from Непрерывное математическое образование
на странице https://www.mathnet.ru/present12021 и далее по ссылкам
можно послушать рассказы Ф.Петрова на ЛШСМ-2015 про полиномиальный метод
в т.ч. с применениями и к упоминавшимся чуть выше списочным раскраскам, и к аддитивной комбинаторике, и к тождествам с q-биноимальным коэффициентам…
можно послушать рассказы Ф.Петрова на ЛШСМ-2015 про полиномиальный метод
в т.ч. с применениями и к упоминавшимся чуть выше списочным раскраскам, и к аддитивной комбинаторике, и к тождествам с q-биноимальным коэффициентам…