Одне з найкрасивіших і досі не вирішених завдань математики формулюється наступним чином. Спробуємо розфарбувати площину так, щоб ніякі дві точки, що знаходяться на відстані одного сантиметра один від одного, не виявилися пофарбовані в один колір. Яка мінімальна кількість кольорів для цього потрібна? Незважаючи на уявну простоту, за майже 70 років існування цього завдання точної відповіді досі немає, притому що над ним працювала ціла плеяда видатних вчених, в тому числі і Пал Ердеш, один з найбільших математиків XX століття.
Приблизно 60 років тому математики зрозуміли, що це мінімальне число кольорів дорівнює або чотирьом, або п'яти, або шести, або семи - і до останнього моменту цей результат не вдавалося поліпшити. Але минулого тижня британець Обрі ді Грей опублікував статтю, в якій довів, що чотирьох фарб теж не вистачає, скоротивши число варіантів до трьох: п'ять, шість або сім.
Примітний також той факт, що сам ді Грей далекий від фундаментальної математики, область його професійних інтересів більше пов'язана з біомедициною - він є провідним науковим співробітником фонду SENS боротьби зі старінням. Мабуть, найближче до математики належать його статті, присвячені штучному інтелекту в медицині.
Редакція вирішила розібратися в історії завдання про розмальовування площини (і не тільки) і розповісти про те, як математик-аматор зміг зробити новий важливий крок до її вирішення, в деякому сенсі випередивши багатьох професіоналів.
Формулювання проблеми
Завдання про хроматичне число площини
Яка найменша кількість кольорів, достатня для розмальовування площини таким чином, щоб на ній не було двох точок одного кольору, розташованих на відстані 1 (одного сантиметра) один від одного?
Сьогодні ніхто не сумнівається в тому, що завдання про розмальовування площини - з області теорії графів. Вона виникла в середині XX століття, причому, очевидно, незалежно один від одного її придумали відразу кілька математиків - до числа авторів зараховують і самого Пала Ердешу. У «Математичній книзі розмальовок» Олександр Сойфер розповідає про результати своїх спроб встановити авторство завдання - опитавши кілька математиків, Олександр дійшов висновку, що першим сформулював завдання Едвард Нельсон - тоді студент Університету Чикаго. У 1950 році Едвард Нельсон займався проблемою розмальовок планарних графів, яка пізніше отримала назву теореми про чотири фарби.
Планарний граф
Графом називається набір точок (вершин) і з'єднуючих їх відрізків (ребер). Планарним називається такий граф, який можна намалювати на площині без перетину ребер.
Чого дорівнює найменша кількість фарб, достатня для розмальовки всіх вершин будь-якого планарного графа так, що жодні дві вершини, сполучені ребром, не виявилися одноколірними?
У цієї проблеми є більш просте еквівалентне формулювання: візьмемо деяку карту, намальовану на площині. Вона складається із замкнутих областей, що межують одна з одною. Чи завжди цю карту можна розфарбувати в чотири кольори так, щоб ніякі дві країни одного кольору не мали спільного кордону?
Нельсон припустив, що замість того, щоб розфарбовувати всілякі планарні графи, можна побудувати один величезний граф, в якому містяться всі можливі планарні графи. І тоді, якщо довести, що цей «суперграф» розмальовуємо за правилами в чотири кольори, то затвердження теореми стане очевидним наслідком.
Кандидатом на роль «великого-великого» графа стала така конструкція: візьмемо всі (без винятку) точки площини. Вони стануть вершинами нашого графа. Якщо пара точок знаходиться на відстані довжиною в одиницю (наприклад, в один сантиметр), то ми з'єднаємо їх відрізком - ці відрізки стануть ребрами нашого графа. Звичайно, він не буде планарним. Питання, яке поставив Нельсон: чи можна розфарбувати вершини такого графа в чотири кольори?
Це формулювання, при уважному розгляді, повністю збігається зі звичайним завданням про розмальовування площини. Просто нам треба побачити за кожною з точок площини вершину графа, сполучену величезним числом ребер з іншими вершинами.
Відразу варто зауважити - на жаль, ідея Нельсона не допомогла у вирішенні завдання про чотири фарби. Цей доказ було представлено лише 26 років потому Кеннетом Аппелем і Вольфгангом Хакеном і він був заснований на класифікації всіх можливих планарних графів (карт) на 1936 різних категорій (пізніше спрощено до 633), розмальовуваність кожної з яких можна перевірити. Цей доказ став першим комп'ютерним доказом складного математичного завдання. Так перебір переміг улюблене математиками узагальнення.
Перші результати
Перші кроки до вирішення завдання про розмальовування площини зробити дуже просто. Задумаємося над тим, якої кількості кольорів точно не вистачить. Очевидно, однієї фарби буде мало. А чи вистачить двох?
Легко показати, що і двох кольорів недостатньо. Для цього потрібен доказ від противного. Нехай ми розфарбували нашу площину в два кольори. Тоді візьмемо на ній рівносторонній трикутник зі стороною рівною одному сантиметру. Перша вершина - синя, друга - червона. А якого кольору третя вершина? Оскільки вона знаходиться на відстані одного сантиметра від перших двох, то ні синьої, ні червоної бути не може. У наявності логічне протиріччя.
Трохи складніше показати, що і трьох фарб недостатньо. Візьмемо ромб, що складається з двох склеєних між собою по стороні правильних одиничних трикутників, і спробуємо його розфарбувати. Дві склеєних вершини нехай будуть синього і червоного кольору, а решта дві абсолютно точно виявляться третього, наприклад зеленого, кольору. Відстань між цими двома зеленими вершинами дорівнює квадратному кореню з трьох - жодних суперечностей з умовою теореми тут не виникає.
Але насправді ми тільки що довели, що будь-які дві точки на площині, розташовані один від одного на відстані квадратного кореня з трьох, будуть одноколірними. Отже, якщо ми візьмемо одну зелену точку і побудуємо навколо неї коло діаметром корінь з трьох, виявиться що вона теж буде зеленою! Але між деякими точками цього кола точно буде одинична відстань (у кожної точки кола буде мінімум дві таких сусідки). А це вже суперечить умові. Цей результат був отриманий Гуго Хадвигером в 1961 році - до речі, Хадвигера вважають другим автором завдання про хроматичний число.
Цю побудову можна легко спростити - тоді ми отримаємо відому фігуру під назвою «веретено Мозера». Візьмемо дві копії нашого ромба з загальною зеленою вершиною і трохи повернемо їх один відносно одного - так, щоб відстань між двома іншими «зеленими» вершинами стала одиницею. Вершини такого графа, звичайно ж, не можна розфарбувати в три кольори - фарб буде потрібно як мінімум чотири.
Отже, ми з'ясували, що при дотриманні вихідної умови не можна розфарбувати площину в три кольори. Але чи можна взагалі хоч якось розфарбувати площину так, щоб ця розмальовка відповідала вимозі завдання? Відповідь: так, звичайно. Найпростіша розмальовка, що спадає на думку, - сітка з квадратів зі стороною 0,51 сантиметра, що складається з повторюваних сегментів 3x3, пофарбованих у дев'ять різних кольорів. Мінімальна кількість кольорів, для якого відома розмальовка площини, дорівнює семи: в її основі лежить замощення площини шестикутниками, на манер бджолиних сот.
Математики намагалися скоротити кількість кольорів для верхньої межі, але це виявилося не так просто. Наприклад, в одній із розмальовок площини семикутниками і квадратами частка площі, пофарбованої в сьомий колір, не перевищує 0,3 відсотка. Їм пофарбовані лише маленькі квадрати. Але повністю позбутися його не виходить.
Всі ці прості результати були отримані ще до 1962 року. І протягом понад півстоліття просунутися у вирішенні цього завдання не вдавалося.
Невловиме число
Особливість завдання про хроматичний кількість полягає в тому, що, мабуть, якогось загального підходу або інструменту для її вирішення немає (або поки немає). З іншого боку, розфарбовування графів було непогано досліджено, і відкрита важлива теорема, яка з'явилася незалежно від завдання про площину в 1951 році і вказує деякий шлях до того, як може виглядати рішення. Це теорема де Брейна-Ердеша.
Повернемося до формулювання, яке дав для завдання про хроматичне число Едвард Нельсон. По суті, наша мета - розфарбувати величезний нескінченний граф, в якому вершинами є всі, без винятку, точки дійсної площини. Ніколаас де Брейн і Пал Ердеш досліджували, як співвідноситься розмальовка нескінченного графа і окремих його частин, субграфів. Виявляється, хроматичне число графа - якщо воно взагалі звичайно - дорівнює максимальному хроматичному числу його підграфів.
Ми вже знаємо, що хроматичне число площини звичайно, не перевищує семи. Отже, якщо воно дорівнює шести, то ми точно зможемо побудувати граф з одиничними відстанями між зв'язаними вершинами, для «правильної» фарбування якого буде потрібно як мінімум шість кольорів. На жаль, довести, що іншого графа з хроматичним числом, рівним семи, не існує, за допомогою цієї теореми не вийде. Натомість, якщо знайти такий граф з хроматичним числом, рівним семи, то завдання про хроматичне число площини буде нарешті вирішено.
Варто зауважити, що доказ теореми вимагає використання спеціальної аксіоми теорії безліч - аксіоми вибору. Не вдаючись у подробиці, зауважимо, що не всі системи аксіом включають її і в деяких спеціальних випадках ця теорема може виявитися невірною. А значить, і хроматичне число площини, в теорії, може залежати від вибору аксіом.
Інші хроматичні числа
Завдання про розмальовки площини легко розширюється. Наприклад, можна спробувати розфарбовувати з тими ж вимогами простору вищих розмірностей: ніщо не заважає розфарбовувати тривимірний або чотиримірний простори. Більше того, можна розглядати не тільки площини дійсних чисел, але і обмежитися тільки раціональними числами. Для цього випадку хроматичне число виявиться дивним чином рівним двом. Є й деякі інші спеціальні формулювання завдання, в яких забороняється не одне, а кілька відстаней.
П "ятиколірний граф
Теорема де Брейна-Ердеша наче пропонує будувати все більш і більш складні графи з одиничними відстанями між пов'язаними вершинами і досліджувати їх хроматичні числа. Саме цим і вирішив зайнятися Обрі ді Грей. По суті, він зробив наступне: знайшов маленький граф, в якому є два різних типи розмальовок в чотири кольори, і вплів його спочатку в один величезний граф, який заборонив перший тип розмальовок, а потім в інший, що заборонив другий тип розмальовок. Об'єднавши ці два графа, ді Грей отримав новий, ще більш монструозний, граф з 20 тисячами вершин, в якому для вихідного маленького графа заборонені обидві розмальовки в чотири кольори. А значить, без п'ятого кольору не обійтися.
Величезні розміри сіток, які розфарбовував ді Грей, абсолютно не дозволяли працювати з ними вручну. Тому британець активно використовував у побудовах комп'ютер. Прослідкуємо за його роботою.
Побудуємо правильний шестикутник зі стороною, що дорівнює одному сантиметру, поставимо крапку в його центрі і з'єднаємо її з вершинами. Всі намальовані нами відрізки мають одиничну довжину, перед нами граф з 7 вершинами і 12 ребрами. Спробуємо розфарбувати його в чотири кольори всіма можливими способами. Виявляється, є всього лише чотири принципово різних розмальовки шестикутника, причому в двох з них виникають рівносторонні трикутники зі стороною, що дорівнює квадратному кореню з трьох, всі вершини яких пофарбовані в один колір. Їх ді Грей називає монохроматичними трійками.
Виявляється, можна побудувати такий граф (каркас з вершин і ребер), в якому обов'язково знайдеться монохроматична трійка. Він складатиметься з 52 таких шестикутників, правильним чином розташованих на площині. Побудова починається з шестикутника, побудованого з шестикутників з абзацу вище, який потім подвоюється і повертається відносно центру, а потім знову подвоюється і повертається відносно вершини, що лежить на відстані двох сантиметром від центру.
Потім ді Грей побудував інший граф, в якому монохроматичні трійки заборонені. Перша спроба побудувати цей граф комп'ютерним перебором, взявши за основу багато веретен Мозера, провалилася. Але потім ді Грей замінив їх на граф, в якому одна вершина оточена тридцятьма іншими, що лежать на одиничному колі певним чином. Потім він взяв ще тридцять таких сіток і поєднав їх центри з вершинами вихідного 31-вершинного графа. Вийшла 1345-вершинна конструкція - вона називається графом W. Сім копій W ді Грей помістив у вершини найпершого одиничного шестикутника з сьомою вершиною в центрі і перевірив, як його можна розфарбувати. Комп'ютерний перебір показав, що в центральному шестикутнику не може виникнути монохроматичної трійки.
На наступному етапі ді Грей скопіював цей граф 52 рази так, щоб його частиною виявився граф з попереднього абзацу, в якому монохроматична трійка обов'язково виникне. 20425-вершинний каркас (151311 ребер) не можна розфарбувати в чотири кольори, оскільки інакше виникає протиріччя. Так і вийшов перший приклад графа з одиничними відстанями між зв'язаними вершинами, хроматичне число якого дорівнює п'яти.
Наприкінці статті ді Грей також наводить спрощений 1567-вершинний граф, який також вимагає для розмальовування п'ять кольорів. Правда, як виявилося, в цьому місці британець трохи помилився і видалив занадто багато вершин.
А що далі?
Відразу після публікації препринту на arXiv.org професійні математики приступили до перевірки доказу. Незважаючи на деякий скепсис - любитель просунувся в завданні, в якому ніхто не міг просунутися майже 60 років? - виявилося, що рішення в цілому вірне. Це підтвердила багаторазова незалежна комп'ютерна перевірка побудови. Правда, зі спрощеним графом вийшла помилка - виявилося, що він все ж розфарбовуємо в чотири кольори. Але цей «лід», як його назвали математики, легко виправляється додаванням 18 вершин, які ді Грей видалив на останніх кроках спрощення.
Слідом за цим ді Грей, порадившись з Терренсом Тао, опублікував нове завдання на сайті проекту Polymath Projects з пошуку можливих спрощень п'ятиколірного графа. На сьогоднішній момент кращий результат запропонував Марайн Хюле (Marijn Heule) з Університету Техасу, скоротивши число вершин до 826. До речі, про роботи Марайна ми писали два роки тому - він є автором найбільшого комп'ютерного доказу.