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

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Башов, Максим Александрович. Минимизация тени в слое булева куба : диссертация ... кандидата физико-математических наук : 01.01.09 / Башов Максим Александрович; [Место защиты: Моск. гос. ун-т им. М.В. Ломоносова].- Москва, 2013.- 73 с.: ил. РГБ ОД, 61 13-1/1013

Введение к работе

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

Пусть (М, ^) — некоторое частично упорядоченное множество, х Є М. Нижней тенью элемента х называется множество непосредственно предшествующих ему элементов: Ах = {у Є М \ у < х}. Верхней тенью элемента х называется множество непосредственно следующих за ним элементов: Vx = {у Є М | у > х}. Двусторонняя тень ^хх — это объединение множеств Ах и \7х. Тенью множества ХСМ называется объединение теней его элементов: АХ = |J Ах, VX = (J Vz, ^ХХ = \J *ж.

хеХ хеХ хеХ

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

Подобные задачи возникают, например, при перечислении комбинаторных объектов, таких как монотонные булевы функции¹ или независимые множества в графах², в теории надёжности сетей³.

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

Сапоженко А. А. Проблема Дедекинда и метод граничных функционалов. М., Физматлит, 2009. Alon N. Independent sets in regular graphs and sum-free subsets of finite groups // Israel Journal of Mathematics. 1991. 73(2). P. 247-256.

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

Решения задачи минимизации односторонней тени в слое булева куба были независимо описаны Дж. Краскалом и Д. Катоной⁵.

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

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

Теорема (М. Мере, 3. Фюреди и Дж. Р. Григгс). Начальный лексикографический отрезок (^/) длины т является единственным с точностью до изоморфизма минимальным по нижней тени семейством мощности т в случае, когда мощность нижней тени отрезка длины т + 1 превосходит мощность тени отрезка длины т.

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

Теорема (П. Киваш⁸). Пусть є>0, к^1и0^5< 5(є,к). Пусть Т С (к), \АТ\ = {k-i) ^и 1*^1 ⁼ (1 ^— ^)CD- Тогда найдётся такое множество S, \S\ = \х\, что число множеств А Є AJ⁷, для которых выполнено А <. S, не превосходит є (^)-Теорема (Р. О'Доннелл, К. Виммер⁹). Пусть є > 0, 5 = 5(e) > 0, и є ^ К

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

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

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

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

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

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

Пусть Т С (jj), и \щ ^ 1 — є. Тогда либо

выполнено

W⁷! \Т\ _ logn

^{(,«) (ї)}

либо найдётся і Є [п], длд которого

\{АєТ\ієА}\ \{А є J" І і і А}\ 1

Известно несколько обобщений теоремы Краскала-Катоны. Булев куб можно рассматривать как декартово произведение цепей длины 2 или как произведение однолучевых звёзд. Дж. Клементе и Б. Линдстрём¹⁰ доказали, что лексикографические отрезки слоя имеют минимальную одностороннюю тень в декартовых произведениях цепей произвольной длины. Б. Линдстрём¹¹ обобщил теорему Краскала-Катоны на случай декартовых степеней двухлу-чевой звезды, то есть частично упорядоченного множества{0,1,2}, в котором О > 1, 0 > 2, а1и2 несравнимы. С. Л. Безруков¹² установил справедливость обобщения для декартова произведения звёзд с произвольным числом лучей. П. Франкл, Ж. Калаи и 3. Фюреди¹³ получили обобщение для частично упорядоченного множества, двойственного произведениям звёзд, для некоторых значений параметров. Справедливость этого результата для произвольных значений параметров следует из общей теории, развитой С. Л. Безруковым и У. Леком¹⁴. С. Л. Безруков и Р. Элсассер¹⁵ обобщили теорему Краскала-Катоны на случай произведения регулярных пауков — частично упорядоченных множеств, являющихся обобщением звёзд.

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

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

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

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

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

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

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

нян и Л. Хачатрян¹⁶ рассмотрели задачу для булева куба с ограничениями. С. Л. Безруков¹⁷, Дж. Кернер и В. Вей¹⁸, X. Тирсма¹⁹ доказали аналог теоремы Краскала-Катоны в двуслойном частично упорядоченном множестве, один из слоев которого состоит из двоичных наборов фиксированной длины с чётным числом единиц, а другой — из двоичных наборов с нечётным числом единиц, и сравнимыми являются наборы, расстояние Хэмминга между которыми равно 1. У. Лек²⁰ доказал аналогичную теорему для порядка подматриц — декартова произведения булевых кубов с удалённой наибольшей точкой.

Р. Алсведе и Н. Каи²¹, Д. Дайкин и Т. Дан²² доказали существование минимизирующего тень порядка для так называемого порядка подслов5'0(2) — множества слов в алфавите из двух символов, частичный порядок на котором введён следующим образом: слово а предшествует слову /3, если а можно получить из /3 удалением символов. У. Лек²³ показал, что для порядка SO(n) в алфавите из п > 2 символов не существует аналога теоремы Краскала-Катоны, то есть решения задачи минимизации тени в этом частично упорядоченном множестве нельзя описать в терминах линейного порядка. Р. Алсведе и В. С. Лебедев рассматривали задачу минимизации тени в множестве слов в алфавите из двух символов с отношением слово-подслово.

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

С задачей минимизации тени тесно связаны изопериметрические задачи на графах. Пусть G = (V, Е) — граф, АСУ- некоторое множество

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

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

Korner J., Wei V. К. Odd and even Hamming spheres also have minimum boundary // Discrete Mathematics. 1984. 51 (2). P. 147-165.

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

Leek U. Optimal shadows and ideals in submatrix orders // Discrete Mathematics. 2001. 235(1). P. 173-188.

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

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

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

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

его вершин. Границей множества А называется множество вершин Т(А) = {v <Е А \ 3w ф A,(v,w) Є E(G)}. Вершинный вариант изопериметриче-ской задачи заключается в нахождении множества вершин заданной мощности с минимальным размером границы. Рёберные варианты изоперимет-рической задачи заключаются в нахождении множества вершин А заданной мощности с максимально возможным числом внутренних рёбер 1(A) = {(0.1,0.2) E(G) I а\ Є A, 0-2 А}, либо с минимальным числом внешних рёбер О (А) = {(а,6) Є E(G) І а Є A_}b . А]. Для регулярного графа эти две задачи эквивалентны, поскольку в /с-регулярном графе для любого множества А верно 1(A) + О (А) = к \А\.

Решения изопериметрических задач в булевом кубе, то есть в графе (2^, {(А, В) \АСВ Є 2^, \А\ = \В\ - 1}), были найдены Л. Харпером²⁵.

Теорема (Л. Харпер). Пусть т = (о) + (і) + + О + ^то> 0 ^ то < (^). Пусть Т является квазисферой мощности т, то есть объединением семейств (y) для 0 ^ і ^ к и конечного лексикографического отрезка (й) длины то. Тогда для любого Q С 2^_; \Q\ = т, выполнено \T(Q)\ ^ |r(.F)|.

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

Заметим, что теорема Краскала-Катоны является следствием решения вершинно-изопериметрической задачи.

С. Л. Безруков²⁶'²⁷ описал все попарно не изоморфные решения вершинно-изопериметрической задачи в булевом кубе для некоторых значений параметров. Р. Алсведе и Н. Каи²⁸ описали решения изопериметрической задачи в графе, являющемся диаграммой Хассе порядка подслов 5*0(2).

Примером изопериметрической задачи, решения которой в общем случае не удаётся описать в виде отрезков некоторого порядка, является задача Клейтмана-Веста. В этой задаче рассматривается граф с множеством вершин

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

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

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

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

(у) и множеством рёбер {(А, В) \ \ А П В\ = к — 1}. Р. Алсведе и Д. Катона²⁹ рассмотрели случай к = 2 и показали, что решения принадлежат к одному из двух классов множеств. При к > 2 решение задачи для произвольной мощности множества неизвестно. Л. Харпер³⁰ получил решения некоторых мощностей с помощью сведения исходной задачи к задаче минимизации веса идеала частично упорядоченного множества и рассмотрения её непрерывного аналога.

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

Теорема (Р. Алсведе, Д. Катона). Пусть Т С 2^ — идеал, то есть если А є Т и В С А, то В є Т. Пусть К_г = \{А є Т \ \А\ = г}\, и f(F) = ^KjWi. Тогда min /(J⁷) достигается на следующих семействах:

і Т:\Т\=т

если Wq ^ W\ ^ ... ^ W_n, то минимум достигается на квазисфере моищости т;
если Wo ^ W\ ^ ... ^ W_n, то минимум достигается на начальном лексикографическом отрезке семейства 2^ моищости т;
если Wq ^ W\ ^ ... ^ W_q ^ W_q+i ^ ... ^ W_n, то минимум достигается на объединении некоторой квазисферы и некоторого начального лексикографического отрезка;

4- если Wo ^ W\ ^ ... ^ W_q ^ W_q+\ ^ ... ^ W_n, то минимум достигается на пересечении некоторой квазисферы и некоторого начального лексикографического отрезка;

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

Ahlswede R., Katona G. О. Н. Graphs with maximal number of adjacent pairs of edges // Acta Math. Acad. Sci. Hungar. 1978. 32. P. 97-120. ³⁰Harper L. H. On a problem of Kleitman and West // Discrete Mathematics. 1991. 93(2). P. 169-182.

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

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

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

Методы исследования. Результаты диссертации получены с помощью методов экстремальной комбинаторики. Используется метод операторов сдвига и обобщение метода Алсведе-Катоны для решения задачи минимизации веса идеала частично упорядоченного множества с невозрастающей весовой функцией.

Научная новизна. Результаты диссертации являются новыми.

Основные результаты:

Показано, что задачи минимизации односторонней и двусторонней тени в слое булева куба сводятся к задачам минимизации веса идеала.
Описаны решения задачи минимизации двусторонней тени произвольной мощности в к-м слое n-мерного булева куба при к ^ 2 и при к^п-2.
Получены верхние оценки мощности максимальной системы вложенных решений задачи минимизации двусторонней тени, и показано, что за исключением случая п = б, к = 3, при ЗО^к-Зв к-м слое n-мерного булева куба не существует минимизирующего двустороннюю тень линейного порядка.
В к-м слое n-мерного булева куба для произвольных п, к описаны решения задачи минимизации двусторонней тени мощности, не превосходящей 2 + к(п — к), образующие систему вложенных множеств. Показано, что решение мощности 1-\-к(п — к) единственно с точностью до изоморфизма.

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

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

Публикации. По теме диссертации опубликовано 6 работ, в том числе 3 работы [1; 3; 6] в рецензируемых изданиях, включенных в перечень ВАК.

Апробация результатов. Результаты диссертации докладывались на следующих семинарах и конференциях:

на семинаре «Дискретный анализ» под руководством А. А. Сапоженко, Т. В. Андреевой и А. Б. Дайняка (кафедра математической кибернетики ВМК МГУ) в 2010-2013 гг.;

на семинаре по теории кодирования добрушинской математической лаборатории ИППИ РАН под руководством Л. А. Бассалыго в 2011 г.;

на семинаре «Дискретная математика и математическая кибернетика» под руководством В. Б. Алексеева, А. А. Сапоженко и С. А. Ложкина (кафедра математической кибернетики ВМК МГУ) в 2013 г.;

на ежегодной международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2010»;

на XI международном семинаре «Дискретная математика и её приложения» (Москва, 18-23 июня 2012 г.).

Структура и объем диссертации. Работа состоит из введения, трех глав и списка литературы, содержащего 59 наименований. Диссертация содержит 73 страницы.

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

Похожие диссертации на Минимизация тени в слое булева куба