Комбинаторно-геометрические свойства точечных множеств тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Райгородский, Андрей Михайлович

• Райгородский, Андрей Михайлович
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Райгородский, Андрей Михайлович

Общая характеристика работы

1 Системы общих представителей

1.1 Постановка задачи. Определения и обозначения.

1.2 Формулировки основных результатов главы

1.3 Доказательство теоремы 1.1.

1.4 Доказательство теоремы 1.2.

1.5 Доказательство теоремы 1.3.

1.6 Замечание.

4'. *

2 Дефект допустимых множеств в решетке

2.1 Постановка задачи для октаэдров и шаров. Определения и обозначения.

2.2 Формулировки основных результатов главы для октаэдров и шаров.

2.3 Первая комбинаторная лемма.

2.4 Вторая комбинаторная лемма.

2.5 Доказательство теоремы 2.2.

2.6 Доказательство предложения 2.2.

2.7 Постановка обобщенной задачи.

2.8 Формулировка основного результата главы для множеств общего вида.

2.9 Обобщенная комбинаторная лемма.

2.10 Доказательство теоремы 2.3.

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

3.1 Построение контрпримера к гипотезе Борсука во всех размерностях d > 561.

3.2 Доказательство теоремы 3.2.

3.3 Проблема Борсука для (0,1) - многогранников и кросс - политопов.

3.3.1 Определения и обозначения

3.3.2 Формулировки основных результатов параграфа

3.3.3 Примеры.

3.3.4 Доказательство теорем 3.4 и 3.5.

3.3.5 Доказательство теоремы 3.3.

Введение диссертации (часть автореферата) на тему «Комбинаторно-геометрические свойства точечных множеств»

В диссертации рассматривается несколько задач, лежащих, по существу, на стыке двух весьма активно развивающихся разделов математики - геометрии чисел и комбинаторной геометрии. Комбинаторная геометрия занимается задачами о дискретных системах (выпуклых) тел и точек в (вообще говоря, не обязательно евклидовом) пространстве, имеющими ярко выраженный комбинаторный характер. Иными словами, задачи комбинаторной геометрии - это те задачи дискретной геометрии, которые удается свести к нахождению тех или иных целочисленных характеристик возможных расположений в пространстве упомянутых дискретных систем. В этом смысле многие задачи геометрии чисел также могут быть отнесены к комбинаторной геометрии. Существенное отличие состоит, однако, в том, что если задачи, решаемые в геометрии чисел, возникают, как правило, из теоретико - числовой проблематики, то вопросы, рассматриваемые в комбинаторной геометрии, обусловлены задачами, геометричными по своей сути.

В геометрии чисел, основанной трудами Эрмита, Мин-ковского и Вороного и очень активно развивавшейся впоследствии, благодаря работам Касселса, Давенпорта, Малера, Зигеля, Морделла, Роджерса, Шмидта, Рышкова и др., изучается весьма широкий круг задач и методов, успешно прилагаемых к различным проблемам теории чисел. Так, в связи с задачами теории диофантовых приближений, а также с некоторыми вопросами алгебраической теории чисел, целесообразным оказывается рассматривать такую дискретную систему точек в евклидовом пространстве, как решетка - целочисленная линейная оболочка некотрого множества линейно независимых векторов в пространстве, - являющаяся, по существу, основным объектом геометрии чисел. Тем самым естественными вопросами геометрии чисел становятся, в частности, вопросы, связанные с выявлением тех или иных комбинаторных свойств точечных множеств, образующих решетку в пространстве (см. [6], [32]).

С другой стороны, следует отметить, уточняя сказанное, что многие задачи теории диофантовых приближений удается переформулировать на геометрическом языке в терминах допустимых множеств в решетке, что, в свою очередь, позволяет получать весьма глубокие результаты. Таким образом, несомненный интерес представляет выделение комбинаторных свойств тех решеток, относительно которых некоторое фиксированное множество (тело) является допустимым (см. [6], [32]).

Термин "комбинаторная геометрия" восходит, по - видимому, к трудам Хадвигера (см. [35], [36]). Основными задачами комбинаторной геометрии принято считать проблему Борсука о разбиении ограниченных множеств ненулевого диаметра на части меньшего диаметра (см. [2], [19], [23], [24], [27], [34]), задачу Хадвигера - Гохберга - Маркуса - Болтянского об освещении границы выпуклого тела в евклидовом пространстве (см. [1], [2], [23]), задачу Грюнбаума о покрытии тела единичного диаметра шарами радиуса 1/2 (см. [4]), задачи, связанные с теоремой Хелли (см. [4] и [17]), и пр. В частности, задача Борсука, сформулированная еще в 1933 году (см. [24]), является едва ли не классической задачей математики, на протяжении многих лет привлекавшей и продолжающей привлекать внимание крупнейших специалистов, работающих в области комбинаторной геометрии. В последние же годы существенный прогресс в решении этой задачи был достигнут, благодаря работе Кана и Калаи (см. [39]), в которой был получен многомерный контрпример к гипотезе Борсука как раз за счет рассмотрения некоторого конечного точечного множества в евклидовом пространстве и определения комбинаторных свойств этого множества. Тем самым одним из приоритетных направлений в комбинаторной геометрии представляется дальнейшая разработка методов, позволяющих с помощью построения дискретных точечных множеств, обладающих надлежащими комбинаторными свойствами, получать различные результаты, касающиеся проблемы Борсука: например, понижать размерность контрпримера, предъявленного Каном и Калаи.

Диссертация делится на четыре главы. В первой главе доказываются различные новые асимптотики для мощности минимальной системы общих представителей, возникающей в задаче о покрытии некоторой системы подмножеств конечного множества множеством заданного вида. Эти результаты напрямую связаны с работами Эрдеша, Спенсера, Турана, Леонтьева, Кузюрина и др. (см. [8], [9], [18], [21], [40], [52]) и их следует рассматривать скорее как иллюстрацию некоего общего подхода, который в той или иной мере будет обсуждаться во второй и третьей главах. Вторая глава связана с некоторой экстремальной задачей геометрии чисел и, в частности, с комбинаторикой допустимых множеств в решетке. В этой главе излагается уже один из основных результатов диссертации, дается обзор близких задач и формулируются некоторые возможные обобщения (качественно иные возможные обобщения формулируются в четвертой главе - приложении). Наконец, третяя глава посвящена исследованию проблемы Борсука именно в упомянутом выше ключе: строятся различные конечные точечные конфигурации в евклидовом пространстве и доказываются комбинаторные свойства этих конфигураций, позволяющие, кроме всего прочего, получать контрпримеры к гипотезе Борсука в размерностях, существенно меньших, чем те, в которых это удавалось сделать до сих пор.

Благодарности. Соискатель считает своим приятным долгом в первую очередь поблагодарить Н.Г. Мощевитина за постановку задач, постоянный интерес и внимание к его работе. Соискатель также благодарит Н.П. Долбилина за неоднократную помощь и поддержку.

Общая характеристика работы

Актуальность темы диссертации. В работе изучаются комбинаторные свойства некоторых дискретных точечных множеств в евклидовом пространстве. С одной стороны, рассматриваются некоторые комбинаторные характеристики реперов решеток, относительно которых допустимо (фиксированное) множество в пространстве. Интерес к такого рода задачам геометрии чисел восходит к работам Морделла, Кьюсика, Бантеньи и Рышкова (см. [13], [22], [28], [43]), где схожие комбинаторные характеристики были детально изучены в малых размерностях. Все эти результаты тесно связаны с классическими задачами геометрии чисел, - например, с задачей определения минимума квадратичной формы (см. [13], [6] и [32]). Однако с ростом размерности никаких общих результатов до сих пор получено не было, и, стало быть, представляет несомненный интерес рассмотрение свойств подобных комбинаторно - геометрических характеристик в растущей размерности (см. [10] в этой связи).

С другой стороны, в работе рассматривается задача Борсука о разбиении ограниченных неодноточечных множеств в евклидовом пространстве на части меньшего диаметра. Эта задача была впервые сформулирована Борсуком еще в 1933 году (см. [24]), и популярность ее не вызывает сомнений. Так, различные результаты, связанные с этой задачей, были в разное время получены Грюнбаумом, Хадвигером, Роджерсом, Эглстоном, Шраммом и др. (см. [29], [33], [37], [48], [51]). Для решения задачи были предложены многочисленные подходы, позволившие доказать гипотезу Борсука в общем случае в размерностях 1, 2 и 3, а также в произвольной размерности для множеств с гладкой границей и для множеств, обладающих определенной симметрией. Наконец, в 1993 году Кан и Калаи (см. [39]) предложили совершенно иной подход к решению задачи Борсука и, в частности, опровергли гипотезу в размерностях (1 > 2015. В результате огромный интерес представляет любое нетривиальное понижение размерности контрпримера. Конечно, практически всякий результат такого рода обязан будет носить временный характер, и потому прежде всего необходимо сделать акцент на новизне предлагаемого метода и, как следствие, его актуальности для получения возможных дальнейших продвижений.

Кроме того, многочисленные результаты были получены в связи с проблемой отыскания различных оценок для минимального числа частей меньшего диаметра, на которые удается разбить произвольное ограниченное множество в евклидовом пространстве. Здесь следует отметить такие имена, как Лассак, Шрамм, Бургейн и Линденштраусс (см. [42], [51], [26]).

Наконец, проблема Борсука тесно связана с другими задачами комбинаторной геометрии: например, с задачей Хадвигера о нахождении так называемых хроматических чисел евклидова пространства и с задачей Грюнбаума о покрытии произвольного тела единичного диаметра шарами радиуса 1/2 (см. [4]).

Цель и задачи исследования. Целью диссертационной работы является получение различных результатов, касающихся свойств некоторых дискретных точечных множеств в евклидовом пространстве, и применение их к задачам геометрии чисел и комбинаторной геометрии. Основные задачи диссертации: доказательство как конструктивных, так и вероятностных теорем, связанных с комбинаторными свойствами реперов решеток, относительно которых (фиксированное) множество из весьма широкого класса оказывается допустимым; разработка нового подхода к построению контрпримеров к гипотезе Борсука и к получению нижних оценок на минимальное число частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество ненулевого диаметра, лежащее в евклидовом пространстве; получение новых верхних оценок на минимальное число частей меньшего диаметра для так называемых (0,1)

- многогранников и кросс - политопов.

Научная новизна полученных результатов. Все результаты диссертации являются новыми. Для доказательства ряда теорем, связанных с проблемой Борсука, применен в значительной мере усовершенствованный метод Кана

- Калаи - Алона. Кроме того, новым является применение методов задачи о покрытии для получения верхних оценок, касающихся проблемы Борсука для (0,1) - многогранников и кросс - политопов.

Практическая значимость полученных результатов. Диссертация носит теоретический характер. Ее результаты могут быть полезными при исследовании свойств решеток, близких к экстремальным, в задачах об упаковках и покрытиях, при исследовании свойств хроматических чисел различных метрических пространств.

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

1. Для величины дефекта с1*(П) (где О в {О},В}}, О} -единичный октаэдр в Е", ^ - единичный шар в И") допустимого множества П в решетке Л, такой, что Л/Ъп - циклическая группа, имеет место оценка с?* (О) . (теорема 2.2 из параграфа 2.2).

2. Для величины дефекта йп{О) (где О Е {О^В^}) допустимого множества О в произвольной решетке Л имеет место оценка <4(Г2) > п — О(щг^). (предложение 2.2 из параграфа 2.2).

3. Результат пункта 1 может быть обобщен на случай множеств О из весьма широкого класса, (теоремы 2.3, параграф 2.8, и 4.1, глава 4).

4. Строятся контрпримеры к гипотезе Борсука о разбиении ограниченных множеств ненулевого диаметра в евклидовом пространстве на части меньшего диаметра во всех размерностях с1 > 561. (теорема 3.1 и утверждение 3.1 главы 3).

5. В задаче Борсука для величины /(с?) (минимальное число частей меньшего диаметра, на которые может быть разбито всякое неодноточечное ограниченное множество в евклидовом пространстве) имеет место оценка /(сГ) > (2/л/З+ о( 1))^. (теорема 3.2 главы 3). б. Для минимального числа частей меньшего диаметра, на которые может быть разбит каждый (0,1) - многогранник и кросс - политоп из весьма широкого класса, имеет место верхняя оценка, лучшая, чем общая оценка для величины $(<1) (см. пункт 5). (теоремы 3.3 - 3.5 из главы 3).

Личный вклад соискателя. Все результаты диссертационной работы получены соискателем самостоятельно.

Апробация результатов. Результаты диссертации докладывались на международной конференции "Современные проблемы теории чисел и ее приложения" (г. Тула, 1996 г.), на второй международной конференции "Алгебра, геометрия и комбинаторика" в Порту (Португалия, 1998 г.), на международной конференции "Алгебраическая теория чисел и диофантовы приближения" в Граце (Австрия, 1998 г.), на третьей международной конференции "Алгебра, геометрия и комбинаторика" в Порту (Португалия, 1999 г.), на международной конференции, посвященной памяти П.Эрде-ша, в Будапеште (Венгрия, 1999 г.), на международной конференции "XXI Арифметические дни" в Риме (Италия, 1999 г.), на международной конференции "Решетки, многогранники и разбиения" в Обервольфахе (Германия, 2000 г.), на международной конференции, посвященной Кли и Грюнбау-му, в Эйн - Геве (Израиль, 2000 г.), на международной конференции "Конференция по теории чисел, посвященная смене тысячелетий" в Эрбане (США, 2000 г.); на Ломоносовских чтениях в Московском государственном университете в 1999 г., а также на кафедральном семинаре кафедры Теории чисел механико - математического факультета МГУ под руководством проф. А.Б. Шидловского и чл. - корр. Ю.В. Нестеренко, на семинарах доц. Мощевитина и доц. Долбилина в МГУ, на семинаре проф. Конягина в МГУ, на семинаре проф. Рышкова в МГУ, на семинаре к.ф.м.н. Тарасова и чл. - корр. Разборова в Вычислительном Центре при Российской Академии Наук и, кроме того, на семинаре проф. Шинцеля в Варшаве (Польша, 1999 г.), проф. Тихого в Граце (Австрия, 1999 г.), проф. Циглера в Берлине (Германия, 1999 г.) и проф. Барани в Будапеште (Венгрия, 2000).

Опубликованность результатов. Результаты диссертации опубликованы в работах [56] - [70] списка использованных источников. Всего по теме диссертации опубликовано 15 работ.

Структура и объем диссертации. В диссертации имеется введение, общая характеристика работы, 4 главы, список использованных источников. Полный объем 118 е., из них 8 с. занимает список использованных источников (70 наименований).