Метод граничных функционалов в перечислительных изопериметрических задачах Сапоженко, Александр Антонович

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

Актуальность теин исследований. В дискретной математике, где множества изучаемых объектов, как правило, конечны и, вместе с тем, достаточно велики, существенную роль играет вопрос о модности этих множеств. Зто важно, например, с алгоритмической точки зрения для оценки сложности перебора при реиении дискретных задач (I, раздел 31,, для получения низших мощностнах оценок и решения вопроса о существовании того или иного типа объектов (23 для оценки эффективности вероятностных алгоритмов (II, (211. В ряде случаев асимптотика или даже оценки модности множеств комбинаторных объектов представляют самостоятельный интерес. Сюда можно отнести, например, так называемую проблему Дедекинда о числе монотонных булевых функций [31,(41,[51. Бе асютгтотическое решение, наиденное А.Д.Корауновым сравнительно недавно (см.(51,[61), получено им с помощью довольно громоздких комбинаторных конструкций, связанных с перебором большого количества случаев. С другой стороны, существует целый ряд перечислительных задач из различных областей дискретной' математики, кмещах общую с проблемой Дедекинда комбинаторную природу . К ним относятся задачи о числе независимых множеств в двудольных графах, задача о числа булевых функций с интервалами только размерности ноль, о числе двоичных кодов с расстоянием 2 (см.(301), задача о протекании (перколяции) (71, многие задачи нз теории многозначных функций [81,(91. Во. всех этих задачах речь идет о нахождении числа объектов, нмеювдх заданную границу зли заданную мощаость границы. Поэтому естественно назвать их перечислительными изопериметрическкмн задачами (сокращенно, ИЗ).

Общее в этих задачах также то, что все они, как оказалось, сводятся к вычислению сумм специального вида, которые называются здесь суммами граничных функционалов (СРФ). Весьма актуальной поэтому является разработка единого метода решения задач такого типа. Основным побудительным мотивом для разработки метода является стремление уйти от перебора и громоздких конструкций, неизбежных при традиционном чисто комбинаторном подходе к решению перечислительных изопериметричэских задач. Здесь эта цель достигается с помощью сведения исходной комбинаторной задачи к вычислению СГФ и дальнейшем аналитическом исследовании последних.

Постановка задачи и примеры. Граничным называется функционал Ф, определенный на семействе всех подмножеств некоторого множества X и обладающий следующими свойствами:

1. О <. ф(А) < 1 для всех АсХ ;

2. ф(А) = 1 «Ьй;

3. ф(АиВ) > <р<А)ф(В);

4. ф(АиВ) > (р(А)(р(В) * (э иеА)(э v«B) (fXtu.v)) > ф({и))ф({т>).

Пара (Х,ф), где X - множество (как правило, конечное), а ф -граничный функционал, называется функциональной парой (сокращенно, <Ш). Задача ВСГФ состоит в вычислении сумм вида

Т(1) = I ф(А). АсХ

Под вычислением здесь понимается представление ее асимптотики в

виде формул, через "легко вычислимые" суммы аналогичного вида,

берущиеся по связным подмножествам множества X. Использование

термина "граничный функционал" объясняется тем, что функции,

связанные с различными понятиями границы множеств, обычно чэбладают

свойствами 1-4.

Примар І (Задача о числе независимых множеств в двудольном графе). Пусть G=(X,Z;E) связный двудольный граф с долями вершин X.Z и множеством ребер Е и АсХ. Границей (или тенью) множества А называется множество 3(A) = {v«Z:(3u)(u,v)eE}. Нетрудно

проверить, что функционал <р, такой, что <р(А) = 2"' * '', обладает свойствами 1-4. Пусть ф(С) - число независимых,"множеств в графе G=(X,Z;E). Тогда оказывается, что (см. лекалу 3.3.1)

ф(С) =2l^zl J ₂-ia(A>| _{= 2}|Z| _{T(I(j) t}

A=X

где I_c = (X,

Припар 2 (Задача о пврколяцин). Рассмотрим плоскую целочисленную реаетку Г^, состоящую из всех пар вида (а,Ь) , где a, b -целые числа. Пары (точки) (а,о) и (a',b') называются соседними, если |а - а' | + |Ь - Ь'| = 1. Границей многества A s 1^ называется множество Н(А), включающее все точки из HgVA, имепзю хотя бы одну соседнюю точку из множества А. Связное подмножество точек реветки

называется кластером. Функционал <р(А) = р (1-р) * ' обладает

свойствами I - 4. В теории просачивания (перколяции) (см. Х.Кестен [71, стр.84) важную роль для нахождения вероятности перколяции по вершинам играет сукм J <р (А), где суммирование ведется по всем кластерам А, содержащим начало координат.

Прзмер 3 (Проблема Дедекинда). Пусть В^п - единичный п-ыерный куб с обычным отновением частичного порядка. Антицепью называется произвольное подмножество, состоящее из элементов куба, попарно несравнимых между собой. Задача заключается в нахождении числа

(n) антицепей в В^п. Пусть в - к-й слой куба В^п, состоящий из наборов с К единицами. Проекцией произвольного множества AsBⁿ на слой в (или границей множества /?) назовем множество Р^(^) тех элементов, из в, которые сравнимы хотя бы с одним элементом из А. Если AsB__t (АсВ*^,)> то пусть Q(A) - число антицепей D с U В" (D с U В?), удовлетворяющих условию P. ,(D)=A (P_v ,(D)=A). Пусть

^.=^-,¹¹^, al_t- множество всех антицепей Агі^. Для всех Сс^ полагаем Ш) = Q(A П В_,) U Q(A П B₊₁). Пусть ф(С) = Q(C)2~!^Pk^(C)' для всех С с Х^.. Тогда

ф(п> = 2^!Вк^! 2- Ф(С> = г'^п 2- .

к к

Если при этом Q(C) < 2І^СІ для всех непустых множеств С с 2^, ТО ЦІ

удовлетворяет условиям 1-4. При четных ті и к = п/2 эти условия оказываются выполненными, а пара 1^ = (Х^ф) является ФП.

Приведенные примеры, перечень которых можно продолжить, показывают , что вычислив сумму вида Т(1), мы фактически получаем решение соответствующей перечислительной ИЗ.

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

граничный функционалов (сокращенно, метода РФ), и решения с его помощью некоторых перечислительных ИЗ. Под приближенным вычислением мы понимаем получение асимптотик сумм граничных функционалов (СГФ) и решений перечислительных задач. Мы стремимся к тому, чтобы, сведя некоторую перечислительную задачу к

вычислению СГО для некоторой Ш и определив ее тип , а также ряд параметров ФП, получить готовую асимптотическую формулу для числа искомых объектов.

Рассмотрим метод РФ в применении к задаче о числе <|>(G) независимых множеств в двудольном графе G (см. пример I). Поскольку вычисление величины 2^IZ! для заданного графа G=(X,Z;E) не вызывает трудностей, задача сводится к вычислению СГФ

Т(1) = I ф(А) (0.1)

А=Х

-ia(A)i

для функциональной пары I=I_G=(X,(p>, где ф(А) = 2 . Свойства 1-4 граничных функционалов позволяют ввести граф Н(1)=(Х;Е) с

множеством ребер E=({u,v): ф{{и,7)) > (f({u))-<{v))j и тем самым

определить понятие связного множества. Именно: АсХ называется связным, если подграф графа Н(1), порожденный множеством А, связен. Пусть II = 41(1) - семейство всех связных подмножеств множества X. Далее для произвольного Ж с 31 определим семейство (8) как множество всех А&Х, каждая компонента связности которых принадлежит семейству Ж, а также функционал

а^а'<Ж) = J (v (0.2)

Справедливо утверждение о том, что

I ф(А) < I ф(А) < ф(А) I ф(А) (0.3)

Ае«(Ж> А=Х А(<5(Ж> В«<«\8)

Эти неравенства содержат идею получения асимптотики суммы Т(С).

Именно: положив S(D)= ф(А), будем искать такое Ж = II, чтобы A««(D>

выполнялись следующие два условия:

1) S(U\S)-.1, (0.4)

2) существует простая асимптотическая формула, выражающая S(8) через суммы типа (0.2), вычисление которых обычно не вызывает затруднений.

В связи с тем, что S(B) <; ехр(а'(0)), условие (0.4) сводится к условию

а¹ (

Условия (0.4) и (0.5) предполагают неявно наличие параметра п,

стремящегося к а>, относительно которого рассматриваются
асимптотики.

Очевидно следующее соотношение:

о'(Р)= I <р(А) = 2 2-^,3<^M!=V 2-«Ф(»,₈),
UV А*Р

где Ф(Х),е) - число множеств Ае» с границей мощности g, а g,=g, (*>) - наименьшая мощность границы у множества из Ї). Поэтому для доказательства (0.5) достаточно доказать существование такого є, чтобы выполнялись условия:

>(»,g) <2^_в(1-^є) (0.6)

У 2^_Єв -О при и-» (0.7)

Таким образом, проверка условия (0.4) приводит к оценка числа $(!),g) множеств А?В с мощностью границы, равной g. Мы вновь сталкиваемся с изопериметрической задачей, но в "облегченном"

варианте: нужна лишь оценка сверху. Неравенство вида (0.6) удается доказать (см. главу II) для довольно широкого класса графов, называемых расширителями. Тем самым, для каждого такого графа С и для подходящего S выполнено

T(I_G) „. S(8) (0.8)

Введем теперь параметр п явным образом: пусть = 8 . Проблема состоит в том, чтобы найти асимптотику для S(S ). Полагаем

tt_k(8_n) = JA((S_n):число компонент связности А равно kj,

A««_k(»_n) k»

Оказывается, что последовательность o_n удовлетворяет рекуррентному соотношению:

для некоторой последовательности а такой, что a > a_n при всех к. Эти неравенства вместе с равенством (0.9) влекут неравенство о . < (a ₀)^k/k? и существование в такого, что

У о ,-- 0(0 ). Положим b = rain a , . Тогда, если

n ^Ь_П = ^an,0 ^{+ 0(,)}' ^T

о . „. (a „)^k/k! и о „ exp{a .). (0.10)

n,k n,0 n r _n>o

В этом случав цель достигнута, поскольку о =S(Ж ), а a ,= a' (В ). Заодно мы получаем предельное распределение случайной величины і ,

равной числу компонент связности случайного множества АсХ: P(5_n=W~ ((o^Mmexpi-o.^)

Заметим, что при выполнении условия ib - a _Q! = о На ₀) )]

величина имеет асимптотически нормальное распределение. В этом и в более сложных случаях используется приближенное представление суммы о = S(S ) произведениями вида П(1+ф(А)>, берущимися по семействам типа S5 , а также семействам подмножеств из »_п и семействам более высокого порядка (см. 3.4). Отметим, что полученные здесь условия сходимости к пуассоновскому распределению отличны от тех, что получаются с помощь» метода моментов (см., например, (101, стр.117)

Метод ТФ ориентирован на решение перечислительных ИЗ. С его помощью удается получать асимптотики для числа комбинаторных объектов довольно сложной природы, какими являются антицепи в частично упорядоченных множествах, коды, независимые множества, покрытия, паросочетания и т.п. Он позволяет решать некоторые теоретико-вероятностные задачи: получать предельные распределения для случайных величин типа числа компонент связности, вычислять средние значения, решать дискретные экстремальные задачи типа расшифровки монотонных функций и поиска максимального нуля в вероятностной постановке.

Дальнейшее развитие метода - в расширении области его применимости, именно:

1. В распространении метода ГФ на случай задач , в которых элементы граница и'элементы самого множества принадлежат одному пространству (как,напримёр, в задаче о перколяции).

2. В ослаблении условий, при которых получены неравнства вида

(0.6), что позволит получить существенные продвижения в теории многозначных функций.

3) В получение асимптотик СРФ вида S(8) через суммы вида a^v{35) для более слабых ограничений.

Методы исследования. В работе используются метода теории графов, комбинаторики и теории вероятностей. При выводе асимптотик (0.8) используются вероятностные и комбинаторные методы, а при получения неравенств вида (0.6) - методы теории графов и комбинаторики.

Научная новизна. В диссертации получены следующие основные

результаты:

1. Разработан метод граничных функционалов для решения
перечислительных изопериметрических задач.

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

3. С помощью метода РФ получены асимптотики для числа антицепей в унимодальных частично упорядоченных множествах.

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

Б. Для достаточно широкого класса ранжированных множеств получены нетривиальные нижние оценки числа антицепей.

fi. Получено решение задачи поиска максимального нуля случайной млготонной (0,1)-<35ункции, заданной на унимодальном множестве.

Практическая ценность. Работа имеет теоретическую направленность. Полученные результаты могут применяться для

получения асимтотик при решении перечислительных и теоретико-вероятностных комбинаторных задач.

Апробация и публикации. Результаты диссертации докладывзшсь на международной конфоренциии по основам теории вычислений (Казань, 1987), на советско-германских семинарах (Самарканд, [987, Росток, 1988, Ереван, 1989), на международном семинаре по дискретной математике (Благоевград, 1990), на международном семинаре по экстремальным проблемам в конечных множествах (Вытеград, 1991), на международной конференции по случайным ірафам (Познань, 1991), на международном семинаре по сложности и реализации булевых функций (Дагштул, 1992), на всесоюзных конференциях по проблемам теоретической кибернетики (Иркутск, 1985, Горький, 1988, Волгоград, 1990), на всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1987, 199()), на всесоюзном семинаре по вероятностным методам в дискретной математике (Петрозаводск, 1988), на семинаре по кибернетике под руководством чл.-корр. РАН С.В.Яблонского, на семинаре по сложности булевых функций под руководством чл.-корр. РАН О.Б.Лупанова и с.н.с. В.М.Храпченко, на семинаре чл.-корр. РАН Б.А.Севастьянова и проф. В.Ф.Колчина в Математическом институте им. В.А.Стеклова, на других конференциях и семинарах.

Результаты диссертации опубликованы в работах 118 - 311.

Структура и объем работы, диссертация состоит из введения, четырех глав и списка литературы. Первая и четвертая главы содержат по четыре параграфа, вторая - три, а третья - пять параграфаов. Объем работы 240 страниц, включая 8 страниц

цитированной литература. В списке литературы 81 наименование.