Изопериметрические задачи на n-мерном единичном кубе

• Автор: Безруков, Сергей Леонидович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 115 c. : ил

Глава I. Построение решений основной дискретной

изопериметрической задачи

§ I. Определение рассматриваемых классов решений

1. Постановка задачи

2. Теорема о сводимости

§ 2. Построение всех оптимальных множеств особой

мощности

1. Описание используемого подхода

2. Вычисление радиусов Ь -шаров и некоторые вспомогательные утверхэдения

3. Множества, перестановочно-эквивалентные стандартному размещению

4.- Описание всех оптимальных множеств из

класса
5. Описание всех оптимальных множеств из класса

6. Актуальность описания всех оптимальных множеств особой мощности
§ 3. Построение решений, имеющих неособую мощность
1. Достаточное условие несуществования оптимальных критических множеств неособой мощности
2. Построение оптимальных критических множеств из неоптимальных
Глава 2. Изопериметрические задачи на множествах специальной структуры
§ I. Теорема о четных слоях куба £>
1. Постановка задачи
2. Доказательство основного результата

3. Обобщения основного результата
§ 2. йзопериметрическая задача для К -того слоя
куба Е)1^
1. Постановка задачи
2. Каноническое множество
3. Некоторые определения и вспомогательные утверждения
4. Леммы о конечных отрезках
5. Доказательство оптимальности канонического множества при К- 2. и К
6. Мощность окрестности канонического множества
7. Исследование множества Нб'Ц к, га.) на ассим-птотическую оптимальность при К=о(у[н)и К-т-ео
8. Сравнение мощностей множеств т) и
П (уь, К, га.) при к= с-п , 0. к < С < 0.
Глава 3. Изопериметрические задачи, возникающие при
различных определениях граничных вершин
1. Обзор постановок задач
2. Обобщение изопериметрической задачи, рассматриваемой в главе I
3. Центральная теорема
4. Случай, когда окрестность состоит из линейнонезависимых векторов куба
5. Дальнейшее обобщение центральной теоремы
Литература

В диссертации исследуется задача, являющаяся .дискретным аналогом известной классической изопериметрической задачи. На её основе производится построение решений некоторых других экстремальных комбинаторных проблем.
Как известно, классическая изопериметрическая задача заключается в отыскании среди всех простых замкнутых кривых с фиксированным периметром р такой, которая отделяет максимальную площадь ^ . В двойственной постановке указанная задача состоит в нахождении среди всех фигур площади 5 такой, которая имеет наименьший периметр р . Эти задачи были известны давно, и полное их решение впервые было найдено в XIX столетии на основе аппарата вариационного исчисления |~8_] . Оказалось, что окружность и крут являются единственными решениями соответствующих задач.
В настоящее время под изопериметрическими подразумевают широкий класс задач, связанных с исследованием соотношений между мощностью множеств различной природы и мощностью границ этих множеств. В диссертации исследуются дискретные изопери-метрические задачи.
Рассмотрим ^ -мерный единичный куб:
Ьк = [ (**, > ХИ.) : ХС £ = и,}.
Определим расстояние Хемминга между вершинами куба:
■ Дк-А-1, -О, Г/1,,
Скажем, что вершина /или точка/ является граничной для множества Аей , если , где
шар радиуса Ь в метрике Хемминга с центром в точке £ £ ЁэЁ . Совокупность всех граничных точек множества А будем обозначать через Г (А).
Дискретная изопериметрическая задача состоит в том, чтобы

Обозначим ^ ("А)" ]Р(Р (■ ■■ ( РСА)...)Л Пусть Р^СА)^р ,

PZ(A)* Ф £ (А)Фф , Рш(А)*0 . Нетрудно заметить,
что число ~t определяется по множеству А однозначно. Назовем его глубиной множества А и обозначим через d(A). Заметим, что РШ](А) является некритическим множеством.
На первом шаге алгоритма рассматривается множество S(Pf/)). если , то переходим ко второму шагу. Пусть $(Р(АЬ
. Построим шары & Z , ^ J . Нетрудно заметить, что <34 ç А-После этого переходим ко второму шагу.
Пусть уже проведено с шагов построения и с < с щ. Рассмотрим на (д + l) -ом шаге множество S(Q+i(A))> Если £(7?+/А))-- ф , то переходам к £'+£) -му шагу. Пусть S(P(-+iCA)) Ф Р и $(I°C+1 (А)]* №ГЛ, -у, 1 » Построим шары 3‘+4-- Q/2c/d),
*•• * Нетрудно заметить, что .уs А .
После этого переходим ко (£+2)-му шагу
Алгоритм заканчивает работу на шаге с номером d(A)+l
«toi) te- wc- Л Лежа 1.13. Имеет место равенство J U Ъ; ~ ■
с=4 J = i Доказательство
с((А) с н< л
Из описания алгоритма вытекает, что Jd± Ру !=■ А Покажем обратное включение. Пусть є А . Рассмотрим совокупность сфер радиусов і, г, cfYA) с центром в точке <=4 }
т.е. множества Т(' - £Jb е ёА : с' і » с’- І,с//А).
Утверждается, что хотя бы для одного из сегмента сч «fou] имеет место равенство . В качестве с'о
можно взять, например, число J , такое что Т- О Р- (A)î Р ,
но дал ццл)=0 . Осталось заметить, что <=£" принад0 а
лежит некоторому шару, построенному на шаге алгоритма с номером с'о . Лемма доказана.