Cтраница 2
Задача Хадвигера [1] состоит в том, чтобы найти наименьшее из таких натуральных чисел т, что в Rn найдутся тела К... [16]
В этих условиях также доказывается эквивалентность методов разбиения и дополнения, но. Именно, Хадвигер строит некоторую систему аддитивных С-инварпаптов и доказывает, что выполнение равенств Фа ( - 4) Фа ( В) для всех инвариантов qa построенной системы является необходимым и достаточным условием G-равносоставленности многогранников А и В. Если теперь многогранники А нВ являются G-равнодополняемыми, то, по теореме 15, Ф ( А) ф ( В) для любого аддитивного G-инварианта q, и потому, в силу сказанного выше, А - В. [17]
Неудивительно, что эта гипотеза связана с гипотезой четырех красок. Для - п5 гипотеза Хадвигера утверждает, что каждый 5-хроматический граф G стягиваем к К. Но по теореме 11.14 любой такой граф G обязательно непланарен. Таким образом, из гипотезы Хадвигера для / г 5 следует гипотеза четырех красок. [18]
Эта глава посвящена рассмотрению четырех тесно связанных между сабой задач комбинаторной геометрии. Стержнем главы является известная гипотеза Хадвигера [1] о том, что ограниченное выпуклое тело / ( может быть покрыто не более чем 2П телами, гомотетичными телу К с положительным коэффициентом гомотетии, меньшим единицы. В работе [2] введена еще одна задача комбинаторной геометрии - задача освещения. С, равно наименьшему числу освещающих пучков. В работах [3, 4] рассматриваются еще две задачи, близкие указанным. Оказалось [5], что для неограниченных выпуклых тел все четыре задачи р а з л и ч-н ы, хотя и тесно связаны. Кроме того, имеются отдельные результаты более частного характера. [19]
Существует несколько других гипотез о раскрасках, но именно гипотеза четырех красок получила наибольшую известность. Одну из наиболее интересных гипотез о раскрасках сформулировал Хадвигер [1]; в ней рассматриваются стягивания. [20]
Для каждого графа О существует наименьшее число п п ( 0), такое, что некоторый минор графа О является п-кли-кой. Это число представляет интерес в связи с знаменитой гипотезой Хадвигера, утверждающей, что вершины графа С, не имеющего петель, можно раскрасить в не более чем п ( 0) цветов. [21]
Этому и посвящен настоящий параграф. В конце его эта теорема излагается в той форме, которую ей первоначально придал Хадвигер. [22]
Общее понятие хроматического числа метрического пространства было предложено в 1976 году Бендой и Перлесом. Однако частные случаи рассматривались существенно раньше: еще в сороковые годы двадцатого века Эрдеш и Хадвигер дали ставшее ныне классическим определение величины x ( Rn) - хроматического числа п - мерного евклидова пространства. За прошедшие с тех пор шестьдесят лет были получены многочисленные результаты как в классической задаче, так и в ее обобщении. [23]
В силу теорем 14.1) и 12.4 Ь) функционал В инвариантен относительно движений, однороден 1 - й степени, непрерывен и линеен в смысле Минковского. Тот факт, что по су-и дела В - единственный функционал с такими свойствами, устанавливается следующей теоремой Хадвигера. [24]
Формализация этого отношения эквивалентности приводит к введенному Хадвигером [24] понятию алгебры многогранников, рассмотрению которого и посвящен этот параграф. [25]
Неудивительно, что эта гипотеза связана с гипотезой четырех красок. Для - п5 гипотеза Хадвигера утверждает, что каждый 5-хроматический граф G стягиваем к К. Но по теореме 11.14 любой такой граф G обязательно непланарен. Таким образом, из гипотезы Хадвигера для / г 5 следует гипотеза четырех красок. [26]
В 1903 году вышла работа Кагана [39], в которой рассуждения Дена были существенно усовершенствованы, изложены более систематично и популярно. Эти работы ( в частности, [21], [24], [27]) позволили по-новому взглянуть на работу Дена, получить основной ее результат на основе прозрачных идей в современном изложении. Единственным недостатком их изложения было применение аксиомы выбора ( связанное с использованием рациональных базисов в поле действительных чисел; ср. Наконец, в [6] было дано переработанное доказательство Хадвигера, в котором рассмотрение всей числовой прямой R заменено рассмотрением конечных множеств; это позволило избежать применения аксиомы выбора. Доказательство теоремы Дена, данное в [6], по-видимому, является наиболее простым. [27]