Минимизация тени в слое булева куба

• Автор: Башов, Максим Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 73 с.

Оглавление
Введение

1. Сведение задачи минимизации тени к задаче минимизации веса идеала

1.1. Оператор сдвига и его свойства

1.2. Критерий уменьшения размера тени

1.3. Частичный порядок, порождаемый оператором сдвига

1.4. Задача минимизации веса идеала

1.5. Обобщение теоремы Краскала-Катопы

1.6. Минимизация двусторонней тени в крайних слоях

2. Несуществование минимизирующего

двустороннюю тень линейного порядка в центральных слоях

2.1. Структура частично упорядоченного множества М.(та, к)
2.2. Свойства минимизирующего линейного порядка
2.3. Несуществование минимизирующего линейного порядка
3. Минимальные по двусторонней тени
семейства
3.1. Вспомогательные утверждения
3.2. Минимальность круга Сх(та, к)
3.3. Система вложенных минимальных семейств
3.4. Минимальность семейства С{п, к)
3.5. Свойства круга С2(та, к)
Литература

Введение
Экстремальная комбинаторика, изучающая вопрос о максимально или минимально возможном числе объектов в классе, обладающем некоторыми свойствами, является важным разделом дискретной математики. Известными результатами в этой области являются, например, теорема Шпернера о максимальном количестве множеств, ни одно из которых не вложено в другое, или теорема Эрдёша-Ко Радо о максимальной мощности семейства попарно пересекающихся множеств. В диссертации решаются задачи минимизации тени в булевом кубе.
Пусть (М, — некоторое частично упорядоченное множество, х £ М. Ниж-
ней тенью элемента х называется множество непосредственно предшествующих ему элементов: Ах — {у £ М у < х}. Верхней тенью элемента х называется множество непосредственно следующих за ним элементов: Vx = {у £ М | у > х}. Двусторонняя тень Хх — это объединение множеств Ах и Vx. Теныо множества X С А/ называется объединение теней его элементов: ДА" — [J Дх,

XX = и Vx, XX = и Хя.
х€Х хёХ
Задача минимизации тени заключается в том, чтобы в некотором заданном семействе X подмножеств М найти множество, имеющее минимальную мощность тени. Обычно частично упорядоченное множество М является ранжированным, а в качестве семейства X рассматривается семейство подмножеств фиксированной мощности, вложенных в слой множества М.
Подобные задачи возникают, например, при перечислении комбинаторных объектов, таких как монотонные булевы функции [12] или независимые множества в графах [26], в теории надёжности сетей [31].
Будем обозначать через [п] множество п первых натуральных чисел {1,..., п}. Под п-мерным булевым кубом будем понимать семейство 2^1 всех подмножеств множества [п] с отношением частичного порядка С. Через (^) обозначим к-й слой n-мерного булева куба, то есть семейство всех /с-элемеитпых подмножеств [гг].
Нетрудно видеть, что так определённое частично упорядоченное множество изоморфно множеству Вп = {(ct'i, Q'2, • • •, ап) сц £ {0,1}} двоичных наборов

длины п с отношением покоординатного сравнения: (ад ^ (/Зх,..., /Зп)
тогда и только тогда, когда а* ^ Д для всех г. Действительно, набору (ах,..., ап) из Вп можно сопоставить множество А — {г а„_г+1 — 1} € 2^.
Пусть Т — семейство ^-элементных подмножеств [гг], то есть Т С (^)- Тогда нижняя тень АТ — это семейство всех множеств А из слоя (Д), для которых существует множество В £ Т, В Э А. Аналогично, верхняя тень УТ — это семейство всех множеств А ИЗ СЛОЯ (х|"х), ДЛЯ которых существует множество В £ Т, В С А. Наконец, двусторонняя тень ХТ есть семейство АТ и У Т.
Семейство Т С называется минимальным по нижней тени (верхней тени, двусторонней тени), если IA.Fl ^ |Д£?| (соответственно IV.FI ^
|^ |ХС/|) для любого такого семейства С? С (!”'), что Я — Т.
Множество А £ 2^ лексикографически предшествует множеству В £ 2Т, если тах((А В) и (В А)) £ В. Семейство, состоящее из т лексикографически наименьших множеств семейства Т, называется начальным лексикографическим отрезком Т длины т. Семейство, состоящее из т лексикографически наибольших множеств семейства Т, называется конечным лексикографическим отрезком Т длины га.
История вопроса
Одними из первых работ, где рассматривалась задача минимизации тени, являются статьи [52] и [49], в которых независимо были описаны подмножества слоя фиксированной мощности, минимизирующие одностороннюю тень.
Теорема (Дж. Краскал [52], Д. Катона [49]). Начальный лексикографический отрезок (^) длины т минимален по нижней тени, то есть имеет наименьший размер нижней тени среди всех подмножеств слоя мощности т. Конечный лексикографический отрезок (^) длины т минимален по верхней тени, то есть имеет, наименьший размер верхней тени среди всех подмножеств слоя мощности га.
Оригинальные доказательства теоремы достаточно громоздки. Простые доказательства можно найти, например, в [35, 46, 38, 13].
Краскал и Катона также дали точную формулу для подсчёта размера тени лексикографического отрезка. Пусть
т = С л) + (* - О+- -+С‘) ’ с‘-1 > - - -> с‘ ^ > °-

Рассмотрим семейство Т" = Т U {С} U {С U {г} {ç} | г < q ^ п}. Заметим, что Т" = Р U {Я>}| = | Т + п - q, и

КТ" = хт + s(C) + $>(
n—q n—q—
= XТ + $>( г=0 г=
Если п — q > 2, то отсюда следует, что КТ" < К(Т' и {Я}), что противоречит определению минимизирующего порядка ) ^ ■s(C), и вновь выполнено КТ" < К{Т' U {-D}).
Теперь пусть Л° = {2,3,..., /с, п}, и следовательно, В0 = {2,3,..., k—1, /с+1, п}, В = В1 = {1,2,..., к — 2, к + 1, А: + 2}. Заметим, что з(Я) = п — 4. По утверждению 28 лишь три множества из Х(А°) имеют вес, больший гг. — 4:
s({l, 2,..., к — 1, А: + 1}) = п — 2,
s({l, 2,..., к — 1, к + 2}) — п — 3,
s({l, 2,..., к — 2, к, к + 1}) = п — 3,
и все эти множества предшествуют В в частичном порядке С, а следовательно, и в порядке <тш- Таким образом, s (С) = п — 4.
Поскольку А' = {1,2,..., к — 2, к, к + 2} С Б, верно A' по утверждению 28 все множества из Х(Л°), отличные от А', G, Я, имеют вес, не равный п — 4. Следовательно, либо С — G, либо С = Я. Заметим, что либо А: > 2, либо п — к > 2, потому что в противном случае G, Я ^ (^). Не ограничивая общности, будем считать, что п — к > 2.
Предположим, Я К(Т U {Я, (?})[ - ЦТ U {Я, Я})| = ЦТ U {G, {1,2,..., к — 2, к, к + 3}})| - 1,
и начальный отрезок <т,п длины огс1(Я) + 2 не является минимальным по двусторонней тени семейством.