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

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики

На правах рукописи

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

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2013

3 1 ОКТ 2013

005536671

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель:

Официальные оппоненты:

доктор физико-математических наук, профессор Сапоженко Александр Антонович

доктор физико-математических наук, профессор кафедры математических методов прогнозирования факультета ВМК МГУ Дьяконов Александр Геннадьевич

кандидат физико-математических наук, старший научный сотрудник ВЦ РАН Вялый Михаил Николаевич

Ведущая организация:

Институт системного программирования РАН

Защита состоится 29 ноября 2013 г. в И часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/ в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан «ё. » октября 2013 г.

Ученый секретарь диссертационного совета

Костенко В. А.

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

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

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

хеХ хеХ хеХ

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

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

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

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

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

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

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

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

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

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

Теорема (П. Киваш8). Пусть е > 0, k^lu0^5< 5(е,к). Пусть Т С lAJ7! = (fc*j) и \F\ = (1 — <$)Q!). Тогда найдётся такое множество S, |£| = [г], что число множеств А € A F, для которых выполнено А % S, не превосходит е ■ •

Теорема (Р. О'Доннелл, К. Виммер9). Пусть s > 0, 5 = 5(e) > 0, и е <

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

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

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

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

355-363.

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

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

Пусть Т С и ^ < 1 — е. Тогда либо выполнено

(2) п ' либо найдётся г 6 [п], для которого

\{Ае?\1еА}\ > 1

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

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

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

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

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

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

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

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

нян и Л. Хачатрян16 рассмотрели задачу для булева куба с ограничениями. С. Л. Безруков17, Дж. Кёрнер и В. Вей18, X. Тирсма19 доказали аналог теоремы Краскала-Катоны в двуслойном частично упорядоченном множестве, один из слоёв которого состоит из двоичных наборов фиксированной длины с чётным числом единиц, а другой - из двоичных наборов с нечётным числом единиц, и сравнимыми являются наборы, расстояние Хэмминга между которыми равно 1. У. Лек20 доказал аналогичную теорему для порядка подматриц - декартова произведения булевых кубов с удалённой наибольшей

точкой.

Р. Алсведе и Н. Каи21, Д. Дайкин и Т. Дан22 доказали существование минимизирующего тень порядка для так называемого порядка подслов SO{2) -множества слов в алфавите из двух символов, частичный порядокна котором введён следующим образом: слово 5 предшествует слову /3, если а можно получить из ¡8 удалением символов. У. Лек23 показал, что для порядка SO{n) в алфавите из п > 2 символов не существует аналога теоремы Краскала-Катоны, то есть решения задачи минимизации тени в этом частично упорядоченном множестве нельзя описать в терминах линейного порядка. Р. Алсведе и В. С. Лебедев24 рассматривали задачу минимизации тени в множестве слов в алфавите из двух символов с отношением слово-подслово.

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

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

I6Ahlswede R., Aydinian H., Khachatrian L. H. More about shifting techniques // Européen J. Combin. 2003. 24(5). P. 551-556.

"Безруков С. Л. Об одной изопериметрической задаче // Методы дискретного анализа е оптимизации

управляющих систем. 1983. 40. С. 3-18. .■„„„,„

18K5raer J., Wei V. К. Odd and even Hamming spheres also have minimum boundaxy // Viscrete

MathemaHcs. 1984. 51 (2). P. 147-165.

19Tiersma H. J. A note on Hamming spheres // Discrète MathemaHcs. 1985. 54(2). P. 225-228

20Leck U Optimal shadows and ideals in submatrbe orders // Discrète MathemaHcs. 2001.235(1). P. 173-188. "Ahlswede R., Cai N. Shadows and isoperimetry under the sequence-subsequence relation // Combxnatonœ.

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. *W U. Nonexistence of a Kruskal-Katona type theorem for subword orders // Combmatonca. 2004. 24(2).

P 305-312

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

его вершин. Границей множества А называется множество вершин Г(А) = {v е A I 3w £ A,(v,w) G E(G)}. Вершинный вариант изопериметриче-ской задачи заключается в нахождении множества вершин заданной мощности с минимальным размером границы. Рёберные варианты изоперимет-рической задачи заключаются в нахождении множества вершин А заданной мощности с максимально возможным числом внутренних рёбер 1(A) = {(яъ^г) £ Bio) I ai € A, a<i £ А}, либо с минимальным числом внешних рёбер О(А) — {(а,Ь) 6 E(G) | а Е A, b ф А}. Для регулярного графа эти две задачи эквивалентны, поскольку в ^-регулярном графе для любого множества А верно 1(A) + О(А) = к •

Решения изопериметрических задач в булевом кубе, то есть в графе (2W, {(А, В) I А С В б 2И, \А\ = \В\ - 1}), были найдены Л. Харпером25. Теорема (JT. Харпер). Пусть т = (JJ) + (") + ...+ (£)+ m0, 0 < т0 < Gt+i) • Пусть J- является квазисферой мощности т, то есть объединением семейств для 0 ^ i ^ к и конечного лексикографического отрезка (¿"'J длины то. Тогда для любого Q С \Q\ = т, выполнено |Г(С/)| ^ |r(.F)|. Теорема (Л. Харпер). Пусть Т — начальный лексикографический отрезок 2'п1 длины т. Тогда для любого Q С 2^, \Q\ = т выполнено \I(G)\ ^ l-^C^7)!-Заметим, что теорема Краскала-Катоны является следствием решения вершинно-изопериметрической задачи.

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

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

25Нагрег L. Н. Optimal numberings and isoperimetric problems on graphs // Journal of Combinatorial Theory. 1966. 1. P. 385-393.

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

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

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

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

Рёберно-изопериметрические задачи часто удаётся переформулировать в терминах задач минимизации веса идеала в частично упорядоченном множестве. Р. Алсведе и Д. Катона31 описали решения этой задачи в булевом кубе для монотонных и унимодальных симметрических функций. Теорема (Р. Алсведе, Д. Катона). Пусть Т С — идеал, то есть если A G Т и В С А, то В S Т. Пусть Щ = |{Л <Е Т | \А\ = г}|, и /(.F) =

У)KiWi. Тогда min f (F) достигается на следующих семействах: i r|=m

1. если Wo < W\ < ... ^ W„, то минимум достигается на квазисфере мощности т;

2. если Wo ^ Wi > ... > Wn, то минимум достигается на начальном лексикографическом отрезке семейства 2'п1 мощности т;

3. если W0 < W\ ^ ... ^ Wq > Wq+1 ^ ... > Wn, то минимум достигается на объединении некоторой квазисферы и некоторого начального лексикографического отрезка;

4. если W0 ^ Wi > ... > Wq < Wq+1 < • • - < Wn, то минимум достигается на пересечении некоторой квазисферы и некоторого начального лексикографического отрезка;

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

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

30Натрет L. H. On a problem of Kleitman and West // Discrète Mathematics. 1991. 93(2). P. 169-182.

31Ahlswede R., Katona G. 0. H. Contributions to the geometry of Hamming spaces // Discrète Mathematics. 1977. 17(1). P. 1-22.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во введении приводится обзор исследований, связанных с темой диссертации, и кратко излагается содержание работы.

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

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

Пусть А и В - элементы ('£), А = {аь о2,..., ак}, В = {61, Ь2, • • ■, Ьк}, и ах < а,2 < ... < <Ь2 < ... <Ьк. Множество А предшествует множеству В в порядке С, если < Ьг для всех г = 1,2,..., к.

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

В разделе 1.4 выводятся формулы для вычисления размера тени идеала. Теорема. [1] Пусть Т С — идеал. Тогда размеры теней Т вычисляются по формулам \АТ\ = £ а^А), = £ в„(Л), \*Г\= £ з(А), где

А<кТ Ае? А&Т

а^А) = тт([п] \ А) - 1, зи(А) = п- тахА, = + ви(А).

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

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

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

ства в крайних слоях булева куба.

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

Во второй главе доказывается несуществование аналога теоремы Крас-кала-Катоны для задачи минимизации двусторонней тени в центральных слоях булева куба, то есть несуществование линейного порядка на слое булева куба, все начальные отрезки которого минимизируют двустороннюю тень. В разделе 2.1 доказываются свойства частично упорядоченного множества, к минимизации веса идеалов которого сводится задача минимизации тени. В разделе 2.2 устанавливаются свойства минимизирующего порядка. В разделе 2.3 показывается, что в центральных слоях булева куба никакой порядок, обладающий этими свойствами, не является минимизирующим, и оценивается максимальный размер системы вложенных решений. Теорема. [1] При п>7 никакой линейный порядок на не минимизирует двустороннюю тень. Для любого линейного порядка, заданного на ('3')) существует такое число т ^ шах{4п — 14,15}, что начальный отрезок этого порядка длины т не является минимальным по двусторонней тени семейством.

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

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

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

по двусторонней тени семейством. Обозначим это семейство через С\(А), и положим Ci(n, к) — Ci({l, 2,...,&}) С (М).

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

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

В разделе 3.3 описываются минимальные по двусторонней тени семейства малой мощности, образующие систему вложенных семейств. Теорема. [1] Если к^ то начальные лексикографические отрезки Ci(n, к) являются минимальными по двусторонней тени. Теорема. [2] Если 2 < к < п — 2, то семейство

С[(п, к) = Ci(n, к) ü {{1,2,..., к - 2, к + 1, к + 2}}

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

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

Теорема. [3] Если п ^ 13, то Ci(n,3) является минимальным по двусторонней тени семейством.

Теорема. [3] Если п ^ \кА, то С\{п,к) является минимальным по двусторонней тени семейством.

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

Обозначим через Сг(п, к) семейство {А | А П [&] ^ тг — г}, то есть пересечение слоя с шаром Хэмминга с радиусом 2г.

Теорема. [6] С2(п, 3) является минимальным по двусторонней тени семейством.

Публикации по теме диссертации

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-28 июня 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.

Напечатано с готового оригинал-макета

Подписано в печать 08.10.2013 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 70 экз. Заказ 308.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет имени М. В. Ломоносова

На правах рукописи

04201363840

Башов Максим Александрович

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. и., профессор Сапоженко Александр Антонович

Москва - 2013

Оглавление

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

семейства 41

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

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

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

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

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

Литература 69

Введение

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

Пусть (М, — некоторое частично упорядоченное множество, х € М. Нижней тенью элемента х называется множество непосредственно предшествующих ему элементов: Ах — {у £ М \ у < х}. Верхней тенью элемента х называется множество непосредственно следующих за ним элементов: Х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 вводится порождённый на слое булева куба оператором сдвига частичный порядок С и устанавливаются его свойства. Показывается, что при решении задачи минимизации можно, не ограничивая общности, рассматривать только идеалы данного частичного порядка. Доказывается, что если двусторонние тени двух множеств имеют непустое пересечение, то эти множества сравнимы в частичном порядке. Устанавливается, что лексикографический порядок является линейным расширением введённого частич