Развитие метода граничных функционалов и его приложение к комбинаторным задачам

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

ГЛАВА 1. Оценки сумм граничных функционалов

1.1. Основные понятия

1.2. Асимптотики сумм граничных функционалов

1.3. Отношения между суммами граничных функционалов

1.4. Оценки сумм 5(6) для ординарных функциональных пар

1.4.1. Оценки сумм 5(6) для ординарных функциональных

1.4.2. Оценки сумм 5(6) для семейств й-связных множеств

1.4.3. Оценки сумм 5(6) для регулярных семейств

1.5. Оценки сумм 5(6) для нерегулярных функциональных пар

ГЛАВА 2. Асимптотика числа антицепей в декартовой степени звезд 5£

2.1.Основные понятия
2.2. Унимодальность множества 5£
2.2.1. Расширительность пар слоев 5£ с большими к
2.2.2. Расширительность пар слоев 5)* с малыми к
2.2.3. Доказательство основного результата
2.3. Асимптотика числа антицепей в 5).1
ГЛАВА 3. Оценки числа антицепей в трехзначной п-мерной решетке 63
3.1. О мощности слоев множества 63
3.2. Нижняя оценка числа антицепей в средних слоях множества 63
3.3. Логарифмическая выпуклость мощностей слоев
/с-значной п-мерной решетки
3.4. Расширительность пар слоев Ег31
ПРИЛОЖЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Значительное место в математике занимают перечислительные задачи, связанные с доказательством существования, алгоритмами построения и подсчетом числа элементов данного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, чиеле п вершинных графов с определенными свойствами или о числе изомеров химических элементов. Существующие методы решения таких задач можно разделить на два типа: комбинаторные и вероятностные.
К комбинаторным методам относится классический метод производящих функций, получивший развитие в середине XX века. Использование перечислительных теорем Пойа, де Брёйна и Робинсона позволяет получать некоторые соотношения между числовыми характеристиками изучаемых объектов. Метод заключается в том, что на основании рекуррентных соотношений выводится дифференциальное уравнение, решением которого является производящая функция. Разложение производящей функции в ряд дает точные или асимптотические формулы для коэффициентов. Тем не менее, методика построения производящих функций сложна и не всегда приводит к обозримым результатам, поэтому существует класс задач, которые не могут быть решены с помощью классических методов.
Существенную роль играют комбинаторно - вероятностные методы решения перечислительных задач. В своих работах эти методы применяли Ю.Л. Васильев, В.В. Глаголев, В.Л. Гончаров, В.Ф. Колчин, A.A. Сапоженко, В.Н. Сачков, Н. Алон, Дж. Спенсер, П. Эрдёш. Идея вероятностного метода заключается в том, чтобы показать, что почти все объекты из рассматриваемого класса обладают некоторым свойством. Вероятностные формулировки комбинаторных задач дают возможность при отыскании асимптотических формул использовать аппарат предельных теорем.
Задачи, в которых речь идет о нахождении числа объектов, имеющих заданную границу или заданную мощность границы, естественно назвать перечислительными изопериметрическими задачами. Такими являются, например, задачи о числе монотонных булевых функций (так называемая проблема Дедекинда), независимых множеств в двудольных графах, булевых функций ранга ноль, двоичных кодов с расстоянием 2, пар подмножеств с расстоянием 2 в графах. Оказалось что, такие задачи сводятся к вычислению сумм специального вида, которые называются суммами граничных функционалов. Метод граничных функционалов разработан A.A. Сапоженко для решения перечислительных изопериметрических задач. Он сочетает в себе комбинаторный и вероятностный подходы и позволяет получать предельные распределения для случайных величин типа числа компонент связности. Сущность метода заключается в сведении исходной комбинаторной задачи к вычислению сумм граничных функционалов и дальнейшему аналитическому исследованию последних. Цель метода — получение оценки исходных сумм через "простейшие” суммы граничных

функционалов. Это позволяет уйти от перебора и громоздких конструкций, возникающих при чисто комбинаторном подходе.
К классу перечислительных изопериметрических задач относятся задачи о числе антицепей в частично упорядоченных множествах, а, значит, и задачи о числе конечнозначных монотонных функций. Наибольшую известность среди таких задач получила упоминавшаяся выше проблема Дедекинда о числе ф(п) монотонных булевых функций или, что то же, о числе антицепей в единичном та-мерном кубе Вп.
В 1897 г. Р. Дедекинд вычислил значение ф{А). Р. Черч в 1940 г. и М. Уорд в 1946 г. получили соответственно значения ф(Ь) и ^’(6). В 1954 г. В. Гильберт показал, что ф(п) удовлетворяет неравенствам
2(l»/2j) < ф(п) < + 2.
В.К. Коробков в 1962 - 65 гг. показал, что ф(п) < 24'23(l"/2j), Ж. Ансель в 1968 г. улучшил верхнюю оценку до а Д. Клейтмен в 1969 г. доказал, что
log2^(n)~ (tn"2j).
Асимптотическое решение проблемы Дедекинда было получено А.Д. Коршуновым в 1980 г. Оно основано на описании ’’типичных” монотонных булевых функций и оценках числа подмножеств вершин слоев единичного га-мерного куба, имеющих заданную мощность границы.
В 1989 г. A.A. Сапоженко получил асимптотику числа антицепей в унимодальных частично упорядоченных множествах, из которой вытекает и асимптотика для ф(п).
Проблема вычисления мощности множеств функций п переменных из замкнутых классов исследовалась и для fe-значных логик. В 1974 г. В.Б. Алексеев получил асимптотику логарифма числа fc-значных функций, монотонных относительно произвольно заданного частичного порядка на S. В целом же асимптотик числа монотонных функций А-значной логики при к > 2 практически нет.
Таким образом, актуальным является развитие методов решения перечислительных изопериметрических задач и метода граничных функционалов, в частности.
Краткое содержание диссертации
Модельной задачей, иллюстрирующей подход, связанный с методом граничных функционалов, является проблема нахождения числа независимых множеств в двудольных графах. Пусть дан двудольный граф Г = (А, Z Е) с долями вершин А, Z и множеством ребер Е. Границей множества А С X называется множество
ö(A) = {v Е Z : 3 и Е А {u,v} Е Е}.
Подмножество С вершин графа Г называется независимым, если подграф, порожденный множеством С, не содержит ребер. Функция /(А) = 2Аэ*А)1 обладает следующими свойствами:
1) 0 < /(А) < 1 для всех АСА;
2) /(А) = 1 тогда и только тогда, когда А = 0;
3) ДАиЯ)>/(А)ДВ);
4) /(А Ui?) > f(A)f(B) тогда и только тогда, когда существуют и Е А и v € В такие, что f({u,v}) > Д{и})Д{г}).

Покажем, что функция /(ж) = (1 — 1 /х)х монотонно возрастает при всех х > 2. Производная функции равна
Л,)--«-“"« (ц1 + -1_)
Воспользуемся разложением 1п(1 + у) — у — ^ ^ получим
~1г,М _1 /-Л ( 1 1.1

'2(ж — I)2 3(ж-1)3 4(ж — I)4
Очевидно, что при х > 2 функция Р(х) положительна, следовательно, функция /(ж) возрастает. Из существования предела и монотонности функци /(ж) следует первое неравенство (2.2.8).
Лемма доказана.
Лемма 2.2.6. Пусть к = 2, п достаточно велико и таково, что для некоторого целого т выполнено п — Зт + 2. Тогда
|тт+і(С„_1(2))| > ^т+11Доказательство. Вычислим |тто+і(Сп_і(2))| при т = (п — 2)/3. Множество тт+і(Сп-і(2)) состоит из наборов, у которых в первых двух координатах есть хотя бы один нуль. По формуле включений - исключений получаем
Ітт+і(С'п_і(2))| = 2 • 2п~т~2(П ~ ^ -2Г
т + 1/ т + 1/ то + 1/3(га —1)
(2.2.9)
Теперь вычислим 5І52іт+1|:
ї|5?т+1І = 2п_т_2 ( п ) = 2П--2 (п ~ Л (2.2.10)
2 2’т+11 т + 1/ 2 га - 1 ' '
При достаточно больших п из (2.2.9) и (2.2.10) следует утверждение леммы.
Лемма 2.2.7. Пусть к > 3, и достаточно велико и топково, чтоо для некоторого целого т выполнено п = (& + 1)тга + &. Тогда
гт+1(Сп^(к)) > ^"т+1|.
Доказательство. Из (2.2.7) следует, что для любых к, л. и і,р < л. выполнено
і(л,М,р)> !^У |(~)Р (2.2.11)
Кроме того, при то, = (га — к)/(к 4- 1) выполнено
I — 1 Г П ^ кп~т~1 — 19Г*-1 12 12 2
2ІЧт+!І-2^то+1^ -|^"*+ІІ2(*Л-1)- (2-2Л2)