Прорив у завданні розфарбування площини

Навчання 26 серпня 2022 Перегляди: 78

Введення

У цій статті ми розповімо про недавнє дивовижне просування в одному з найвідоміших завдань комбінаторної геометрії. Це завдання про так зване хроматичне число площини. Потрібно знайти мінімальну кількість кольорів, в які можна так пофарбувати площину, щоб відстань між точками одного кольору ніколи не дорівнювала одиниці. Це число і називається хроматичним, а позначається воно(   (mathbb {R} ^ 2)). Навіщо так багато букв? Ну, просто фарбувати можна не тільки площину — можна і пряму, і простір, і багато інших цікавих об’єктів. На прямій, до речі, все майже очевидно: (  (mathbb {R} ^ 1) = 2), оскільки одного кольору, звичайно, не вистачить, а двох достатньо, про що свідчить малюнок 1. Що ж з площиною?

Ріс. 1. Розмальовка прямої у 2 кольори

Ріс. 2. Мозерівське веретено

Ясно, що не вистачить одного кольору, і легко бачити, що не вистачить і двох кольорів. Дійсно, розглянемо вершини правильного трикутника зі стороною 1. Вже для «правильної» розмальовки цих трьох точок, очевидно, необхідно використовувати три різних кольори. Трохи складніша конструкція так званого мозерівського веретена (рис. 2) показує, що(   (mathbb {R} ^ 2) ^ 4).

У той же час легко пофарбувати площину в 7 кольорів без точок одного кольору на відстані 1. Цілих два різних фарбування зображені на малюнках 3 і 4. На малюнку 3 кольори утворюють правильні шестикутники з великими діагоналями довжини x трохи менше одиниці. Межі між двома або трьома шестикутниками фарбуються в колір будь-якого з них (у будь-якому з двох або трьох кольорів, відповідно, але не в один з решти кольорів). Відстань між найближчими шестикутниками одного кольору дорівнює( xfrac {sqrt {7}} {2}), і це число, своєю чергою, має бути вже суворіше за одиницю. Таким чином, здається, що у розмальовки є «запас міцності», що дозволяє якось її модифікувати в розмальовку шістьма кольорами. На малюнку 4 кольору утворюють квадрати, і тут ніякого запасу міцності немає, навіть межі доводиться фарбувати з ^{обережністю}.

Ріс. 3. Перша розмальовка площини у 7 кольорів

Ріс. 4. Друга розмальовка площини у 7 кольорів

Завдання про вишукування хроматичного числа площини виникло 1950 року (див. [1]), хоча ще 1944 року дуже близьке завдання вивчав Хадвіґер. До недавнього часу все, що було відомо про хроматичному числі, — це з легкістю доведені нами тільки що оцінки

( 4 ≤ χ (mathbb{R}^2) ≤ 7 ).

Іншими словами, близько 70 років у вкрай популярному завданні було цілих 4 варіанти відповіді, і ніяких просувань до встановлення істини не було!

Відзначимо ряд цікавих суміжних фактів. Наприклад, всі нижні оцінки, які ми отримували, це фактично оцінки за допомогою графів. І трикутник, і мозерівське веретено — це так звані дистанційні графи, тобто графи, вершини яких — точки площини, а ребра — відрізки довжини 1, що з’єднують пари точок, що відстоять один від одного на відстань 1. Нагадаємо, що хроматичне число графа G — це мінімальне число кольорів(   (G)), в які можна так пофарбувати вершини графа, щоб кінці будь-якого ребра мали різні кольори. Таким чином ,(   (mathbb {R} ^ 2) ^   (G)) для будь-якого дистанційного графа G. У 1976 році Ердеш поставив питання, чи існують дистанційні графи з хроматичним числом 4 (як у мозерівського веретена), але без трикутників. Виявилося, і таке буває! Зараз відомі приклади лише на двадцяти трьох вершинах (див. [2]).

У 1971 році Вудал довів, що якщо фарбувати площину в певному сенсі так само, як на малюнках 3 і 4, то буде потрібно не менше шести кольорів. Що означає «так само»? Ну, скажімо, кожен колір — це об’єднання деякого числа багатокутників (не обов’язково випуклих і не обов’язково містять весь свій кордон). Виходить, що якщо раптом(   (mathbb {R} ^ 2)

У 2016 році Канель-Бєлов запропонував [4] наступну інтерпретацію завдання. Розгляньмо у тривимірному просторі шар між двома площинами товщини. Зрозуміло, що під час досить малих відступів запас міцності з зображення 3 дозволяє і весь шар пофарбувати в 7 кольорів без точок одного кольору на відстані 1. Виявилося, що при будь-якому   > 0 чотирьох кольорів вже не вистачає: потрібно хоча б 5! Іншими словами, якщо раптом(   (mathbb {R} ^ 2) = 4), то розмальовку не просто важко, а дуже важко собі уявити!

Багато інших цікавих фактів можна знайти в книжках [1] і [3].

А 8 квітня 2018 року сталася чудова подія. На ресурсі arxiv.org, куди викладаються статті до своєї публікації в журналах, з’явилася замітка Обрі ді Грея [5], в якій описувався дистанційний граф з хроматичним числом 5! Оскільки завдання неймовірно популярне, величезна кількість фахівців взялася за перевірку і практично відразу результат був підтверджений. Тепер ми знаємо, що

( 5 ≤ χ (mathbb{R}^2) ≤ 7 ).

Цікаво, що ді Грей не є професійним математиком. Він геронтолог за фахом, тобто він займається вивченням процесів старіння. Свіжий погляд на завдання дозволив йому досягти такого успіху.

У роботі ді Грея дистанційний граф з хроматичним числом 5 мав 1581 вершину. Зараз вже знайдено графи з 553 вершинами [6]. І є сміливці, які сподіваються відшукати графи з хроматичним числом 6!

У цій статті ми розповімо про результат ді Грея.

Про користь свіжого погляду

Подивимося, як влаштовані найпростіші дистанційні графи з хроматичним числом 4. Це веретено Мозерів, винайдене братами Лео і Вільямом Мозерами, і граф Голомба. У веретені Мозерів є два підграфа- «ромба», що складаються з двох рівносторонніх трикутників із загальною стороною. При будь-якому розмальовуванні вершин такого підграфа в 3 кольори точки M, N мають один колір (рис. 5, а). Значить, у веретені Мозерів точки P, Q, R одного кольору, але Q і R з’єднані руба (рис. 5, б). Чи можемо ми отримати протиріччя таким же способом, коли кольорів не три, а чотири? Іншими словами, побудувати такий граф, що в ньому є пара вершин, кольори яких збігаються при будь-якій правильній розмальовці. Тоді було б доведено, що площина не фарбується в чотири кольори. Але як побудувати такий граф — незрозуміло.

Ріс. 5. Підграфи у веретені Мозерів

Розіб’ємо граф Голомба на два підграфи (рис. 6, а). Перший з них — шестикутник, що містить шість рівносторонніх трикутників. З точністю до перестановок кольорів він фарбується в три кольори єдиним чином (рис. 6, б) Значить, вершини рівностороннього трикутника A ­ B ­ C — зі стороною(sqrt {3}) розфарбовані в цьому випадку в один колір.

Ріс. 6. Підграфи у графі Голомба

Позначимо тут і далі( Δ_{sqrt{3}}) — безліч, що складається з вершин рівностороннього трикутника зі стороною(sqrt {3}). При цьому розташування трикутника на площині може бути будь-яким.

У другому підграфі вершини такого рівностороннього трикутника з’єднані з вершинами рівностороннього трикутника зі стороною 1 (рис. 6, в). Розфарбовуючи три кольори X, Y, Z різнокольорові. Тоді A’, B‘, C’не можуть бути одного кольору, оскільки він збігається з кольором однієї з точок X, Y, Z. Таким чином, у графі Голомба до протиріччя призводить розмальовка двох підграфів: перший з них гарантує, що вершини( Δ_{sqrt{3}}) будуть одноколірними, а другий виключає таку можливість.

Тепер нас цікавить дистанційний граф, який неможливо розфарбувати в чотири кольори. Можливо, простіше шукати не весь граф цілком, а підграфи, розмальовка яких призводить до суперечностей? У першому підграфі деякий набір вершин, «шаблон», при будь-якій правильній розмальовці буде одноколірним, а в другому підграфі він завжди різнокольоровий. Або так: якщо в першому підграфі знайдеться хоча б один одноколірний шаблон, а в другому підграфі його неможливо пофарбувати в один колір, то це неодмінно призведе до протиріччя при розмальовуванні площини. (З одного боку, одноколірний шаблон повинен десь виявитися, а з іншого боку, він заборонений — адже до будь-якого його розташування на площині можна прикріпити другий граф.)

Саме так і діяв ді Грей: він розглядав як шаблон трикутник( Δ_{sqrt{3}}), як у графі Голомба, і перебирав розмальовки в 4 кольори двох досить складних дистанційних графів, про які йтиметься далі.

Побудова графа, що містить одноколірний( Δ_{sqrt{3}})

В яких множинах точок серед попарних відстаней зустрічається багато одиниць, а серед всіляких трикутників — багато( Δ_{sqrt{3}})? Перше, що спадає на думку, це шматок трикутної решітки. Припустимо, що одноколірного трикутника( Δ_{sqrt{3}}) немає. Це не призводить до суперечності відразу, але сильно обмежує число можливих розмальовок.

Вправи

1. Переконайтеся, що якщо правильна розмальовка у 4 кольори графа на малюнку 7 не містить одноколірного( Δ_{sqrt{3}}), то: а) кожен колір, крім кольору центральної вершини, зустрічається рівно два рази; б) з точністю до поворотів і перестановок кольорів допустимі тільки дві розмальовки.

Ріс. 7. Розмальовки графа на 7 вершинах

2. Доведіть, що будь-яка розмальовка трикутної решітки у 4 кольори, яка не містить одноколірного( Δ_{sqrt{3}}), складається з низки ліній сітки, на кожній з яких є вершини лише двох кольорів.

Вказівник. Можна розглянути два випадки: а) у шестикутниках зустрічається тільки розмальовка, наведена на малюнку 7 праворуч; б) хоча б в одному шестикутнику зустрічається тип розмальовки, як на малюнку 7 ліворуч.

Ріс. 8. Граф Q

Візьмемо ділянку трикутної решітки у формі квітки (рис. 8) і назвемо цю граф Q. З точністю до поворотів і перестановок кольорів існує шість розмальовок центрального великого шестикутника без одноколірного( Δ_{sqrt{3}}) (рис. 9). Кольори дванадцяти крайніх вершин нам не цікаві, хоча їх наявність впливає на число варіантів розмальовки. Важливо, що в розмальовках a, г всі вершини шестикутника розфарбовані в той же колір, що і його центр; в розмальовках б, д таких вершин чотири, а в розмальовках в, е тільки дві.

Ріс. 9. Можливі розмальовки центральної області в графі Q

Ріс. 10. Граф X складається з двох екземплярів графа Q із загальною центральною вершиною

Що буде, якщо взяти два екземпляри графа Q₁ і Q₂ з загальною центральною вершиною і повернути один з них на кут( ^ = 2text {arcsin }frac {1} {4}) щодо іншого (рис. 10)? У отриманому графі, позначимо його X, відстані між відповідними вершинами шестикутників дорівнюють одиниці:

AA′ = BB′ = CC′ = DD′ = EE′ = FF′ = 1.

Крім того, в кожному з примірників графа Q дві, чотири або шість вершин шестикутника розфарбовані в той же колір, що і центральна. Якщо хоча б в одному з примірників таких вершин чотири або шість, то знайдуться дві вершини одного кольору на відстані 1. Отже, Q1 і Q₂ допустимі лише розмальовки в, є.

Нарешті, зауважимо, що в розмальовках в, і кінці діагоналів шестикутників розфарбовані однаково. Тому у графі X за додаткової умови про відсутність одноколірного( Δ_{sqrt{3}}) вершини A, D мають один колір — майже як у триколірній розмальовці веретена Мозерів. Візьмемо два екземпляри графа X, поєднаємо їх і повернемо один з них відносно іншого навколо A на кут( 1 = 2text {arcsin }frac {8}). Тоді( Dtilde {D} = 1) і ці вершини розфарбовані в той же колір, що і A. Ми прийшли до протиріччя, а значить, побудований граф G, в якому хоча б один трикутник( Δ_{sqrt{3}}) розфарбований в один колір (рис. 11).

Ріс. 11. Граф G, у свою чергу, складається з двох примірників графа X

Вправа 3. Доведіть, що якщо безліч вузлів трикутної сітки розмножити трьома поворотами на кути порожніх кутів навколо одного і того ж вузла, отримуючи при цьому ще три екземпляри сітки (рис. 12), то отриманий нескінченний дистанційний граф при будь-якому розмальовуванні вузлів у 4 кольори також містить одноколірний( Δ_{sqrt{3}}). Як і вище ,( ^ = 2text {arcsin }frac {1} {4}) ,( ^ = 2text {arcsin }frac {1} {8}).

Ріс. 12. Чотири екземпляри трикутної сітки

Побудова графа, що виключає розмальовку( Δ_{sqrt{3}}) в один колір

Правильність описаної вище побудови можна перевірити якщо не в розумі, то хоча б з ручкою і листком паперу. На жаль, другий граф зі статті ді Грея не допускає наочних пояснень. Поки ніхто не придумав, як довести без комп’ютера, що цей граф має потрібну властивість, або як побудувати інший граф, для якого доказ був би «людським» від початку до кінця.

Ді Грей припустив, що якщо в дистанційному графі міститься досить багато веретень Мозеров в якості підграфів, то вдасться виключити одноколірну розмальовку хоча б одного фіксованого трикутника( Δ_{sqrt{3}}). Як побудувати такий дистанційний граф, щоб на одну вершину в середньому доводилося якомога більше веретен? Після низки невдалих спроб ді Грей прийшов до конструкції, при описі якої стане в нагоді наступне визначення.

Визначення. Нехай X, Y — деякі безлічі векторів (взагалі кажучи, X, Y можуть складатися з чого завгодно, лише б була визначена операція додавання). Сумою Мінківського M = X + Y називається безліч, що складається з усіх можливих сум x + y, де x ∈ X, y ∈ Y (див. приклад на малюнку 13).

Ріс. 13. Сума Мінківського {u₁, u₂} + {v₁, v₂, v₃}

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

Ріс. 14. Класи еквівалентності ребер. Граф V

На малюнку 14, б поєднані «звичайне» веретено Мозеров (рис. 14, а) і «потрійне» веретено — два веретена Мозеров із загальним підграфом- «ромбом». Назвемо два ребра еквівалентними, якщо кут між ними кратний 60 °. Ребра розіб’ються на 5 класів, позначених кольором (див. рис. 14, б). Порівняємо кожному ребру вектор, приписавши йому довільний напрямок. Тепер уявімо, що на площині сидить коник і він може стрибати на одиничну відстань або в одному з цих напрямків, або в будь-якому з них, повернутому на кут, кратний 60 °. Відзначимо початкову точку і всі точки, в які коник потрапляє за один стрибок. Таких точок буде 5· 6 + 1 = 31 — це вершини графа V, показаного на малюнку 14, в. Очевидно, точки P, Q, R утворюють( Δ_{sqrt{3}}). Нехай O — початок координат. При обчисленні суми Мінківського V + V кожна точка буде складатися з точкою O, тому

{P, Q, R} ⊂ V ⊂ V + V ⊂ V + V + V.

Вправа 4. а) Переконайтеся, що якщо ковальцю дозволяється зробити не більше 2 стрибків, то йому доступні вершини графа W = V + V. б) Доведіть, що W містить веретено Мозерів як підграф.

Виявляється, якщо позначити всі точки, в які коник може потрапити за 0, 1, 2 або 3 стрибки (V + V + V) і пофарбувати точки P, Q, R в один колір, то правильно розфарбувати інші вершини в чотири кольори неможливо!

Шуканий граф побудований, але комп’ютерний перебір розмальовок зачіпає лише невелику частину вершин. Ді Грей не поспішав з публікацією і спробував зробити побудову більш економною. Опишемо варіант, до якого він прийшов.

Нехай W складається з векторів з W, довжина яких не перевершує(sqrt {3}). Нехай U — підграф V на 7 вершинах, показаний на малюнку 7.

Вправа 5. Знайдіть потужності багатьох W і W.

Ріс. 15. Граф H на 1345 вершинах

Граф H = W ^ + U має 1345 вершин і є підграфом V + V + V (рис. 15). Якщо розфарбувати три точки в вершинах( Δ_{sqrt{3}}), вибраних з вершин U, комп’ютерний перебір показує, що для розмальовки інших вершин чотирьох кольорів (включаючи перший) не вистачає.

Перевірити це твердження без написання програми поки нікому не вдалося. Порівняно з багатьма іншими «комп’ютерними» доказами обсяг обчислень невеликий: близько хвилини рахунку на одному ядрі сучасного процесора. Але і цей перебір набагато перевищує людські можливості. А ось перевірка за допомогою комп’ютера доступна для більшості програмістів.

Використовується трохи вдосконалений пошук у глибину. По-перше, корисно спочатку впорядкувати вершини графа так, щоб у наступної вершини було якомога більше сусідів серед розфарбованих раніше (наприклад, сортуванням зі збиття ступеня вершини, хоча є способи і краще). По-друге, після розмальовки будь-якої вершини слід відразу ж перевіряти, чи немає серед сусідніх вершин таких, для яких залишився тільки один варіант розмальовки, і фарбувати їх негайно (подібно до того, як відразу ж вписуються єдині варіанти при розгадуванні судоку).

Пласкі дистанційні графи з хроматичним числом 5

У попередніх розділах ми описали побудову графа G, при розмальовуванні якого в 4 кольори хоча б один з трикутників( Δ_{sqrt{3}}) буде розфарбовано в один колір, і графа H, при розмальовуванні якого в 4 кольори фіксований трикутник( Δ_{sqrt{3}}) не може бути одноколірним. З першої умови випливає, що на площині, розфарбованій у 4 кольори, знайдеться одноколірний( Δ_{sqrt{3}}), а з другої — що одноколірного( Δ_{sqrt{3}}) на площині немає. Це вже означає, що

( χ (mathbb{R}^2) ≥ 5 ),

але неважко вказати і конкретний граф, що забезпечує нижню оцінку. Прикриємо до кожного з 52 шестикутників у графі G за екземпляром H. При цьому багато вершин збігаються, але це не повинно нас турбувати. Якщо не існує правильної розмальовки графа в чотири кольори без урахування їх розташування на площині і ототожнення вершин, то після ототожнення її тим більше не буде. Отриманий граф P на 20425 вершинах неможливо правильно розфарбувати в чотири кольори.

Як і при переборі розмальовок H, з’ясовується, що більшу частину вершин можна відкинути. Ді Грею вдалося виділити з графа P підграф P ­ на 1581 вершині, який також не фарбується в чотири кольори (рис. 16).

Ріс. 16. Граф P — на 1581 вершині. Не існує правильної розмальовки P в чотири кольори

Стаття ді Грея привернула увагу ентузіастів комбінаторної геометрії до кількох питань. Яке найменше число вершин може мати плаский дистанційний граф з хроматичним числом 5 або більше? Чи не можна знайти граф з хроматичним числом 6 або 7, ускладнюючи конструкцію? Чи існує доказ нової нижньої оцінки, доступний для безпосередньої перевірки людиною?

Незабаром було знайдено алгоритмічно простіший, хоча, на жаль, ще менш «людський» спосіб будувати графи з хроматичним числом 5 і меншим числом вершин. З’ясувалося, що для цього можна взяти як безліч вершин (V + V + V) ∪ _^ (V + V + V), де _^ — поворот на кут( ^ =text {arcsin }frac {1} {8}) навколо початку координат. Автор статті [6] перебирав різні способи відкидання «зайвих» вершин при обчисленні суми Мінковського, а потім використовував так звані ^{SAT-рішучі 2}, щоб знайти підграф, з якого не можна видалити жодної вершини без зменшення хроматичного числа. Станом на поточний момент вдалося скоротити число вершин до 553, але, зрозуміло, немає ніякої гарантії, що це число мінімальне. Цілком ймовірно, що рекорд ще не раз оновиться. Його поточне значення можна дізнатися на сайті проекту Polymath [7] у розділі, присвяченому даному завданню.

Література1

. A. Soifer. The Mathematical Coloring Book. Springer, 2009.

2. А. Райгородський, О. Рубанов, В. Кошелєв. Хроматичні числа//Квант, 2008, № 3.3

. О. М. Райгородський. Хроматичні числа. М.:МЦНМО, 2015.4.

А. Я. Канель-Бєлов, В. А. Воронов, Д. Д. Черкашин. Про хроматичне число площини//Алгебра та аналіз, 29:5 (2017), с. 68-89.5. A

. D. N. J. de Grey. The chromatic number of the plane is at least 5 // arXiv preprint arXiv:1804.02385 (2018).6. M

. J. H. Heule. Computing small unit-distance graphs with chromatic number 5 // arXiv preprint arXiv:1805.12181 (2018).7. П

роект Polymath.

¹ На малюнку 4 рожевим виділено частину межі, що фарбується в той самий колір, що й сам квадрат. Чорна частина кордону отримує колір від сусідніх квадратів.

² Спеціалізовані алгоритми і програми, призначені для вирішення завдання про здійсненність бульових формул — NP-повної задачі, до якої зводиться в тому числі і завдання про розмальовування графа в k кольорів.