Минимизация тени в слое булева куба тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Башов, Максим Александрович

• Башов, Максим Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Башов, Максим Александрович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

2.1. Структура частично упорядоченного множества Л4(п,к)

2.2. Свойства минимизирующего линейного порядка

2.3. Несуществование минимизирующего линейного порядка

3. Минимальные по двусторонней тени

семейства

3.1. Вспомогательные утверждения

3.2. Минимальность круга С\{п, к)

3.3. Система вложенных минимальных семейств

3.4. Минимальность семейства С^го, к)

3.5. Свойства круга Сч^-, к)

Литература

Введение диссертации (часть автореферата) на тему «Минимизация тени в слое булева куба»

Введение

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

Пусть (М, — некоторое частично упорядоченное множество, х € М. Нижней тенью элемента х называется множество непосредственно предшествующих ему элементов: Ах — {у £ М \ у < х}. Верхней тенью элемента х называется множество непосредственно следующих за ним элементов: Х7х = {у € М | у > х]. Двусторонняя тень Хх — это объединение множеств Ах и \7х. Теныо множества X С Л/ называется объединение теней его элементов: ДА" = Да;,

х€Х

УХ = и Уж, XX = и Хх.

хех хех

Задача минимизации тени заключается в том, чтобы в некотором заданном семействе X подмножеств М найти множество, имеющее минимальную мощность тени. Обычно частично упорядоченное множество М является ранжированным, а в качестве семейства X рассматривается семейство подмножеств фиксированной мощности, вложенных в слой множества М.

Подобные задачи возникают, например, при перечислении комбинаторных объектов, таких как монотонные булевы функции [12] или независимые множества в графах [26], в теории надёжности сетей [31].

Будем обозначать через [тт.] множество п первых натуральных чисел {1,..., п}. Под п-мерным булевым кубом будем понимать семейство 2^ всех подмножеств множества [п] с отношением частичного порядка С. Через обозначим /с-й слой п-мерного булева куба, то есть семейство всех /с-элементиых подмножеств [п].

Нетрудно видеть, что так определённое частично упорядоченное множество изоморфно множеству Вп = {(«1, «2,..., ап) \ а.{ € {0,1}} двоичных наборов

длины п с отношением покоординатного сравнения: (а^,..., ап) ^ /Зп)

тогда и только тогда, когда щ ^ для всех г. Действительно, набору (скх,..., ап) из Вп можно сопоставить множество А = {г\ = 1} е

Пусть Т — семейство /^-элементных подмножеств [п], то есть Т С Тогда нижняя тень АТ — это семейство всех множеств А из слоя для которых

существует множество В е Т7, В Э А. Аналогично, верхняя тень УТ7 — это семейство всех множеств А из слоя для которых существует множество

В £ Т, В С А. Наконец, двусторонняя тень Х77 есть семейство Д^и УТ7.

Семейство Т7 С называется минимальным по нижней тени (верхней

тени, двусторонней тени), если (ДТ7! ^ |Д£?| (соответственно ^

^ |Х£|) для любого такого семейства О С что \<3\ —

Множество А £ 2^ лексикографически предшествует множеству В € 2^, если тах((Л \ В) и (В \ А)) £ В. Семейство, состоящее из т лексикографически наименьших множеств семейства Т7, называется начальным лексикографическим отрезком Т длины т. Семейство, состоящее из т лексикографически наибольших множеств семейства Т, называется конечным лексикографическим отрезком Т длины т.

История вопроса

Одними из первых работ, где рассматривалась задача минимизации тени, являются статьи [52] и [49], в которых независимо были описаны подмножества слоя фиксированной мощности, минимизирующие одностороннюю тень.

Теорема (Дж. Краскал [52], Д. Катона [49]). Начальный лексикографический отрезок длины т минимален по ниэюней тени, то есть имеет наименьший размер ниэюней тени среди всех подмножеств слоя мощности т. Конечный лексикографический отрезок длины т м.инимален по верхней тенге, то есть имеет, наименьший размер верхней тени среди всех подмиоэюеетв слоя мощности т.

Оригинальные доказательства теоремы достаточно громоздки. Простые доказательства можно найти, например, в [35, 46, 38, 13].

Краскал и Катона также дали точную формулу для подсчёта размера тени лексикографического отрезка. Пусть

т = Й) + + ■ ' ' + (?) • <*>*-!>•• * > О-

Тогда мощность нижней тени начального лексикографического отрезка длины т равна так называемой псевдостепени числа гп

»^ЛИ^Ь-Ч-О-

Для использования нижних оценок мощности тени удобна следующая форма теоремы Краскала-Катоны (см., например, [47]):

Теорема (теорема Краскала-Катоны в форме Ловаса). ЕслиТ С и = (£) для некоторого ж £1, то |А-7-"| ^ (/ДО-

Булев куб (2^, С) обладает автоморфизмами, связанными с перестановками. Пусть 7г £ Бп — перестановка, тогда, очевидно, А С В в том и только в том случае, когда тг(А) = {тг(^) | й € Л} С 7г(Б). Также выполнено |Л| = \тт{А)\, и (А^7! = |А{7г(Л) | А е для всех Т С 2^. Таким образом, семейства, изоморфные лексикографическим отрезкам в смысле перестановки элементов [п], также минимизируют тень.

М. Мёрс [57] и независимо 3. Фюреди и Дж. Р. Григгс [43] установили необходимое условие существования минимальных семейств, не изоморфных лексикографическим отрезкам.

Теорема (М. Мёрс [57], 3. Фюреди и Дж. Р. Григгс [43]). Начальный лексикографический отрезок длины т является единственным с точностью до изоморфизма минимальным по нижней тени семейством мощности т в случае, когда (т 4- > гг№~1!к\

Известны также следующие результаты, описывающие структуру «почти минимальных» по односторонней тени семейств.

Теорема (П. Киваш [50]). Пусть г > к ^ I и 0 ^ 5 < 5(е, к). Пусть Т С |= (/ДзЗ и [Т7! = (1 — Тогда найдётся такое множество в, 151 = \х\,

что число множеств А £ АТ, для которых выполнено А ^ Б, не превосходит

Теорема (Р. О'Доннелл, К. Виммер [58]). Пусть £ > 0, 5 = <5(е) > 0, и г ^ Пусть Т С №), и ^ 1 — £. Тогда либо выполнено

Ы

Ш "О - '

5

либо найдётся г £ [тт.], для которого

\jAeF\ie А}\ А}\

Известно несколько обобщений теоремы Краскала-Катоны. Булев куб можно рассматривать как декартово произведение цепей длины 2 или как произведение одполучевых звёзд. Дж. Клементе и Б. Линдстрём [32] доказали, что лексикографические отрезки слоя имеют минимальную одностороннюю тень в декартовых произведениях цепей произвольной длины. Б. Линдстрём [56] обобщил теорему Краскала-Катопы па случаи декартовых степеней двухлучевой звезды, то есть частично упорядоченного множества {0,1,2}, в котором 0 > 1, 0 > 2, а 1 и 2 несравнимы. С. Л. Безруков [8] установил справедливость обобщения для декартова произведения звёзд с произвольным числом лучей. П. Франкл, Ж. Калаи и 3. Фюреди [40] получили обобщение для частично упорядоченного множества, двойственного произведениям звёзд, для некоторых значений параметров. В [30] установлена справедливость этого результата для произвольных значений параметров. С. Л. Безруков и Р. Элсассер [29] обобщили теорему Краскала-Катопы на случай произведения регулярных пауков — частично упорядоченных множеств, являющихся обобщением звёзд.

Аналоги теоремы Краскала-Катоны, то есть описания решений задачи минимизации тени в виде отрезков некоторого линейного порядка, доказаны также для других частично упорядоченных множеств. Р. Алсведе, А. Айдиняп и Л Ха-чатрян [13] рассмотрели задачу для булева куба с ограничениями и доказали, что начальные лексикографические отрезки семейства {А £ | А П [с/] ^ г} имеют минимальный размер тени среди всех подсемейств этого семейства той же мощности. С. Л. Безруков [7], Дж. Кёрнер и В. Вей [51], X. Тирсма [59] доказали аналог теоремы Краскала-Катоны в двуслойном частично упорядоченном множестве, один из слоев которого состоит из двоичных наборов фиксированной длины с чётным числом единиц, а другой — из двоичных наборов с нечётным числом единиц, и сравнимыми являются наборы, расстояние Хэмминга между которыми равно 1. У. Лек [53] доказал аналогичную теорему для порядка подматриц — декартова произведения булевых кубов с удалённой наибольшей точкой.

Р. Алсведе и Н. Каи [18], Д. Дайкин и Т. Дан [34] доказали существование минимизирующего тень порядка для так называемого порядка подслов 50(2) — множества слов в алфавите из двух символов, частичный порядок на котором введён следующим образом: слово а предшествует слову если а можно получить из /3 удалением символов. У. Лек [54] показал, что для порядка БО(п) в

алфавите из п > 2 символов не существует аналога теоремы Краскала-Катопы, то есть решения задачи минимизации тени в этом частично упорядоченном множестве нельзя описать в терминах линейного порядка.

В [25] рассматривалась задача минимизации тени в множестве слов в алфавите из двух символов с отношением слово-подслово.

Тесно связанной с задачей минимизации тени является задача о максимальной мощности пересекающихся семейств. Семейство JF С называется ¿-пересекающимся, если для любых А, В G J- выполнено \А П В\ ^ ¿. П. Эрдёш, Ч. Ко и Р. Радо [37] получили достижимую верхнюю оценку мощности 1-пересекающегося семейства, вложенного в

Теорема (П. Эрдёш, Ч. Ко, Р. Радо [37]). Если п ^ 2к, и Т С (М) - 1-пересекающееся семейство, то \Т\ ^ (¿i}) — £ | 1 £ Л}|.

В той же статье авторы показали, что для произвольного t при достаточно больших п максимальным по мощности í-пересскающимся семейством, вложенным в является семейство {А £ | [t] С А].

Д. Дайкин [36] показал, что теорема Эрдёша-Ко-Радо является следствием теоремы Краскала Катоны. Р. Алсведе и Л. Хачатряи [24] получили описание всех максимальных ¿-пересекающихся семейств, вложенных в для произвольных значений параметров n, k, t.

Теорема (Р. Алсведе, JI. Хачатрян [24]). Пусть — мак-

симальное по мощности t-пересекающееся семейство, влооюенное в . Тогда

1) если существует целое г ^ 0; для которого

(k-t + 1)(2 + (¿ - 1 )/(r + 1)) < п < (k - t + 1)(2 + (¿ - 1 )/г), то найдётся такое мноо/сество 5 С [n]; |¿)| = ¿ + 2г, что

\\AnS\>t + r

2) если существует целое т ^ 0, для которого

(/с - ¿ + 1)(2 + (¿ - 1 )/(r + 1)) - п, то либо найдётся такое множество S С [n], \S\ — t + 2г, что

|Ае ^ I \Ans\ ^¿ + г|,

либо найдётся такое миооюество 5 С [п], |5| = Ь + 2г + 2, что

I 1ЛП51 +

В [23] для произвольных значений параметров описаны максимальные по мощности ¿-пересекающиеся семейства Т С для которых выполнено Р) А < ¿.

АеТ

Д. Катона [48] получил достижимую верхнюю оценку мощности произвольного ¿-пересекающегося семейства. В той же статье рассматривалась задача минимизации тени пересекающихся семейств и получена следующая верхняя оценка.

Теорема (Д. Катона [48]). Пусть Т С ([™]) — ^пересекающееся семейство. Тогда

к

к - £ +

Р. Алсведе, А. Айдинян и Л. Хачатряп [14] описали пересекающиеся семейства больших мощностей, имеющие минимальную одностороннюю тень. В [39], [41], [42] рассмотрены обобщения пересекающихся семейств и получены оценки их мощности и мощности их тени.

Ещё одним классом задач, тесно связанным с задачей минимизации тени, являются изопериметрические задачи на. графах. Пусть О = (V, Е) — граф, А С V — некоторое множество его вершин. Границей множества А называется множество вершин Г(Л) = {у е А \ Зш £ Л, (г?,гу) £ #((?)}.

Вершинный вариант изопериметрической задачи заключается в нахождении множества вершин заданной мощности с минимальным размером границы. Решения вершиино-изопериметрической задачи в булевом кубе, то есть в графе (2^, {(А, В) \ACBe 2^, \А\ = \В\ - 1}), были найдены Л. Харпером в [44].

Теорема (Л. Харпер [44]). Пусть т = (¡¡) + (") + ... + (£) + т0; 0 ^ т0 < . Пусть Т является квазисферой мощности т, то есть объединением семейств

для 0 ^ ъ ^ к и конечного лексикографического отрезка длины

Тогда для любого <3 С \0\ = т, выполнено |Г(£?)| ^ ^(Т7)!-

С. Л. Безруков в статьях [9] и [28] описал все попарно не изоморфные решения всршинно-изопериметрической задачи в булевом кубе для некоторых значений параметров. Р. Алсведе и Н. Каи [19] описали решения изопериметрической задачи в графе, являющемся диаграммой Хассе порядка подслов 50(2).

Рёберные варианты изонериметрической задачи заключаются в нахождении множества вершин А заданной мощности с максимально возможным числом внутренних рёбер 1(А) = {(01,02) £ E(G) | а\ £ А, <22 G А}, либо с минимальным числом внешних рёбер О(А) = {(а, fr) G E(G) | а G А, b ф А}. Для регулярного графа эти две задачи эквивалентны, поскольку в ^-регулярном графе для любого множества А верно 1(А) + О(А) — к • \А\. Рёберно-изопериметрическая задача в булевом кубе рассматривалась Л. Харпером.

Теорема (Л. Харпер [44]). Пусть Т — начальный лексикографический отрезок 2^ длины т. Тогда для любого Q С \Q\ = т выполнено \I(ö)\ ^ \1(Т)\.

Лексикографические отрезки также являются решениями рёберно-изопери-метрической задачи для произведения полных графов [55] и для произведения полных двудольных графов с равпомощными долями [16]. Р. Алсведе и Н. Каи [17] получили простое достаточное условие оптимальности лексикографических отрезков в декартовых степенях произвольного графа, так называемый локально-глобальный принцип.

Примером изопериметрической задачи, решения которой в общем случае не удаётся описать в виде отрезков некоторого порядка, является задача Клейт-мана-Веста. В этой задаче рассматривается граф с множеством вершин и множеством рёбер {(Л, В) | \А П В\ = к — 1}. В статье [22] рассмотрен случай к = 2 и показано, что решения принадлежат к одному из двух классов множеств. Более простое доказательство того же результата получено в [27]. При к > 2 решение задачи для произвольной мощности множества неизвестно. Л. Харпер [45] п Р. Алсведе и Н. Каи [20] показали, что задача Клейтмана-Веста сводится к задаче минимизации веса идеала частично упорядоченного множества. В [45] с помощью перехода от дискретной задачи к непрерывной получены решения некоторых мощностей.

В статьях [11] и [33] рассмотрен вершинный вариант задачи Клейтмана-Веста и получены оценки мощности границы множества.

Задача минимизации веса идеала, в терминах которой часто удаётся переформулировать рёберно-изопериметрические задачи, рассматривалась также в [21] и [10]. Р. Алсведе и Д. Катопа описали решения этой задачи в булевом кубе для монотонных и унимодальных симметрических функций.

Теорема (Р. Алсведе, Д. Катона [21]). Пусть J7 С 2^ — идеал, то есть если А £ Т и В С А, то В G Т. Пусть Кг = |{А G 7 | |Л| - г}|, и J{F) = Vк^.

г

Тогда min /(J7) достигается на следующих семействах:

1) если \№о ^ \¥\ ^ ... ^ \¥п, то минимум достигается на квазисфере мощности т;

2) если ]¥о ^ \¥г ^ ... ^ ]¥П) то минимум достигается на начальном лексикографическом отрезке семейства мощности т;

3) если Жо ^ У/\ ^ ... ^ У/ч ^ ^ ... ^ ]¥п, то минимум достигается на объединении некоторой квазисферы и некоторого начального лексикографического отрезка;

4) если \¥о ^ \У1 ^ ... ^ ^ ^ ... ^ У/п, то минимум достигается на пересечении некоторой квазисферы и некоторого начального лексикографического отрезка;

С. Л. Безруков и В. П. Воронин [10] обобщили этот результат на декартовы произведения цепей произвольной длины.

Краткое содержание диссертации

Диссертация состоит из трёх глав.

В первой главе описывается сведение задачи минимизации тени подсемейства слоя булева куба к задаче минимизации веса идеала частично упорядоченного множества. В разделе 1.1 определяется оператор сдвига и доказываются его свойства. В частности, показывается, что оператор сдвига не меняет мощность семейства и не увеличивает мощности его теней. В разделе 1.2 устанавливается необходимое и достаточное условие того, что размер тени семейства строго уменьшается при применении оператора сдвига. В разделе 1.3 вводится порождённый на слое булева куба оператором сдвига частичный порядок С и устанавливаются его свойства. Показывается, что при решении задачи минимизации можно, не ограничивая общности, рассматривать только идеалы данного частичного порядка. Доказывается, что если двусторонние тени двух множеств имеют непустое пересечение, то эти множества сравнимы в частичном порядке. Устанавливается, что лексикографический порядок является линейным расширением введённого частичного порядка.

В разделе 1.4 выводятся формулы для вычисления размера тени идеала.

Теорема (разд. 1.4, утверждения 19, 20, 21). Пусть Т С (М) — идеал. Тогда размеры теней Т вычисляются по формулам ¡ДТ7! = ^ ^С^)* ^Т7! = ^ зи(А),

АеТ А^Т

\ХТ\ = X] ¿К^); гдеэ^А) = тт([га]\А)-1, ви(А) = п-тахД ¿(А) =

В разделе 1.5 описываются решения задачи минимизации веса идеала для некоторого класса весовых функций, включающих функции, соответствующие нижней и верхней тени.

Теорема (разд. 1.5, теорема 1). Пусть /: [0, к] —> М — неубывающая функция. Тогда начальный лексикографический отрезок минимизирует весовую функцию /(5/).

В разделе 1.6 описываются минимальные по двусторонней тени семейства в крайних слоях булева куба.

Теорема (разд. 1.6, теорема 2). Если к ^ 2, то конечный лексикографический отрезок является минимальным по двусторонней тени семейством. Если к > п — 2, то начальный лексикографический отрезок является минимальным по двусторонней тени семейством.

Результаты первой главы опубликованы в [1, 3, 6].

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

Теорема (разд. 2.3, теорема 3). При п ^ 7 никакой линейный порядок на не минимизирует двустороннюю тень. Для любого линейного порядка, заданного на существует такое число т ^ тах{4п — 14,15}, что начальный отрезок этого порядка длины т не является минимальным по двусторонней тени семейством.

Теорема (разд. 2.3, теорема 4). При 4 ^ к < | никакой линейный порядок на не минимизирует двустороичьюю тень. Для любого линейного порядка, заданного па ( ¿J), существует такое число т ^ 1 + k(ri — к) + (к — 1)(2п — 2к — 3), что начальный отрезок этого порядка длины т не является минимальным по двусторонней тени семейством.

Теорема (разд. 2.3, теорема 5). При 4 ^ k = | никакой линейный порядок на не минимизирует двустороннюю тень. Для любого линейного порядка, заданного на существует такое число т ^ 1 + к2 + (2к — 3)(к — 2) + } что начальный отрезок этого порядка длины т не является минимальным по двусторонней тени семейством.

Результаты второй главы опубликованы в [1, 4, 5].

Третья глава посвящена описанию семейств, минимизирующих двустороннюю тень, в центральных слоях. В разделе 3.1 доказываются вспомогательные утверждения. В разделе 3.2 доказывается, что пересечение слоя и шара Хэмминга с радиусом 2 и центром А Е является минимальным по дву-

сторонней тени семейством. Обозначим это семейство через Сх(Л), и положим

Ci(n, k) = Ci({l, 2,..., к}) С (И).

Теорема (разд. 3.2, теорема 6). Ci(n, к) — единственный минимальный по двусторонней тени идеал мощности 1 + к{п — к).

Теорема (разд. 3.2, теорема 7). Если Т С — минимальное по двусторонней тени семейство мощности 1 + к(п — к), то Т = Ci(A) для некоторого А Е .

В разделе 3.3 описываются минимальные по двусторонней тени семейства малой мощности, образующие систему вложенных семейств.

Теорема (разд. 3.3, теорема 8). Если k ^ Ц, то начальные лексикографические отрезки Ci(n, к) являются минимальными по двусторонней тени.

Теорема (разд. 3.3, теорема 9). Если 2 ^ к ^ п — 2, то семейство

С[(п, к) = Ci(n, к) U {{1,2,..., к - 2, к + 1, к + 2}} является минимальным по двусторонней тени.

В разделе 3.4 для некоторых значений параметров описывается минимальное по двусторонней тени семейство мощности 2к(п — к) — п + 2. Обозначим через Сх(гг, к) идеал {А Е ([£]) | А О {2, 3,..., к - 1, к + 1, п}}.

Теорема (разд. 3.4, теорема 10). С\(п,п/2) является минимальным по двусторонней тени семейством.

Теорема (разд. 3.4, теорема 11). Если п ^ 13, то С\{п, 3) является минимальным по двусторонней тени семейством.

1 л ^

Теорема (разд. 3.4, теорема 12). Если п ^ ^к , то С\{п, к) является минимальным по двусторонней тени семейством.

В разделе 3.5 доказываются некоторые свойства пересечения слоя с шаром Хэмминга с радиусом 4 и центром в слое. Показывается, что при к = 3 такое семейство является минимальным по двусторонней тени.

Результаты третьей главы опубликованы в [1, 2, 3, 6].

Основные результаты диссертации

1. Показано, что задачи минимизации односторонней и двусторонней тени в слое булева куба сводятся к задачам минимизации веса идеала (утверждения 19, 20, 21).

2. Описаны решения задачи минимизации двусторонней тени произвольной мощности в к-м слое п-мерного булева куба при к ^ 2 и при к ^ п — 2 (теорема 2).

3. Получены верхние оценки мощности максимальной системы вложенных решений задачи минимизации двусторонней тени, и показано, что за исключением случая п — 6. к = 3. при 3^/с^п — Зв к-м слое п-мерного булева куба не существует минимизирующего двустороннюю тень линейного порядка (теоремы 3, 4, 5).

4. В к-и слое п-мерного булева куба для произвольных п, к описаны решения задачи минимизации двусторонней тени мощности, не превосходящей 2-\-к(п — /с), образующие систему вложенных множеств (теоремы 6, 8, 9). Показано, что решение мощности 1 + к(п — к) единственно с точностью до изоморфизма (теорема 7).

5. При к = п/2 и при малых значениях к описано минимальное по двусторонней тени семейство мощности 2к(п — к) — п -+- 2 (теоремы 10, 11, 12).

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

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

Стандартным инструментом для решения экстремальных задач в булевом кубе являются операторы сдвига, позволяющие уменьшить класс рассматриваемых семейств-кандидатов на экстремальность. Определим оператор сдвига, впервые рассмотренный Эрдёшем, Ко и Радо [37]. Пусть А е Т С 1 ^ г ^ п, 1 ^ 7 ^ тг. Сдвигом множества А относительно семейства Т будем называть множество

Результат применения оператора к семейству Т будем считать семейство

Свойства оператора сдвига хорошо известны (см., например, [39, 13]). Приведём с доказательствами те из них, которые используются при решении задачи минимизации тени.

Утверждение 1. Пусть Т С 1 ^ г ^ п, 1 ^ ^ ^ п. Тогда =

Доказательство. Достаточно показать, что если 5^(7-", А) — ¿^(Т7, Л), А £ Т7, В е 3=, то А = В. Пусть Бг3{Т,А) = е Т. Тогда - А, и

¿^(Т7, Б) = В, поэтому А — В. Пусть теперь ¿^-(Т7, А) = Згз(Т,В) ^ Т. Тогда Л = ^(Т7, А) и {¿} \ {г} - 5у (7-, В) и 0'} \ {г} = В. □

Утверждение 2. Пусть Т С 1 ^ г < п, 1 < ] ^ п. Тогда Д^Д-Г) С ^(Д-Г).

А

^•(7-, А) А

если 3 А или Д если Аи{г}\ {.?'} 6 Т,

Л и {г} \ иначе.

ЗуСГНй^А) | Ае Л-

Доказательство. Пусть Л Е АЗ^(Т). Докажем, что А Е По опреде-

лению нижней тени существует такое р Е [п], что А и {р} = В Е Пусть

В еТ, тогда А Е АТ. Если 3 А или г Е А, то А Е 3^(А7Г). Пусть 3 Е А иг £ А. Тогда если р — г, то В \ {3} — А и {г} \ Е Д77, и поэтому А Е 5у(Д7Г). Если же р г, то ) 6 В и г ^ Б, поэтому В Е Т влечёт Зц{ТВ) — В} следовательно,

в и {¿} \ {¿} Е Т7, Л и \ Ш Е АТ и Л Е З^(АТ).

Пусть теперь В ф Т. Тогда по определению оператора сдвига 3 ^ В, г Е В и Б и У} \ {г} Е Т7, следовательно, р ^ 3, А и {.?'} \ {г} Е Д^7, и поэтому

Ле^ДТ7)- □

Утверждение 3. Пусть Т С 1 < г ^ п, 1 ^ 3 ^ п. Тогда У^ОТ С (УТ").

Доказательство. Пусть Л Е УЗу^). Докажем, что Л 6 У.77). По определению верхней тени существует такое ре [п], что Л \ {р} = В Е ^-(Т7). Пусть В ЕТ, тогда Л Е У-?7. Если 3 А или г Е Л, то Л Е ,%(У^7). Пусть ^ Е Лиг ^ Л. Тогда если р = то В и {г} = Л и {г} \ {7} Е У.77, и поэтому Л Е ¿^-(УТ7). Если же Р 3> т0 7 £ В и г ^ В, поэтому В Е Т влечёт ^ В) — В, следовательно, В и {г} \ О"} Е 7-, Л и {г} \ {¿} Е У77 и Л Е ^(УТ7)-

Пусть теперь В £ Т. Тогда по определению оператора сдвига у ф В, г Е В и В и \ {г} Е Т', следовательно, р ф г, Л и } \ {г} Е УТ7, и поэтому Л Е ^(УТ7). □

Из утверждений 1, 2, 3 вытекает Утверждение 4. Пусть Т С ([£]); 1 ^ г ^ п; 1 ^ 3 ^ п. Тогда \АЗ^(Т)\ ^ |

Семейство Т С называется песдвигаемым, если ^-(Т7) = Т7 для любых г и 1 < г < ; ^ п.

Утверждение 5. Пусть Т С Тогда существует такая конечная после-

довательность операторов сдвига ..., что 5,г1_7-1(5г2_72(... Зад (7)...)) — несдвигаемое семейство.

Доказательство. Заметим, что если г < и = £ Т7, то

ЕЕ?>ЕЕ^°-

Следовательно, длина последовательности операторов сдвига ц < Зи каждый из которых при последовательном применении к семейству Т меняет текущее семейство, ограничена числом ^ ^ р. □

Из доказанных утверждений следует, что для любого т, 0 ^ т ^ найдутся нссдвигаемые семейства мощности ш, вложенные в минимальные по нижней, верхней и двусторонней тени. Таким образом, при решении задачи минимизации можно, не ограничивая общности, рассматривать только несдвигаемые семейства.

Утверждение 6. Пусть Т С С/ С 1 ^ г ^ п, 1 ^ з ^ п. Тогда

Доказательство. Пусть А £ Докажем, что А £ Пусть А £ Т.

Если г £ А или з ^ А, то = А) = А, поэтому А £ 3^(С/). Если

г ^ А и з £ А, то А £ Зц{Т) влечёт А и {г} \ {3} £ Т С (?, поэтому (О, А) = А иА£

Пусть теперь А ^ Т. Тогда Ли{^'}\{г} £ Т С и следовательно, А £ 3^(0).

□

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

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

Утверждение 7. < \АТ\ тогда и только тогда, когда для некоторо-

го А £ (^l^) семейство Т codepotcum элементы {г,р} U А и {j, q} U А, причём {j}UA£ ASijiT).

Доказательство. Разобьём семейство Т на две непересекающиеся части: семейство неподвижных при сдвиге 8ц множеств и семейство множеств перемещаемых оператором сдвига Зц.

Т = Т0 U 7"ь где То ={А € Т {А£Т {А£Т {А£Т Тх ={А £ Т

i£ A, j £ A}U ifAJ^A} U, ieA,j$A} и

i£Aj£A,Au{i}\{j}£T}, i <£ A,j £ A, A(J {i}\ {j} £ F}.

Ясно, что Sij(T) = ToUSij(J-'i), следовательно, \AT\ = lAJ^ol + IA-^il-l^^onAJ-il, и lA^fJ-)! = \AT0\ + |ASy(.Fi)| - |Д7Ь П ASij{Ti)\. Заметим, что

ASijfr) = {В \ {j} \B£Tl}U{CU {г} \ {j} \j £ С £ Д^},

поэтому |Д7*1| = (Дй'у (7*1)1. Таким образом, |Д5^-(7*)| < |Д7*| тогда и только тогда, когда |Д 5^(7*1) П Д70| > |Д7*1 П Д70|.

Поскольку /£>у(7"о) = То, из С е Д7*о, 3 £ С, г ^ С следует Си{г}\{;'} е Д7*0. Поэтому неравенство выполнено в том и только в том случае, когда существует такое С <Е Д7*ь что 3 е С, С £ Д70, и С и {г} \ {;'} е Д7*0. Полагая А = С \ {.?'}, получаем, что г^ <£ А, А и {¿,р} € 7*0, А и {.7, <?} € 7*1, и А и ^ Д7*0. Остаётся заметить, что поскольку никакое множество В, содержащее не входит в Д^'у(7*1), последнее условие на Л эквивалентно условию Ли{:/} ^ Дб^Т*). □

Список литературы диссертационного исследования кандидат наук Башов, Максим Александрович, 2013 год

Литература

1. Башов М. А. Минимизация двусторонней тени в единичном кубе // Дискретная математика. 2011. 23. №4. С. 115-132.

2. Bashov М. Minimal families in terms of double-sided shadow in the Boolean cube layer // Electronic Notes in Discrete Mathematics. 2011. 38. P. 117-122.

3. Башов M. А. Минимальные по двусторонней тени подмножества булева куба, отличные от круга // Дискретный анализ и исследование операций. 2012. 19. №5. С. 3-20.

4. Башов М. А. Несуществование аналога теоремы Краскала-Катоны для задачи минимизации двусторонней тени // Материалы XI международного семинара «Дискретная математика и её приложения», посвящённого 80-летию со дня рождения академика О. Б. Лупанова (Москва, 18-23 июня 2012г.). М.: Издательство механико-математического факультета МГУ, 2012. С. 227-230.

5. Bashov М. Nonexistence of a Kruskal-Katona type theorem for double-sided shadow // Acta Sapientiae Informática. 2013. 5(1). P. 53-62.

6. Башов M. А. Минимизация веса идеалов в слое булева куба // Вестник Московского университета. Серия 15: вычислительная математика и кибернетика. 2013. №3. С. 69-77.

7. Безруков С. JT. Об одной изопериметрической задаче // Методы дискретного анализа в оптимизации управляющих систем. 1983. 40. С. 3-18.

8. Безруков С. JI. Минимизация теней подмножеств полурешетки частичных отображений // Методы дискретного анализа в оптимизации управляющих систем. 1987. С. 3-18.

9. Безруков С. JI. О построении решений дискретной изопериметрической задачи в хэммипговом пространстве // Математический сборник. 1988. 135(1). С. 80-95.

10. Безруков С. JL, Воронин В. П. Экстремальные идеалы решётки мультимножеств для симметрических функционалов // Дискретная математика. 1990. 2(1). Р. 50-58.

11. Лист Б. Вершинный вариант задачи Клейтмана-Веста // Дискретный анализ и исследование операций. 1995. 2(3). С. 24-48.

12. Сапоженко А. А. Проблема Дедекинда и метод граничных функционалов. М., Физматлит, 2009.

13. Ahlswede R., Aydinian Н., Khachatrian L. Н. More about shifting techniques // European J. Combin. 2003. 24(5). P. 551-556.

14. Ahlswede R., Aydinian H., Khachatrian L. H. On shadows of intersecting families // Combinatories 2004. 24(4). P. 555-566.

15. Ahlswede R., Blinovsky V. Lectures on advances in combinatorics, Springer, 2008.

16. Ahlswede R., Cai N. General edge-isoperimetric inequalities, Part I: Information-theoretical methods // Europ. J. Combin. 1997. 18. P. 355-372.

17. Ahlswede R., Cai N. General edge-isoperimetric inequalities, Part II: A local-global principle for lexicographic solution // Europ. J. Combin. 1997. 18. P. 479489.

18. Ahlswede R., Cai N. Shadows and isoperimetry under the sequence-subsequence relation //Combinatorica. 1997. 17. P. 11-29.

19. Ahlswede R., Cai N. Isoperimetric theorems in the binary sequences of finite length // Appl. Math. Lett. 1998. 11. P. 121-126.

20. Ahlswede R., Cai N. A counterexample to Kleitman's conjecture concerning an edge-isoperimetric problem // Combinatorics Probability and Computing. 1999. 8(4). P. 301-305.

21. Ahlswede R., Katona G. О. H. Contributions to the geometry of Hamming spaces // Discrete Mathematics. 1977. 17(1). P. 1-22.

22. Ahlswede R., Katona G. О. H. Graphs with maximal number of adjacent pairs of edges // Acta Math. Acad. Sci. Hungar. 1978. 32. P. 97-120.

23. Ahlswede R., Khachatrian L. H. The complete nontrivial-intersection theorem for systems of finite sets // Journal of Combinatorial Theory, Series A. 1996. 76(1). P. 121-138.

24. Ahlswede R., Khachatrian L. H. The complete intersection theorem for systems of finite sets // European Journal of Combinatorics. 1997. 18(2). P. 125-136.

25. Ahlswede R., Lebedev V. S. Shadows under the word-subword relation // Problems of Information Transmission. 2012. 48(1). P. 31-46.

26. Alon N. Independent sets in regular graphs and sum-free subsets of finite groups // Israel Journal of Mathematics. 1991. 73(2). P. 247-256.

27. Bey C. Remarks on an edge isoperimetric problem // General Theory of Information Transfer and Combinatorics. 2006. P. 971-978.

28. Bezrukov S. L. Isoperimetric problems in discrete spaces // Extremal Problems for Finite Sets, Bolyai Soc. Math. Stud. Budapest, 1994. P. 59-91.

29. Bezrukov S. L., Elsasser R. The spider poset is Macaulay // Journal of Combinatorial Theory. 2000. 90(1). P. 1-26.

30. Bezrukov S. L., Leek U. Macaulay posets // Electron. J. Combin. 2004. Dynamic Survey DS12.

31. Brecht T. B., Colbourn C. J. Lower bounds on two-terminal network reliability // Discrete Applied Mathematics. 1988. 21(3). P. 185-198.

32. Clements G. F., Lindstrom B. A generalization of a combinatorial theorem of Macaulay // Journal of Combinatorial Theory. 1969. 7. P. 230-238.

33. Christofides D., Ellis D., Keevash P. An approximate isoperimetric inequality for r-sets // arXiv: 1203.3699. 10 pp.

34. Danh T. N., Daykin D. E. Ordering integer vectors for coordinate deletions // Journal of the London Mathematical Society. 1997. 55(3). P. 417-426.

35. Daykin D. E. A simple proof of the Kruskal-Katona theorem // Journal of Combinatorial Theory, Scries A. 1974. 17. P. 252-253.

36. Daykin D. E. Erdos-Ko-Rado from Kruskal-Katona // Journal of Combinatorial Theory, Series A. 1974. 17(2). P. 254-255.

37. Erdos P., Ko C., Rado, R. Intersection theorems for systems of finite sets // The Quarterly Journal of Mathematics. 1961. 12(1). P. 313-320.

38. Frankl P. A new short proof for the Kruskal-Katona theorem // Discrete Mathematics. 1984. 48(2). P. 327-329.

39. Frankl P. Shadows and shifting // Graphs and Combinatorics. 1991. 7. P. 23-29.

40. Frankl P., Kalai G., Fliredi Z. Shadows of colored complexes // Mathematica Scandinavica. 1988. 63(2). P. 169-178.

41. Frankl P., Tokushige N. Weighted 3-wise 2-intersecting families // Journal of Combinatorial Theory, Series A. 2002. 100(1). P. 94-115.

42. Frankl P., Tokushige N. Random walks and multiply intersecting families // Journal of Combinatorial Theory, Series A. 2005. 109(1). P. 121-134.

43. Fliredi Z., Griggs J. R. Families of finite sets with minimal shadows // Combinatorica. 1986. 6(4). P. 355-363.

44. Harper L. H. Optimal numberings and isoperimetric problems on graphs // Journal of Combinatorial Theory. 1966. 1. P. 385-393.

45. Harper L. H. On a problem of Kleitman and West // Discrete mathematics. 1991. 93(2). P. 169-182.

46. Hilton A. J. W. A simple proof of the Kruskal-Katona theorem and of some associated binomial inequalities // Periodica Mathematica Hungarica. 1979. 10(1). P. 25-30.

47. Jukna S. Extremal combinatorics. Springerverlag Berlin Heidelberg, 2011.

48. Katona G. O. H. Intersection theorems for systems of finite sets. // Acta Math. Hungar. 1964. 15. P. 329-337.

49. Katona G. O. H. A theorem of finite sets // Proceedings of Tihany Conference, New York: Academic Press. 1966. P. 187-207.

50. Keevash P. Shadows and intersections: Stability and new proofs // Advances in Mathematics. 2008. 218(5). P. 1685-1703.

51. Körner J., Wei V. K. Odd and even Hamming spheres also have minimum boundary // Discrete mathematics. 1984. 51 (2). P. 147-165.

52. Kruskal J. The number of simplices in a complex // Mathematical Optimization Techniques, Berkeley - Los Angeles: Univ. of California Press. 1963. P. 251-278.

53. Leck U. Optimal shadows and ideals in submatrix orders // Discrete Mathematics. 200]. 235(1). P. 173-188.

54. Leck U. Nonexistence of a Kruskal-Katona type theorem for subword orders // Combinatorica. 2004. 24(2). P. 305-312.

55. Linclsey J. H. Assignment of numbers to vertices // Amer. Math. Monthly. 1964. 7. P. 508-516.

56. Lindström B. The optimal number of faces in cubical complexes // Arkiv for Matematik. 1971. 8. P. 245-257.

57. Mörs M. A generalization of a theorem of Kruskal // Graphs and Combinatorics. 1985. 1. P. 167-183.

58. O'Donnell R., Wimmer K. KKL, Kruskal-Katona, and monotone nets. // Foundations of Computer Science, 2009. P. 725-734.

59. Tiersma H. J. A note on Hamming spheres // Discrete mathematics. 1985. 54(2). P. 225-228.