Теорема Ремзі

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

Двоколірний повний граф потужності 5, без монохроматичного повного підграфа потужності 3

Як найпростіший приклад, розглянемо два кольори ( синій і червоний). Нехай ${\displaystyle r}$ і ${\displaystyle s}$ –будь-які два натуральні числа. Теорема Ремзі стверджує, що існує найменше натуральне число ${\displaystyle R(r,s)}$, для якого кожне синьо-червоне забарвлення ребер повного графа на ${\displaystyle R(r,s)}$ вершинах містить синю кліку на ${\displaystyle r}$ вершинах або червону кліку на ${\displaystyle s}$ вершинах. ( У даному випадку ${\displaystyle R(r,s)}$ означає ціле число, що залежить як від ${\displaystyle r}$, так і від ${\displaystyle s}$.)

Теорема Ремзі є фундаментальним результатом у комбінаториці. Вперше цей результат був отриманий Френком Ремзі. Це дало початок комбінаторній теорії, яка отримала назву теорія Ремзі. Даний розділ математики шукає певний порядок серед безладу: загальні умови для існування підструктур з регулярними властивостями. У нашому випадку постає питання про існування одноколірних підмножин, зокрема тих, що складаються з суміжних ребер одного кольору.

Продовження цієї теореми дозволяє застосувати її для довільної скінченної кількості кольорів, а не тільки для двох. Власне кажучи, теорема стверджує, що для довільної кількості кольорів ${\displaystyle c}$ та довільних натуральних чисел ${\displaystyle n_{1},...,n_{c}}$, існує натуральне число ${\displaystyle R(n_{1},...,n_{c})}$ таке, що якщо ребра повного графа порядку ${\displaystyle R(n_{1},...,n_{c})}$ розфарбовані в ${\displaystyle c}$ різних кольорів, то для деякого ${\displaystyle i}$ від ${\displaystyle 1}$ до ${\displaystyle c}$, він повинен містити повний підграф порядку ${\displaystyle n_{i}}$ з ребрами ${\displaystyle i}$-го кольору. У наведеному вище випадку ${\displaystyle c=2}$ ( а ${\displaystyle n_{1}=r}$ і ${\displaystyle n_{2}=s}$).

Приклади

2-колірний випадок, доведення без слів За принципом Діріхле, з довільної вершини v виходить щонайменше 3 ребра одного кольору (фіолетові штрихові лінії). Назвемо три вершини, у яких закінчуються ці ребра x, y і z. Якщо ребро xy, yz або zx (суцільні чорні лінії) мало б цей колір (фіолетовий), то воно б утворило трикутник з v. Інакше кожне з них має бути протилежного кольору, утворюючи трикутник xyz.

R(3,3) = 6

Припустимо, що ребра повного графа з 6 вершинами розфарбовані в червоний і синій кольори. Обреремо вершину ${\displaystyle v}$. До вершини ${\displaystyle v}$ прилягає 5 ребер, з яких (за принципом Діріхле) принаймні 3 повинні бути одного кольору. Без втрати загальності, припустимо, що принаймні 3 ребер, які з'єднують вершину ${\displaystyle v}$ з вершинами ${\displaystyle r}$, ${\displaystyle s}$ і ${\displaystyle t}$, є синіми. (У протилежному випадку, надалі поміняємо червоний і синій кольори місцями). Якщо будь-яке з ребер ${\displaystyle rs}$, ${\displaystyle rt}$, ${\displaystyle st}$ також синє, то ми отримаємо повністю синій трикутник. Інакше ці три ребра будуть червоними, і ми отримаємо повністю червоний трикутник. Оскільки дані міркування справедливі для будь-якого забарвлення, то будь-який ${\displaystyle K_{6}}$ містить одноколірний ${\displaystyle K_{3}}$, і тому ${\displaystyle R(3,3)\leq 6}$. Аналогом цього твердження є теорема про друзів і незнайомців.

Ще один спосіб доведення полягає у подвійному підрахунку. Для цього слід підрахувати кількість впорядкованих трійок вершин ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle z}$, таких, що ребро ${\displaystyle xy}$ має червоний колір, а ребро ${\displaystyle yz}$ – синій. По-перше будь-яка вершина буде серединою ${\displaystyle 0\times 5=0}$ (всі ребра від вершини мають один колір), ${\displaystyle 1\times 4=4}$ (чотири мають один колір, одне має інший колір), або ${\displaystyle 2\times 3=6}$ (три мають один колір, два мають інший). Отже, існує всього ${\displaystyle 6\times 6=36}$ таких трійок. По-друге, для будь-якого різнокольорового трикутника ${\displaystyle xyz}$ існує рівно дві такі трійки. Отже, загалом існує 18 різнокольорових трикутників. Звідси випливає, що принаймні 2 з 20 трикутників у ${\displaystyle K_{6}}$ є одноколірними.

І навпаки, можна розфарбувати ${\displaystyle K_{5}}$ двома кольорами, при цьому не створюючи жодного одноколірного ${\displaystyle K_{3}}$, з чого випливає, що ${\displaystyle R(3,3)>5}$. Унікальне розфарбування показано на початку сторінки. Таким чином, ${\displaystyle R(3,3)=6}$.

Задача на доведення того, що ${\displaystyle R(3,3)\leq 6}$, була однією з задач математичної олімпіади Вільяма Лоуелла Путнама в 1953 році, а також угорської математичної олімпіади в 1947 році.

Рис. 1

Багатоколірний приклад: R(3,3,3) = 17

Рис. 2

Багатоколірним числом Ремзі називається число Ремзі, що включає 3 або більше кольорів. Відомо (з урахуванням симетрій) лише два нетривіальних багатоколірних числа Ремзі, для яких відоме їх точне значення, а саме ${\displaystyle R(3,3,3)=17}$ і ${\displaystyle R(3,3,4)=30}$.

Припустимо, що ми розфарбували ребра повного графа трьома кольорами: червоним, зеленим і синім. Припустимо надалі, що розфарбування ребер не містить одноколірних трикутників. Аналогічно до попереднього прикладу виберемо вершину ${\displaystyle v}$. Розглянемо множину вершин, які мають спільне з вершиною ${\displaystyle v}$ червоне ребро. Це називається червоним сусідством ${\displaystyle v}$. Червоне сусідство ${\displaystyle v}$ не може містити червоних ребер, оскільки в іншому випадку утворився б червоний трикутник, що складається з двох кінців цього червоного ребра та вершини ${\displaystyle v}$. Отже, індуковане забарвлення ребер у червоному сусідстві ${\displaystyle v}$ має ребра, забарвлені лише двома кольорами, а саме зеленим і синім. Оскільки ${\displaystyle R(3,3)=6}$, червоне сусідство ${\displaystyle v}$ може містити не більше 5 вершин. Аналогічно, зелене і синє сусідства ${\displaystyle v}$ можуть містити не більше 5 вершин кожне. Оскільки кожна вершина, крім самої ${\displaystyle v}$, знаходиться в одному з червоних, зелених або синіх сусідств v, весь повний граф може мати не більше ${\displaystyle 1+5+5+5=16}$ вершин. Таким чином, маємо ${\displaystyle R(3,3,3)\leq 17}$.

Щоб переконатися, що ${\displaystyle R(3,3,3)=17}$, достатньо намалювати розфарбування ребер на повному графі з 16 вершинами та 3 кольорами, що виключає одноколірні трикутники.Виявляється, що існує рівно два таких розфарбування на ${\displaystyle K_{16}}$, так звані нескручені та скручені розфарбування. Обидва показані на рисунках праворуч, де нескручене розфарбування знаходиться зверху, а скручене – знизу.

Граф Клебша

Якщо ми виберемо навмання колір з нескрученого або скрученого забарвлення на ${\displaystyle K_{16}}$ і розглянемо граф, ребра якого мають саме цей колір, ми отримаємо граф Клебша.

Відомо, що існує рівно два забарвлення ребер трьома кольорами на ${\displaystyle K_{15}}$, які не утворюють одноколірних трикутників і які можна побудувати, вилучивши будь-яку вершину з нескрученого або скрученого забарвлення на ${\displaystyle K_{16}}$ відповідно.

Також відомо, що існує рівно 115 розфарбувань ребер трьома кольорами на ${\displaystyle K_{14}}$, які уникають одноколірних трикутників, за умови, що ми розглядаємо розфарбування ребер, які відрізняються перестановкою кольорів, як однакові.

Доведення

Випадок з 2 кольорами

Теорема для випадку 2 кольорів може бути доведена індукцією по ${\displaystyle r+s}$. З визначення випливає, що для всіх ${\displaystyle n}$, ${\displaystyle R(n,2)=R(2,n)=n}$. Це дає початок індукції. Ми доводимо, що ${\displaystyle R(r,s)}$ існує, знаходячи для нього явну межу. За індуктивною гіпотезою ${\displaystyle R(r-1,s)}$ і ${\displaystyle R(r,s-1)}$ існують.

Лема 1. ${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1).}$

Доведення. Розглянемо повний граф на вершинах ${\displaystyle R(r-1,s)+R(r,s-1)}$, ребра якого зафарбовані двома кольорами. Виберемо вершину ${\displaystyle v}$ з графа і розіб'ємо решту вершин на дві множини ${\displaystyle M}$ і ${\displaystyle N}$ так, що для кожної вершини ${\displaystyle w}$ вершина ${\displaystyle w}$ належить множині ${\displaystyle M}$, якщо ребро ${\displaystyle vw}$ зафарбоване синім кольором, і вершина ${\displaystyle w}$ належить множині ${\displaystyle N}$, якщо ребро ${\displaystyle vw}$ зафарбоване червоним кольором. Оскільки граф має ${\displaystyle R(r-1,s)+R(r,s-1)=|M|+|N|+1}$ вершин, з цього слідує, що або ${\displaystyle |M|\geq R(r-1,s)}$, або ${\displaystyle |N|\geq R(r,s-1)}$. У попередньому випадку, якщо ${\displaystyle M}$ має червоний ${\displaystyle K_{s}}$, то його має і початковий граф, і ми закінчуємо. В іншому випадку ${\displaystyle M}$ має синій ${\displaystyle K_{r-1}}$, і тому ${\displaystyle M\cup \{v\}}$ має синій ${\displaystyle K_{r}}$ за визначенням ${\displaystyle M}$. Останній випадок аналогічний. Отже твердження є вірним, і ми завершили доведення для 2 кольорів.

У цьому двоколірному випадку, якщо ${\displaystyle R(r-1,s)}$ і ${\displaystyle R(r,s-1)}$ є парними, то нерівність можна посилити до:

${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)-1}$

Доведення. Припустимо, що ${\displaystyle p=R(r-1,s)}$ і ${\displaystyle q=R(r,s-1)}$ є парними. Нехай ${\displaystyle t=p+q-1}$ і розглянемо двоколірний граф з ${\displaystyle t}$ вершинами.Якщо ${\displaystyle d_{i}}$ є степенем ${\displaystyle i}$-ї вершини в синьому підграфі, то за лемою про рукостискання ${\displaystyle \displaystyle \textstyle \sum _{i=1}^{t}d_{i}}$ є парною. Оскільки ${\displaystyle t}$ є непарним, то має існувати парне ${\displaystyle d_{i}}$. Припустимо без втрати загальності, що ${\displaystyle d_{1}}$ є парним, а ${\displaystyle M}$ і ${\displaystyle N}$ є вершинами, суміжними з вершиною ${\displaystyle 1}$ у синьому та червоному підграфах відповідно. Тоді обидва ${\displaystyle |M|=d_{1}}$ і ${\displaystyle |N|=t-1-d_{1}}$ є парними. За принципом Діріхле або ${\displaystyle |M|\geq p-1}$, або ${\displaystyle |N|\geq q}$. Оскільки ${\displaystyle |M|}$ є парним , а ${\displaystyle p-1}$ – непарне, то першу нерівність можна посилити, і тоді або ${\displaystyle |M|\geq p}$, або ${\displaystyle |N|\geq q}$. Припустимо, що ${\displaystyle |M|\geq p=R(r-1,s)}$. Тоді або підграф ${\displaystyle M}$ має червоний ${\displaystyle K_{s}}$ і доказ завершено, або він має синій ${\displaystyle K_{r-1}}$, який разом з вершиною ${\displaystyle 1}$ утворює синій ${\displaystyle K_{r}}$. Випадок ${\displaystyle |N|\geq q=R(r,s-1)}$ розглядається аналогічно.

Випадок більшої кількості кольорів

Лема 2. Якщо ${\displaystyle c>2}$, то ${\displaystyle R(n_{1},...,n_{c})\leq R(n_{1},...,n_{c-2},R(n_{c-1},n_{c})).}$

Доведення. Розглянемо повний граф з ${\displaystyle R(n_{1},...,n_{c-2},R(n_{c-1},n_{c}))}$ вершинами і зафарбуємо його ребра ${\displaystyle c}$ кольорами. Уявімо тепер, що ми не розрізняємо кольори ${\displaystyle c-1}$ і ${\displaystyle c}$ мають однаковий колір. Таким чином, граф тепер зафарбований ${\displaystyle c-1}$ кольорами. Згідно з визначенням ${\displaystyle R(n_{1},...,n_{c-2},R(n_{c-1},n_{c}))}$, такий граф містить або ${\displaystyle K_{n_{i}}}$, забарвлений кольором ${\displaystyle i}$ для ${\displaystyle 1\leq i\leq c-2}$, або ${\displaystyle K_{R(n_{c-1},n_{c})}}$ , забарвлений "розмитим кольором".У першому випадку ми закінчили. У другому випадку ми знову розрізняємо кольори і бачимо з визначення ${\displaystyle R(n_{c-1},n_{c})}$, що ми маємо або ${\displaystyle K_{n_{c-1}}}$,забарвлений кольором ${\displaystyle c-1}$, або ${\displaystyle K_{n_{c}}}$, забарвлений кольором ${\displaystyle c}$. В обох випадках доказ завершено.

Лема 1 показує, що будь-яке ${\displaystyle R(r,s)}$ є скінченним. Права частина нерівності в Лемі 2 виражає число Ремзі для ${\displaystyle c}$ кольорів у вигляді чисел Ремзі для меншої кількості кольорів. Тому, будь-яке ${\displaystyle R(n_{1},...,n_{c})}$ є скінченним для довільної кількості кольорів. Це доводить теорему.

Для гіперграфа

m-гіперграфом є гіперграф, ребра якого є набором із m вершин.

Для натуральних чисел ${\displaystyle \ m,c,n_{1},\ldots ,n_{c}}$, існує натуральне число ${\displaystyle \ R(n_{1},\ldots ,n_{c};m)}$ таке, що повний m-гіперграф порядку R, ребра якого розфарбовані в c різних кольорів, в якому для деякого числа i від 1 до c, існує повний під-m-гіперграф порядку ${\displaystyle \ n_{i}}$ кольору i.

Теоретико-множинне формулювання

Якщо X зліченна множина і всі множини X(n) (підмножини X потужності n) розфарбовані в c різних кольорів. Тоді існує нескінченна підмножина M в X, така що всі підмножини M потужності n мають однаковий колір.

Див. також

• Теорема Ердеша — Секереша
• Проблема трійок Буля — Піфагора
• Число ван дер Вардена

Джерела

• Теорема Ремзі [Архівовано 22 грудня 2011 у Wayback Machine.]
• Теорія Ремзі [Архівовано 5 червня 2008 у Wayback Machine.]
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, pp. 77–82, ISBN 978-0-13-602040-0
• Do, Norman (2006). "Party problems and Ramsey theory" (PDF).
• Radziszowski, Stanisław (2011). "Small Ramsey Numbers". Dynamic Surveys. Electronic Journal of Combinatorics. 1000 DS1: Mar 3. doi:10.37236/21.
• "Party Acquaintances".