Муниципальное автономное общеобразовательное учреждение

"Средняя общеобразовательная школа №7 с углублённым изучением

отдельных предметов" ГО Первоуральск Свердловской области

Комбинаторная

геометрия

Автор Ю.А. Павлов, учитель математики высшей квалификационной

категории

Первоуральск, 2016 г.

Содержание

Введение

3

Теорема Хелли. Проблема Хадвигера

4

Хроматическое число пространства

8

Проблема Борсука

11

Заключение

17

Список использованной литературы

18

Введение

Предложенная

мной

тема

«Комбинаторная

геометрия»,

может

быть

использована учителями математики для факультативных занятий в классах с

углублённым

изучением

математики,

поскольку

я

предлагаю

не

только

теоретический

материал,

но

и

практические

задачи.

Может

быть

использована

и

по

другому

–

предложите

ученикам

эту

тему

для

исследовательской работы и сопровождайте их.

Комбинаторная геометрия – это современная и бурно развивающаяся

наука, находящаяся на стыке геометрии и дискретного анализа. Основные

задачи комбинаторной геометрии состоят в изучении комбинаторных свойств

различных

совокупностей

геометрических

объектов.

В

самостоятельную

дисциплину,

богатую

красивыми

и

трудными

проблемами,

а

также

разнообразными приложениями комбинаторная геометрия оформилась лишь

к

середине

ХХ

века.

И

значительную

роль

в

этом

сыграли

такие

основополагающие задачи, как проблема Борсука о разбиении множеств на

части

меньшего

диаметра,

проблема

Нелсона-Хадвигера

о

раскрасках

метрических пространств и др.

Позже

пришло

понимание

глубокой

связи

между

задачами

комбинаторной геометрии и теоретико-графовой проблематикой. Оказалось,

что многие геометрические вопросы легко выражаются на языке теории

графов и на языке теории кодирования.

В

данном

работе

раскрываются

основные

вопросы

и

известнейшие

задачи комбинаторной геометрии, тесно связанные между собою, которыми

активно занимаются ведущие специалисты в мире.

Такой

является

задача

Борсука,

предложенная

в

1933

году.

За

прошедшие 70 лет, она сделалась едва ли не самой популярной в своей

области.

Собственно

говоря,

комбинаторная

геометрия

как

раз

и

сформировалась на основе таких ярких задач, как задача о хроматическом

числе или, скажем, задача Хелли. И, разумеется, проблема Борсука

сыграла в процессе формирования данного раздела математики одну из

главных ролей.

Сразу мы познакомимся с теоремой Хелли и проблемой Хадвигера.

Затем разберем хроматическое число пространства. И, конечно же, следует

понять, в чём же состоит вопрос Борсука – вопрос, которому суждено было

оказать столь существенное влияние на развитие современной науки.

Теорема Хелли. Проблема Хадвигера

Н а рис.1

каждый

из

шести

кругов

имеет

общую

точку

с

кругом,

расположенным

внутри;

при

этом

никакие

два

круга

не

имеют

общих

внутренних точек. А на рис.2 имеется восемь квадратов, каждый из которых

также имеет общую точку с внутренним квадратом (и снова фигуры попарно

не

имеют

общих

внутренних

точек).

А

можно

ли

вокруг

некоторой

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

полученных

из

исходной

с

помощью

параллельного

переноса?

Ответ

отрицателен, хотя доказать это и непросто.

Рис. 1.

Рис. 2.

Рассмотренный вопрос относится к комбинаторной геометрии – новой

ветви

математики,

сформировавшейся

лишь

в

XX

в.

Она

занимается

различными задачами, связанными с взаимным расположением нескольких

фигур (чаще всего выпуклых), с разрезанием фигур на части, с освещением

границы фигуры несколькими источниками света и т. п. При этом всегда

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

расположенных

так,

как

говорилось

выше,

найти

наименьшее

число

параллельных световых пучков, освещающих всю границу выпуклого тела

(рис. 3), и т. п. Различных постановок комбинаторно-геометрических задач

очень много, причем, как правило, они легко формулируются, но решение

каждой из них требует огромных усилий.

Рис. 3.

В настоящее время в комбинаторной геометрии выделились несколько

ведущих

направлений.

Одним

из

них

является

круг

задач,

связанных

с

теоремой Хелли. Австрийский математик в 1913 г. открыл следующий факт:

«Если из нескольких заданных на плоскости выпуклых фигур каждые три

имеют общую точку, то тогда существует точка, принадлежащая всем этим

фигурам». Требование выпуклости в этом утверждении существенно.

Действительно, на рис. 4 изображены четыре фигуры, из которых лишь

одна невыпуклая, однако хотя у любых трех из них есть общая точка, но нет

точки, общей всем четырем фигурам.

Рис. 4.

Для выпуклых тел (в пространстве) теорема Хелли в приведенном виде

неверна.

Чтобы

в

этом

убедиться,

достаточно

рассмотреть

четыре

треугольника,

образующих

грани

треугольной пирамиды.

Однако

если

потребовать, чтобы у системы выпуклых тел в пространстве каждые четыре

тела имели общую точку, то тогда и все эти тела будут иметь общую точку.

Теорема

Хелли

в

соответствующей

формулировке

была

доказана

для

пространства произвольного числа измерений и в этом виде оказалась очень

полезной во многих математических исследованиях.

Из теоремы Хелли следует, что для любого набора точек на плоскости,

такого,

что

каждые

три

его

точки

можно

покрыть

кругом

радиуса

r

,

найдется такой круг радиуса

r

, который покроет все эти точки.

Вот

еще

пример

утверждения,

которое

легко

получить

из

теоремы Хелли. В параллелограмме (или иной центрально симметричной

фигуре) имеется такая точка O , что на любой прямой, проходящей через O,

высекаются

отрезки AO,

BO,

отношение

которых

равно

1 (рис.

5).

В

треугольнике

такой

точки

нет,

но

можно

выбрать

такую

точку O,

что

отношение отрезков AO и BO заключено между 1/2 и 2 (рис. 6). Оказывается,

что внутри любой выпуклой фигуры

F на плоскости найдется такая точка O,

для которой отношение отрезков AO и BO (на любой прямой, проходящей

через O)

заключено

между

1/2 и

2 . Треугольник

в

этом

смысле

самая

несимметричная фигура.

Рис. 5.

Рис. 6.

Теорема Хелли и различные ее обобщения и применения составляют

сегодня важный раздел комбинаторной геометрии. Причем применяется она

не

только

в

геометрии,

но

и

во

многих

других

областях

математики.

Например, в прошлом столетии русский математик П. Л. Чебышев установил

ряд интересных свойств функций, «наименее уклоняющихся от нуля». А

впоследствии

оказалось,

что

свойства

этих

функций

проще

выводятся

именно с помощью теоремы Хелли.

Вот

интересная

комбинаторная

проблема,

еще

не

решенная

для

пространства.

На

рис. 7

показано,

что параллелограмм можно покрыть

четырьмя

меньшими

параллелограммами,

полученными

из

данного

гомотетиями

(преобразованиями подобия). А иные фигуры – даже тремя

меньшими

«копиями» (рис. 8). Ясно, что в пространстве надо разрешить

иметь восемь меньших «копий»: ведь параллелепипед нельзя покрыть семью

меньшими

гомотетичными

параллелепипедами

(поскольку

сразу

две

вершины одной меньшей «копией» не покрываются). Но можно ли любое

выпуклое тело в пространстве покрыть восемью меньшими гомотетичными

телами?

Это

неизвестно

даже

для

выпуклых

многогранников.

Гипотеза

швейцарского

математика

Хадвигера

(любое

выпуклое

тело

может

быть

покрыто 8 меньшими гомотетичными «копиями») еще ждет своего решения.

Рис. 7.

Рис. 8.

Удивительно,

что

проблема

Хадвигера

эквивалентна

следующей

проблеме, поставленной советским математиком В. Г. Болтянским: какое

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

всю границу выпуклого тела? В частности, границу любого ли выпуклого

трехмерного

многогранника

можно

осветить

восемью

параллельными

пучками лучей? При этом лучи, проходящие по касательной, как на рис. 9, не

считаются

освещающими

точку

касания

(т.е.

луч,

освещающий

точку M,

должен после прохождения через эту точку войти внутрь тела, рис. 10).

Рис. 9.

Рис. 10.

Интересно

отметить,

что

теорема

об

эквивалентности

указанных

проблем справедлива лишь для ограниченных выпуклых фигур.

На рис. 11

показано, что для параболической области F любая меньшая гомотетичная

фигура

содержит

лишь

конечную

дугу MN границы

фигуры F.

Поэтому

нужно бесконечное число «копий», чтобы покрыть всю фигуру F, т.е. для

этой фигуры число Хадвигера равно

. А число освещающих параллельных

пучков равно 1 (рис. 12).

Рис. 11.

Рис. 12.

Хроматическое число пространства

Один из самых известных и ярких объектов в комбинаторной геометрии

– это хроматическое число пространства. Прежде чем ввести его, напомним,

что пространство

R

n

, называемое n-мерным евклидовым пространством, –

это

просто

множество

всех

«точек» x,

каждая

из

которых

е сть

последовательность, состоящая из n действительных чисел: x= (x

1

, . . . , x

n

).

При этом между любыми двумя точками x= (x

1

, . . . , x

n

) и y= (y

1

, . . . , y

n

)

можно померить расстояние по формуле

|

x

−

y

|

=

√

(

x

1

−

y

1

)

2

+

…

+

(

x

n

−

y

n

)

2

В частности, при n = 1 получаем обычную прямую, при n = 2 – обычную

плоскость, при n = 3 – обычное пространство.

Так вот, хроматическое число

R

n

– это величина, обозначаемая χ(

R

n

)

и равная минимальному количеству цветов, в которые можно так раскрасить

все точки пространства

R

n

, чтобы между точками одного цвета не было

расстояния 1.

Рассмотрим ряд задач по данной теме.

Задача 1. Докажите, что χ(

R

1

) = 2.

Доказательство. Очевидно,

что

в

один

цвет

раскрасить

нельзя,

поскольку точки 1 и 2 должны быть разных цветов. А в два можно. Для этого

разобьем всю прямую на полуинтервалы [a; a + 1) для всех целых точек a и

раскрасим эти интервалы по очереди в черный и белый цвета.

Задача 2. Докажите, что χ(

R

2

) ≥ 4.

Доказательство. Очевидно,

что

приведенную

ниже

фигуру (рис. 13)

нельзя правильным образом раскрасить в 3 цвета.

Рис. 13.

Задача 3. Докажите, что χ(

R

2

) ≤ 7.

Доказательство. Каждый желающий без труда может убедиться, что

подходит следующая раскраска (рис. 14):

Рис. 14.

Задача 4. Докажите, что χ(

R

3

) ≤ 27.

Доказательство. Задача является частным случаем задачи 7.

Задача 5.

Докажите, что χ(

R

3

) ≥ 5.

Доказательство. Задача является частным случаем задачи 9.

Задача 6. Докажите, что χ(

R

n

) ≤

(

|

√

n

|

+

1

)

n

.

Доказательство. Зафиксируем два числа k

∈

N

и p

∈

R

, после чего

разобьем

пространство

R

n

на кубики с ребром kp. Теперь каждый кубик

разделим на

k

n

меньших кубиков, с ребром p у каждого.

Зафиксируем один большой кубик и все маленькие кубики внутри него

раскрасим каждый в свой цвет (всю внутренность и грани, прилегающие к

вершине

с

наименьшей

суммой

координат.В

этот

же

цвет

красим

соединяющие их рёбра, при этом вершину красим только одну, как раз ту, у

которой наименьшая сумма координат), после чего точно такими же цветами

и в таком же порядке раскрасим все маленькие кубики внутри остальных

больших кубов. Тогда, чтобы раскраска была правильной, необходимо, чтобы

выполнялось два неравенства:

p

√

n ≤1,

(

k

−

1

)

p ≥1.

Но для

k

=

|

√

n

|

+

1

и

p

=

1

√

n

эти неравенства, очевидно, выполнены.

Задача 7. Докажите, чтоχ(

R

n

) конечно при любом n.

Доказательство. Это очевидное следствие предыдущей задачи.

Задача 8.

Докажите,

что

в

R

n

есть

множество

из n +

1

точек,

попарные расстояния между которыми равны 1, а стало быть,

χ(

R

n

) ≥n + 1.

Доказательство. Давайте

построим

такое

множество

точек

в

явном

виде. Положим

A

1

=

(

√

2

2

; 0; 0; … ; 0 ; 0

)

A

2

=

(

0 ;

√

2

2

; 0; … ;0 ;0

)

…

A

1

=

(

0 ; 0 ; 0 ; … ; 0;

√

2

2

)

Понятно, что попарные расстояния между этими n точками равны по 1.

А (n + 1)-ю точку найдем в виде S = (a; a; a; . . .;a; a).

S A

i

=

√

(

n

−

1

)

a

2

+

(

a

−

√

2

2

)

2

=

1

na

2

−

√

2 a

−

1

2

=

0.

Несложно убедиться, что дискриминант этого квадратного уравнения

положителен. И у нас найдутся сразу две точки S

1

и S

2

, от каждой из которых

до любой A

i

расстояние равно 1.

Задача 9. Докажите, что χ(

R

n

) ≥ n + 2.

Доказательство. Возьмем

две

фигуры,

аналогичные

построенным

в

задаче 8, S

1

S

2

A

1

. . . A

n

и равную ей T

1

T

2

B

1

. . . B

n

. Разместим их в пространстве

так, чтобы точка S

1

совпадала с точкой T

1

, а расстояние S

2

T

2

равнялось 1. Если

мы захотим раскрасить пространство в n + 1 цвет, то точки S

1

и S

2

будут

одного цвета, и точки T

1

и T

2

будут одного цвета. Значит S

2

и T

2

будут одного

цвета, но это невозможно.

Проблема Борсука

Эта классическая проблема комбинаторной геометрии возникла в 1933

году

благодаря

польскому

математику

К.

Борсуку.

Пусть

Ω

⊂

R

n

–

произвольное множество диаметра 1 (диаметр – это супремум попарных

расстояний между точками множества; обозначается diam Ω).

A что такое произвольное множество в пространстве? Конечно,

каждый из нас может вообразить себе уйму разных множеств. Скажем, это

могут быть и конечные наборы точек, и какие-нибудь фигуры (если

речь идёт о двумерном пространстве) или

тела

(если

мы

говорим

о

трёхмерном пространстве), и многое, многое другое (см. рис. 15).

Рис. 15.

Небольшая неприятность состоит в том, что иной раз в науке

возникают чрезвычайно хитрые множества, которые и описать-то толком

не

удаётся.

Мы

не

станем

забираться

здесь

в

теоретико-множественные

дебри. Взамен мы предложим представлять себе те множества, какие сами

посчитаете возможным.

Повторимся,

пусть

Ω

⊂

R

n

–

произвольное

множество

диаметра

1

(диаметр – это супремум попарных расстояний между точками множества;

обозначается diam Ω).

Обозначим через f (Ω) минимальное число частей меньшего диаметра, на

которые можно разбить Ω.

То есть проблема может быть сформулирована следующим образом:

найти минимальное число частей меньшего диаметра, на которые может быть

разбито произвольное ограниченное множество в пространстве.

Нетрудно видеть, что f (Ω) всегда конечно. Например, можно покрыть Ω

кубом со стороной 1 и затем разбить куб на кубики диаметра <1 (таких

кубиков

будет

заведомо

не

больше

n

n

). В итоге корректно определена

величина

f

(

n

)

=

max f

(

Ω

)

,

где

максимум

берётся

по

всем

множествам

диаметра 1. Иными словами,

f

(

n

)

– это минимальное количество частей

меньшего

диаметра,

на

которые

разбивается

произвольное

множество

диаметра 1 в -мерном евклидовом пространстве.

В

1933

году

Борсук

высказал

гипотезу

о

том,

что

f

(

n

)

=

n

+

1

.

Мотивировками

для

гипотезы

послужили

следующие

факты.

Во-первых,

очевидно,

ч то

f

(

n

)

≥ n

+

1

(достаточно

взять

множество

Ω

вершин

правильного

-мерного

симплекса

со

стороной

1

и

убедиться

в

том,

что

f

(

Ω

)

=

n

+

1

). Более того, сам Борсук доказал, что

f

(

B

n

)

=

n

+

1

, где

B

n

– шар

в

R

n

. Во-вторых, столь же очевидно, что

f

(

1

)

=

2

, и не очень сложно

понять, что

f

(

2

)

=

3

(достаточно показать, что любое множество диаметра 1

на

плоскости

можно

движением

перевести

внутрь

правильного

шестиугольника с расстоянием 1 между параллельными сторонами, и затем

разбить шестиугольник на три части диаметра

√

3

2

=

0,866 …

<

1

).

Интрига

состояла

в

том,

что

большинство

специалистов

верило

в

справедливость гипотезы. И это немудрено: ещё в 1945 году Г. Хадвигер

показал, что если у Ω граница

C

1

гладкая,

то

f

(

Ω

)

≤n

+

1

. Казалось бы,

сгладим границу произвольного множества, и всё получится. Но не тут-то

было. Целых 60 лет прошло в попытках доказательства гипотезы, и в 1993

году она была опровергнута.

Авторы первого контрпримера к гипотезе Борсука – Дж. Кан и Г. Калаи –

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

опровержения

гипотезы.

Скажем

несколько

слов

об

основной

идее

результата.

Пусть

Ω

⊂

R

n

– конечное множество точек в пространстве. Назовём

графом

диаметров этого

множества

граф

G

Ω

=

(Ω,

E),

где

рёбра

из

множества Eвозникают

тогда

и

только

тогда,

когда

расстояние

между

соответствующими

вершинами

равно

диаметру

Ω.

Напомним,

что

хроматическим

числом г р а ф а

G

называется

минимальное

число

χ

(

G

)

цветов, в которые можно так покрасить все вершины графа, чтобы вершины,

соединённые ребром, имели разные цвета. Заметим, что

f

(

Ω

)

=

χ

(

G

Ω

)

,

и здесь важно, что Ω конечно. Хорошо известно, что

χ

(

G

)

≥

|

V

|

α

(

G

)

, где

V

–

множество вершин графа

G

,

а

α

(

G

)

–число

независимости графа, т. е.

размер самого большого подмножества множества его вершин, элементы

которого

попарно

не

соединены

рёбрами

(такое

подмножество

само

называется независимым). В итоге задача получения нижней оценки для

величины

f

(

n

)

может быть сведена к отысканию конечного графа диаметров

с большим отношением числа вершин к числу независимости. Именно такой

граф и нашли Кан и Калаи, использовав конструкцию, которую ещё в 1981

году предложили П. Франкл и Р. М. Уилсон.

У

Кана

и

Калаи

получилась

оценка

f

(

n

)

≥

(

1,203…

+

o

(

1

)

)

√

n

,

а

минимальная

размерность контрпримера оказалась равной 2015. Сейчас известно, что

(

1,2255 …

+

o

(

1

)

)

√

n

≤ f

(

n

)

≤

(

1,224 …

+

o

(

1

)

)

n

.

Также

известно,

что

гипотеза

верна

при

n≤ 3

и

неверна,

начиная

с

размерности 298.

Сейчас основными вопросами являются следующие два:

1.

Как устранить зазор между верхней экспоненциальной и нижней

субэкспоненциальной оценками величины

f

(

n

)

?

2.

Какова минимальная размерность контрпримера к гипотезе?

Мы

рискнём

предположить,

что

ответ

на

второй

вопрос

–

это

5.

Относительно первого вопроса трудно даже высказывать гипотезы.

Также

изучают

различные

структурные

свойства

графов

диаметров

(максимальное число рёбер, клик и др.). Подробнее о проблеме Борсука и об

устройстве графа диаметров можно почитать в источниках.

Вообще, история проблемы Борсука носит весьма драматический и в

чём-то почти детективный характер. Более того, эта проблема удивительно

тонким,

изящным

и

вместе

с

тем

неожиданным

образом

связана

с

упоминавшейся задачей о хроматическом числе.

Рассмотрим ряд задач.

Задача 10. Доказать, что

f

(

1

)

=

2

.

Доказательство. Очевидно

f

(

1

)

>

1

.

Так

как

любое

множество

диаметра

1

на

прямой

можно

поместить

внутри

отрезкадлины

1,

то

достаточно разбить отрезок на части меньшего диаметра: например, пополам.

Задача 11. Доказать, что

f

(

2

)

≥ 3.

Доказательство. Для доказательства данного утверждения достаточно

привести пример множества на плоскости диаметра 1, которое нельзя разбить

на

две

части

меньшего

диаметра.

Простейший

вариант

–

три

точки

в

вершинах

равностороннего

треугольника

со

стороной

1

(рис.

16).

Предполагая, что разбиение на две части удалось, имеем два множества, хотя

бы в одном из которых находятся хотя бы две исходные точки (пусть в

Ψ

¿

.

Они находятся на расстоянии 1, и, следовательно, диаметр этого множества

равен 1. Противоречие.

1

1

1

1

Рис. 16.

Рис. 17.

Задача 12. Доказать, что

f

(

3

)

≥ 4.

Доказательство. Аналогично задаче 11 достаточно привести пример

множества в трехмерном простарнстве диаметра 1, которое нельзя разбить на

три

части

меньшего

диаметра.

Простейший

вариант

–

«аналог»

равностороннего треугольника в пространстве – тетраэдр (достаточно его

вершин. рис. 17). Вновь предполагая, что разбиение на три части, возможно,

имеем три множества, хотя бы в одном из которых находятся хотя бы две

исходные

точки

(пусть

в

Θ

¿

.

Они

находятся

на

расстоянии

1,

и,

следовательно, диаметр этого множества равен 1. Противоречие.

Задача 13. Доказать, что

f

(

n

)

≥ n

+

1.

Доказательство. Рассмотрим

в

-мерном

пространстве

«аналог»

правильного тетраэдра и правильного треугольника -

n

-мерный симплекс.

Симплекс – фигура, состоящая из

n

+

1

точки, расстояние между любыми

двумя из которых равно 1. Т.о. отрезок длины 1 – 1-мерный симплекс,

правильный треугольник – 2-мерный симплекс, и правильный тетраэдр – 3-

мерный

симплекс.

Вновь

предполагая,

что

разбиение

на

n

частей,

возможно, найдется множество, включающее в себя хотя бы 2 из данных

точек (вершин симплекса. рис.18). Противоречие.

Рис. 18.

Задача 14. Докажите, что при любом разбиении круга радиуса

1

2

на 3

части найдется часть, диаметр которой не меньше

√

3

2

.

Доказательство. Пусть круг разрезан на три части. Возьмём точку на

границе круга, которая принадлежит двум из этих множеств, и построим

равносторонний треугольник с одной вершиной в выбранной точке, а двумя

другими

-

на

границе

круга.

Тогда

две

вершины

этого

треугольника

принадлежат одной части. Значит, диаметр этой части не меньше

√

3

2

.

Задача

15. Разбейте правильный шестиугольник на 3 части диаметра

√

3

2

. Выведите отсюда справедливость гипотезы Борсука на плоскости, а

также, в определенном смысле, «неулучшаемость» константы

√

3

2

.

Доказательство. Р а з р е же м

ш е с т и у гол ь н и к

н а

т р и

ч а с т и

перпендикулярами из центра к трём несмежным сторонам шестиугольника

(рис.19). Диаметр каждой части равен

√

3

2

. Теперь поместим множество

диаметра 1 внутрь шестиугольника. Это множество также разобьётся на

части диаметра не больше. А как мы знаем из предыдущей задачи, константа

неулучшаема в случае круга диаметра 1.

Рис. 19.

Задача 16. Докажите, что в любом множестве из n точек на плоскости

есть не более n пар точек, расстояние между которыми равно диаметру.

Доказательство. Соединим

ребром

пары

точек,

расстояние

между

которыми равно 1. Если из каждой точки выходит не более двух рёбер, то

всего не более n рёбер. Тогда рассмотрим тройку рёбер с общим концом. Так

как

расстояния

между

точками

не

более

1,

то

угол

между

рёбрами

не

превосходит 60◦.

Из другого конца среднего ребра не может выходить ребро, иначе бы его

конец был бы на расстоянии больше 1 от одного из концов рёбер. Потому

можно выкинуть среднее ребро вместе с его концом (необщим) и продолжить

доказательство по индукции.

Задача 17. Выведите из задачи 16 справедливость гипотезы Борсука

д л я конечных множеств

точек на плоскости (не прибегая к помощи

покрышек).

Доказательство. Достаточно

покрасить

вершины

графа

(рис.

20) из

решения предыдущей задачи в три цвета так, чтобы вершины одного цвета не

были

соединены

ребром.

Сделаем

это

по

индукции.

Если

есть

висячая

вершина, то выкинем её, оставшийся граф раскрасим по предположению

индукции, а её – в цвет, отличный от цвета её соседа. Если нет висячей

вершины, то из всех вершин выходит два ребра, а значит, мы имеем набор

циклов,

каждый

из

которых

можно

покрасить

в

три

цвета

требуемым

образом.

Рис 20.

Заключение

Таким образом, в выводе можно сказать, что комбинаторная геометрия

сформировалась на основе таких ярких задач, как задача о хроматическом

числе или, скажем, задача Хелли, гипотеза Борсука. Последняя сыграла в

процессе формирования данного раздела математики одну из главных

ролей.

Интрига

состояла

в

том,

что

большинство

специалистов

верило

в

справедливость гипотезы. И это немудрено: ещё в 1945 году Г. Хадвигер

показал, что если у Ω граница

C

1

гладкая, то

f

(

Ω

)

≤n

+

1

. Казалось бы,

сгладим границу произвольного множества, и всё получится. Но не тут-то

было. Целых 60 лет прошло в попытках доказательства гипотезы, и в 1993

году она была опровергнута.

Сейчас известно, что

(

1,2255 …

+

o

(

1

)

)

√

n

≤ f

(

n

)

≤

(

1,224 …

+

o

(

1

)

)

n

.

Основными вопросами являются:



Как

устранить

зазор

между

верхней

экспоненциальной

и

нижней

субэкспоненциальной оценками величины

f

(

n

)

?



Какова минимальная размерность контр примера к гипотезе?

Список использованной литературы

1.

Алон Н., Спенсер Дж. Вероятностный метод. — М.: Бином. Лаборатория

знаний, 2007. — 320 с.

2.

Колчин В.Ф. Случайные графы. — М.: Физматлит, 2004. — 256 с.

3.

Кошелев

В.А. Задача Эрдеша–Секереша о пустых шестиугольниках на

плоскости // Моделирование и анализ информационных систем. — 2009. — Т.

16, № 2. — с. 22–74.

4.

Райгородский А.М. Линейно-алгебраический метод в комбинаторике. —

М.: МЦНМО, 2007. — 136 с.

5.

Райгородский А.М. Модели случайных графов // Труды МФТИ. — 2010.

— Т. 2,№ 4(8). — с. 130–140.

6.

Райгородский

А.М. Проблема

Борсука

и

хроматические

числа

метрических пространств // Успехи матем. наук. — 2001. — Т. 56, вып. 1. —

с. 107–146.

7.

Райгородский А.М. Проблема Борсука. — М.: МЦНМО, 2006. — 56 с.

8.

Райгородский А.М. Хроматические числа. — М.: МЦНМО, 2003. — 44 с.

9.

Райгородский

А.М. Экстремальные задачи теории графов и анализ

данных. — М.: Регулярная и хаотическая динамика, 2009. — 120 с.

10.

Шабанов Д.А., Райгородский А.М. Задача Эрдеша–Хайнала о раскрасках

гиперграфов, ее обобщения и смежные проблемы // Успехи матем. наук. —

2011. — Т. 66.