Содержание к диссертации
Введение
1. Оценки сумм граничных функционалов 12
1.1. Основные понятия 12
1.2. Асимптотики сумм граничных функционалов 13
1.3. Отношения между суммами граничных функционалов 16
1.4. Оценки сумм S{B) для ординарных функциональных пар 21
1.4.1. Оценки сумм {В) для ординарных функциональных пар 22
1.4.2. Оценки сумм S{B) для семейств rf-связных множеств 25
1.4.3. Оценки сумм S{B) для регулярных семейств 32
1.5. Оценки сумм S{B) для нерегулярных функциональных пар 35
2. Асимптотика числа антицепей в декартовой степени звезд S% 42
2.1.Основные понятия 42
2.2. Унимодальность множества STkl 44
2.2.1. Расширительность пар слоев 5 с большими к 46
2.2.2. Расширительность пар слоев S% с малыми к 52
2.2.3. Доказательство основного результата 58
2.3. Асимптотика числа антицепей в 5 59
3. Оценки числа антицепей в трехзначной п-мерной решетке Щ 64
3.1. О мощности слоев множества Е% 64
3.2. Нижняя оценка числа антицепей в средних слоях множества Е% 72
3.3. Логарифмическая выпуклость мощностей слоев /г-значной n-мерной решетки 77
3.4. Расширительность пар слоев Е$ 80
Приложение 85
- Асимптотики сумм граничных функционалов
- Оценки сумм S{B) для регулярных семейств
- Расширительность пар слоев S% с малыми к
- Нижняя оценка числа антицепей в средних слоях множества Е%
Введение к работе
Значительное место в математике занимают перечислительные задачи, связанные с доказательством существования, алгоритмами построения и подсчетом числа элементов данного множества, обладающих некоторыми свойствами. Речь может идти, например, о числе решений задач целочисленного линейного программирования, числе ге-вершинных графов с определенными свойствами или о числе изомеров химических элементов. Существующие методы решения таких задач можно разделить на два типа: комбинаторные и вероятностные.
К комбинаторным методам относится классический метод производящих функций, получивший развитие в середине XX века. Использование перечислительных теорем Пойа, де Брёйна и Робинсона позволяет получать некоторые соотношения между числовыми характеристиками изучаемых объектов. Метод заключается в том, что на основании рекуррентных соотношений выводится дифференциальное уравнение, решением которого является производящая функция. Разложение производящей функции в ряд дает точные или асимптотические формулы для коэффициентов. Тем не менее, методика построения производящих функций сложна и не всегда приводит к обозримым результатам, поэтому существует класс задач, которые не могут быть решены с помощью классических методов.
Существенную роль играют комбинаторно - вероятностные методы решения перечислительных задач. В своих работах эти методы применяли Ю.Л. Васильев, В.В. Глаголев, В.Л. Гончаров, В.Ф. Колчин, А.А. Сапоженко, В.Н. Сачков, Н. Алон, Дж. Спенсер, П. Эрдёш. Идея вероятностного метода заключается в том, чтобы показать, что почти все объекты из рассматриваемого класса обладают некоторым свойством. Вероятностные формулировки комбинаторных задач дают возможность при отыскании асимптотических формул использовать аппарат предельных теорем.
Задачи, в которых речь идет о нахождении числа объектов, имеющих заданную границу или заданную мощность границы, естественно назвать перечислительными изопериметрическими задачами. Такими являются, например, задачи о числе монотонных булевых функций (так называемая проблема Дедекинда), независимых множеств в двудольных графах, булевых функций ранга ноль, двоичных кодов с расстоянием 2, пар подмножеств с расстоянием 2 в графах. Оказалось что, такие задачи сводятся к вычислению сумм специального вида, которые называются суммами граничных функционалов. Метод граничных функционалов разработан А.А. Сапоженко для решения перечислительных изопериметрических задач. Он сочетает в себе комбинаторный и вероятностный подходы и позволяет получать предельные распределения для случайных величин типа числа компонент связности. Сущность метода заключается в сведении исходной комбинаторной задачи к вычислению сумм граничных функционалов и дальнейшему аналитическому исследованию последних. Цель метода — получение оценки исходных сумм через "простейшие" суммы граничных
функционалов. Это позволяет уйти от перебора и громоздких конструкций, возникающих при чисто комбинаторном подходе.
К классу перечислительных изопериметрических задач относятся задачи о числе антицепей в частично упорядоченных множествах, а, значит, и задачи о числе конечнозначных монотонных функций. Наибольшую известность среди таких задач получила упоминавшаяся выше проблема Дедекинда о числе ф(п) монотонных булевых функций или, что то же, о числе антицепей в единичном те-мерном кубе Вп.
В 1897 г. Р. Дедекинд вычислил значение ф(4). Р. Черч в 1940 г. и М. Уорд в 1946 г. получили соответственно значения ^(5) и ф(6). В 1954 г. Б. Гильберт показал, что ф(п) удовлетворяет неравенствам
2(l«/2J) < ф(п) < nd""2j) + 2. В.К. Коробков в 1962 - 65 гг. показал, что ф(п) < 24'23d»/2j), Ж. Ансель в 1968 г. улучшил верхнюю оценку до З^"/2-!', а Д. Клейтмен в 1969 г. доказал, что
log2V(n)~ ([n;2j).
Асимптотическое решение проблемы Дедекинда было получено А.Д. Коршуновым в 1980 г. Оно основано на описании "типичных" монотонных булевых функций и оценках числа подмножеств вершин слоев единичного та-мерного куба, имеющих заданную мощность границы.
В 1989 г. А. А. Сапоженко получил асимптотику числа антицепей в унимодальных частично упорядоченных множествах, из которой вытекает и асимптотика для ф(п).
Проблема вычисления мощности множеств функций п переменных из замкнутых классов исследовалась и для fc-значных логик. В 1974 г. В.Б. Алексеев получил асимптотику логарифма числа fc-значных функций, монотонных относительно произвольно заданного частичного порядка на S. В целом же асимптотик числа монотонных функций й-значной логики при к > 2 практически нет.
Таким образом, актуальным является развитие методов решения перечислительных изопериметрических задач и метода граничных функционалов, в частности.
Краткое содержание диссертации
Модельной задачей, иллюстрирующей подход, связанный с методом граничных функционалов, является проблема нахождения числа независимых множеств в двудольных графах. Пусть дан двудольный граф Г = (X, Z; Е) с долями вершин X, Z и множеством ребер Е. Границей множества АС X называется множество
д(А) = {v Є Z : 3 и Є A {u,v} Є Е}.
Подмножество С вершин графа Г называется независимым, если подграф, порожденный множеством С, не содержит ребер. Функция f(A) — 2~\д(А" обладает следующими свойствами:
0 < /(Л) < 1 для всех АСХ;
f(A) — 1 тогда и только тогда, когда А = 0; 3)f(AUB)>f(A)f(B);
4) f(A U В) > f(A)f(B) тогда и только тогда, когда существуют и Є А и v Є В такие, что f({u,v}) > f{{u})f({v}).
Пусть /(Г) — число независимых множеств в графе Г. Тогда
/(Г) = 2"*" 2-"в<Л>1. (1)
В самом деле, произвольное независимое множество С в Г может быть представлено в виде С — A U В, где А = СПХ, В = С П Z. Если выбрано множество А С. X, то все подмножества В С Z \ д(А) и только они образуют вместе с А независимое множество в Г. Число таких подмножеств равно 2'2^д^'. Отсюда следует (1).
Из равенства (1) следует, что вопрос о числе независимых множеств сводится к вычислению сумм вида YIacx /(-^-)-
Функционал / : 2^ —> R, удовлетворяющий условиям 1-4, называется граничным. Пара / = (X, /) называется функциональной парой. Через
T(I) = T(X,f)= /(А),
обозначим полную сумму значений граничного функционала /, в дальнейшем для краткости будем говорить о суммах граничных функционалов. Граф Gi = (X; Е) с множеством ребер
Е = {{u,v} : /({«})/({«}) < /({u,t,})}
называется графом функциональной пары I = (X,f). Подмножество АСХ называется связным (относительно функционала f), если подграф графа G[, порожденный множеством А, связен. В случае описанной выше задачи о числе независимых множеств в двудольном графе Г множество АСХ связно относительно функционала /, если граф, порожденный множеством A U д(А), связен. Через Л = Л{1) обозначим семейство всех связных подмножеств множества X.
Если / = (X,f) — функциональная пара, v, j — натуральные, В С Л(1), то положим
«"(%) = (/И)Г> (2)
лев где В у] состоит из всех подмножеств, принадлежащих семейству В и имеющих мощность j.
Для подмножеств А, В С X скажем, что В является компонентой множества А, если В связно, но никакое D такое, что В С D С А не является связным. Для В С Л{1) обозначим через С(В) семейство подмножеств множества X, все компоненты которых принадлежат семейству В. Положим
s(B)= J2 f(B).
ВС{В)
Справедливо утверждение о том, что
S{B) < Т{1) = S(A(I)) < S{B)S{A{I) \ В).
Идея получения асимптотики сумм Т(1) заключается в том, чтобы найти семейство В С А(1), для которого выполняются следующие условия:
1) 5(Л(/)\В)~1;
2) существует простая асимптотическая формула, выражающая S(B) через суммы
вида (2), вычисление которых обычно не вызывает затруднений.
Назовем характеристикой функциональной пары / = (X, /) наименьшее целое Д такое, что выполнено условие
а\Л[л+1](1)) = о(1).
А.А. Сапоженко ([20], [23]) получил асимптотическую формулу для сумм граничных функционалов в случае, когда функциональные пары имеют характеристику Д < 2.
Функциональная пара / = (X, /) пара называется нерегулярной, если существуют подмножества Х\ С X и Xi С X такие, что для любых вершин и Є Х\ и v Є Х2 выполнено соотношение
ЯМ) = *(/({»})).
Целью данной работы является расширение области применения метода граничных функционалов на случай функциональных пар с характеристикой А > 3, а также на случай нерегулярных функциональных пар. Эта задача решается в главе 1. В главе 2 результаты первой главы применяются для получения асимптотики числа антицепей в частично упорядоченном множестве S%, являющемся декартовой степенью й-звезды при к < 11. Функциональные пары, порожденные парами слоев этого множества, имеют характеристику 3. В главе 3 рассматривается множество Е', являющееся декартовой степенью линейного частичного порядка мощности 3. Функциональные пары, порожденные парами слоев этого множества, являются нерегулярными. С использованием результатов первой главы получена нижняя оценка числа антицепей в Е%.
Во введении обоснована актуальность темы исследования, сформулирована цель диссертации, описана структура диссертации и перечислены основные результаты.
В главе 1 получена асимптотическая формула для вычисления сумм S{B) в случае, когда функциональная пара имеет характеристику 3 при условии, что для любых {и}, {г;} Є В выполнено /({и}) = f{{v}). Кроме того, определено расширение класса функциональных пар с характеристикой 2.
В главе используются результаты из работ [19], [20] и [23]. Результатом главы являются теоремы 1.4.3, 1.5.2 (см. ниже), дающие асимптотику сумм S(B) для функциональных пар с характеристиками 3 и 2 соответственно.
В параграфе 1.1 введены основные определения.
В параграфе 1.2 описан класс подмножеств множества X "типичных" для семейства В, и получены оценки сумм граничных функционалов S(B) через суммы граничных функционалов по типичным подмножествам. Типичным является множество, состоящее не более, чем из в компонент, где в = 0^(25)(1 + о(1)).
Пусть даны семейство В и множество В С X, тогда обозначим через 2 множество подсемейств {Ai,..., А„} семейства В, удовлетворяющих следующим условиям:
1) множество Н = (J Aj связно
2) множество В U Н связно.
В параграфе 1.3 получены оценки сумм вида
S(B) = /(Л)тг(А) (3)
через суммы вида (2).
Здесь
п(А)= П (l + f(B)y\ вєвМ
Суммы вида (3) являются обобщением сумм S(B). Для оценки исходных сумм достаточно получить асимптотическую формулу, позволяющую вычислять функционал 7Г. Дальнейшая задача состоит в оценке функционала ж для типичных множеств.
В параграфе 1.4 рассмотрен класс так называемых (Д, к, q, р)-ординарных функциональных пар и доказано, что такие функциональные пары имеют характеристику А.
Для функциональной пары / = (X,f), семейства А(1), вершины v Є X и натурального т положим
^М.т(7) = {ВеА:\В\<т,Ви {v} Є Л}.
Функциональная пара / = (-^/) называется (А, к, q, с)-ординарной, если
для всякого v Е. X выполнено f({v}) < 2~к,
\Х\ < 2(A+1)ft-2182K)
для любых А С X и v Є А
f(A)
4) для всякого v Є X и любого натурального числа т
Пусть / = (X, /) — функциональная пара, порожденная двудольным графом Г = (X, Z; Е), где X = В%, Z = 5+1 — соответственно fc-ый и (к + 1)-ый слои «.-мерного единичного куба, 0 < к < (п — 1)/2,
І? = {{и,v} : и Є X,v Є Zи < v}
и /(А) = 2~1а(л" для всех АС. X. Пара / = (X, /) является (2, п — fc, 1,2)-ординарной. В самом деле,
минимальная степень вершины v Є X в графе Г равна п — к;
\gn\ — (п\ < 23(n-fc)-21og^(n-fc).
границы любых двух вершин u,v Є. X имеют не более одной общей точки;
для любого т и любой вершины v Є X мощность ее окрестности порядка 2т не превосходит ((к + 1)(ге — к))т < (п — к)2т.
Если функциональная пара имеет характеристику 2, то значение функционала 7г для типичных множеств асимптотически равно 1, и, следовательно, значения сумм S(B) и S(B) асимптотически равны.
В пункте 1.4.3 получена асимптотическая формула, выражающая функционал тг через суммы вида (2) для функциональных пар с характеристикой 3 в случае регулярных семейств подмножеств. Семейство В называется регулярным, если
ЯМ) = /(W)
для всех {и}, {v} Є В. В результате получена асимптотика сумм S(B) для функциональных пар с характеристикой 3 и регулярных семейств В:
Теорема 1.4.3. Пусть І — (X,f) является (3, к, q, с) -ординарной функциональной парой, семейство В С As(I) является регулярным. Тогда
S(fi)=(l + 0(2-^"))exp{fr(B)},
MB) = сс\В) ~ \а\В) + \а\В) - а1(42)3])+«1(4]'2))-
В параграфе 1.5 введено обобщение понятия ординарности функциональных пар, и найдена их характеристика. Получена асимптотика сумм граничных функционалов для нерегулярных функциональных пар с характеристикой 2.
Теорема 1.5.2. Пусть I = (X,f) является (2,{кі,к2}^,с,р)-ординарной функциональной парой, В С Ас;(1). Тогда при достаточно больших к2
S(B) = (l + 0(2-11^)) ехрЫ*)},
1ъ{В) = а\В)-\с?(В)-а\ВЫ).
В главе 2 рассматривается задача о числе антицепей в частично упорядоченном множестве S%, диаграмма которого является декартовой степенью А;-звезды, т.е. дерева с к + 1 вершинами, одна из которых имеет степень к. В работе [20] получена формула, позволяющая вычислять асимптотику числа антицепей в так называемых унимодальных ранжированных множествах (точное определение см. в параграфе 2.1) и задача решена для 1 < к < 4.
В параграфе 2.1 введены основные определения. Двудольный граф G — (X, Z; Е) является ^-расширителем, если для всех А С X выполнено неравенство \А\ < (1 — #)|Э(Л)|. Для ранжированного т--слойного множества Р = (Р1?...,Рт) с порядком -< и числа j, 1 < j < 77г обозначим через Gj = (Pj, Pj+i; Ej) двудольный граф с долями вершин Pj и Pj+i и множеством ребер Ej = {{u,v} : и Є Pj,v Є Pj+i,u X г;}. Через Gj = (Pj,Pj-i;Ej) обозначим двудольный граф с долями вершин Pj и Pj-i и множеством ребер Ej = {{и,v} : и Є Pj,v Є Pj_i,v < и}. Множество Р является (Д, к, q, р, г)-квазиунимо дальним, если графы Gj являются (/г)-расширителями при О < І < т — 1, графы Gj являются (У(Ас)-расширителями при г +1 < j < п, а функциональные пары, порожденные этими графами, являются (Д, и, q, 4р)-ординарными. Множество Р является (А,к^,р,г)-унимодальным, если оно является (Д,гс,q,p,г)-квазиунимодальным, и, кроме того, выполнены следующие условия:
max aoAv) < тіште Ы) при 0 < j < г — 1, а также (4)
max o-q\v) < min erg. (ад) при г + 1 < j' < n, (5)
где
Из работ [20], [23] следует, задача о числе антицепей в (Д, к, д,р, г)-унимодальном множестве сводится к задаче о числе антицепей в множестве (РТ-і, Рт, P+i)-
Пусть к — натуральное число, рассмотрим множество Sk = {—1,0,1,... ,к — 1} и зададим на нем отношение частичного порядка ^ следующим образом: — 1 ^ і при і = 0,1,... , к — 1. В параграфе 2.2 доказана унимодальность множества 5. Положим - = {« = («!.., ап) Є S : E?=i он = О-
Теорема 2.2.3. Пусть п = (к + 1)т + і для некоторых целых т и і, 0 < і < к. Положим A = --Hog2(fc + 1) — 1. Тогда при достаточно больших т и 0 < г < fc — 1 множество S% является (А, те — m + 1,1,2, т,т)-унимодальным. При г = к множество S% является (А,п — т, 1, 2, т,т + 1)-унимодальным.
Обозначим через i>(S%) число антицепей в 5.
Теорема 2.2.4. Пусть п — (к + 1)пг + г (?л# некоторых целых т и г, 0 < і < к. Положим A = -Mog2(fc + 1)-1. Тогда при достаточно большихт иО < і < к — 1
tf(S?) = (l + 0(2-^-))^(5^^ и Sm U S?im+1). Яри достаточно больших т и і = к
4>{SZ) = (і + 0{2-^п)) fow^ U Sm U Sm+1) +
Множество (5'^_1,5'^,5^+1) порождает функциональную пару In = (Xn,fn), где Хп = 5^_1и5^+1,дляЛСХп
9(A) = {В С S : Vv Є 5 3 Є Л (и < v) V (и ^ и)},
fn{A) = 2_'9^^'. В параграфе 2.3 доказано, что при 5 < к < 11 функциональные пары 1п = (Хп, fn) являются регулярными и (3,ге — га, 2,3)-ординарными. С использованием результатов главы 1 доказана
Теорема 2.3.3. Пусть 5 < к < 11, п достаточно велико и п = (fc + l)m + г Лі.я некоторых т, і, 0 < і < k, 1п = (Хп, /„) — функциональная пара, порождаемая множеством (Sto_i,.%, «^m+i)- Тогда
^(Sfc")~2U)fcn-mexp{/23},
дз=дз(л(/п)) = 41)д - ^1),z+^ - 42)д+41іа)д.
В приложении суммы «^ вычислены через параметры множества S%.
В главе 3 рассматривается частично упорядоченное множество Е%, являющееся декартовой степенью линейного порядка мощности 3. Как и в предыдущей главе, здесь ставится задача о числе антицепей в данном множестве.
Пусть к — натуральное число, рассмотрим множество Е^ = {О,1,... ,к — 1} и зададим на нем отношение частичного порядка < следующим образом: і < г + 1 при і — 0,1,... ,к — 2. Положим F(n,i,k) = {а = («і ... ,ап) Є Е% : 2=1 at = г}, N(n,i,k) = \F{n,i,k)\.
Обозначим через ф(Е$) число антицепей в множестве Eg. Из работы В.Б. Алексеева следует [1], что
bg2V(3n)~ ?^(1 + о(1)).
В параграфе 3.1 получена асимптотика мощностей центральных слоев Е%.
Теорема 3.1.1. При достаточно достаточно больших п справедливы равенства
3«+i/2 , 15
tf(„,»-l,3) = fWl--- + o(i))
2у/ігп V 16те \nj J
N(n,n,3) = ^L(l -^ + o(l)). 2 Jim \ Іоте \nj J
В параграфе 3.2 рассмотрены функциональные пары, порождаемые тремя центральными слоями Е%- Трехслойное множество (F(n,n —1,3), F(ra, те, 3), F(n,n + 1,3)) порождает функциональную пару 1п — (Хп, /п), где Хп — F(n,n — l,3)UF(n,ni-l,3), для АС Хп
д{А) = {В С F(n, те, 3) : Vv Є В Зи Є A ( < v) V (v < те)},
/п(Л) = 2_'э'л^'. Эти функциональные пары являются нерегулярными, показано, что они имеют характеристику 2. С использованием результатов главы 1 получена асимптотика сумм значений граничных функционалов по множествам малой мощности.
Теорема 3.2.1. Пусть {In = (Xn,fn)} — последовательность функциональных пар, порожденных соответственно множествами (F(n,n — 1,3), F(n,n,3), F(n,n + 1,3)). Тогда при те -> оо
S(As(Q) ~ exPW> где
L(n-1)/2J
Из теорем 2.2.3, 3.2.1 и [21], [23] следует
L(n-1)/2J / \ / _ \
Ъ = Е (J) (п "2/_ J2^ [2 + 2-(^)(Зте2 - 7nj + ll|j2 + 10|j + п - 2)].
Теорема 3.2.2. При достаточно больших те
гс?е /х~ определено в предыдущей теореме.
Таким образом, улучшена известная нижняя оценка ф(Е).
Замечание. Можно убедиться в том, что
[їґ2у/2 + 1\п
М=))
где с « 1.95.
В работе Н.Н. Катериночкиной оценивалась величина 5{i,n,k) = N(n,i + l,fe) — N(n,i,k). В параграфе 3.3 доказана логарифмическая выпуклость мощностей слоев
множества Ец.
Теорема 3.3.1. При любых k>2,n>2u2
N(n,i-2,k) N(n,i-l,k) N(n,i- l,fc) - N(n,i,k)
В параграфе 3.4 доказана (3, [п/2\, 1,2, п, ге)-квазиунимодальность множества Eg , а также унимодальность частично упорядоченных множеств, состоящих из 2и/3 первых или из 2те/3 последних слоев Eg . Это позволяет свести задачу о числе антицепей в Eg к аналогичной задаче в множестве, состоящем из 2та/3 центральных слоев Eg.
Теорема 3.4.3. Положим Eg}i = F(n,i,3), t = [2(n - 1)/3J, к = п- [t/2\. При
достаточно больших п множества (Egfi, Egx,..., Egt) и (Eg2n-t-> > Щ2П-11 Eg 2«) являются (2, к, 1,2, t, t)-унимодальными.
Функциональная пара / = (X, /) называется А-сходящейся, если выполнено
a\A{j](I)) = о(1).
Если для квазиунимодального множества выполнены условия (4), (5), то функциональные пары, порожденные парами его соседних слоев, автоматически являются Д-сходящимися.
Для получения асимптотики числа антицепей в Eg достаточно показать, что функциональные пары, порожденные парами соседних слоев множества Eg, являются А-сходящимися для некоторого А.
В таком случае асимптотика числа антицепей совпадает с нижней оценкой.
Основные результаты диссертации
Для функциональных пар с характеристикой 3 получена асимптотическая формула для вычисления сумм граничных функционалов по регулярным семействам подмножеств.
Получена асимптотическая формула для вычисления сумм граничных функционалов в случае нерегулярных функциональных пар с характеристикой 2.
Получена асимптотика числа антицепей в множестве S% при к < 11.
Получена оценка отношения мощностей соседних слоев множества Eg.
Доказана логарифмическая выпуклость мощностей слоев множества Е%.
Получена нижняя оценка числа антицепей в множестве Eg.
Асимптотики сумм граничных функционалов
В статье А.А. Сапоженко [21] было введено понятие ап-ограниченной последовательности. Сумма такой последовательности приближается суммой ее "типичных" членов. При этом случайные величины, связанные с типичными членами последовательности имеют в пределе при п —У оо распределение Пуассона или нормальное распределение. Пусть даны последовательность функциональных пар {1п — (Хп, fn)} :=l и последовательность семейств {Вп С Л(Іп)} =і- В данном параграфе доказано, что последовательность сумм {S(Bn)} =l, являющихся обобщением сумм S(Bn), является а1 (Бп)-ограниченной. Последовательность {o n,j} j=o называется ап ограниченной, если при любом j выполняется неравенство 1B дальнейшем для краткости (/(-А)) = /"(А). Для «„-ограниченных последовательностей справедливы следующие утверждения: Теорема 1.2.1.[21] Пусть последовательность {&n,j}j=o является ап-ограни-ченной и Km шп где lim єп = 0. Яри этом єп — 0(е Шп ), если шп -у/а ,, и еп — 0(ш 1е Шп 2), если Следствие 1.2.1. Пусть выполнены условия теоремы 1.2.1 и шп — оЦс )1/6). Тогда при п — Теорема 1.2.2.[21] Пусть последовательность {O „,J}J=Q является ап-огра- ниченной и lim u;n = оо. Положим вп = ап + и пЛ/і пі "n = X) щ , „; = при всех B,D С X. Для функциональной пары / = (X, /) и семейства В С Л(1) положим В параграфе 1.3 введен функционал 7Г, удовлетворяющий условию (1.2.1), а также получены асимптотические формулы, выражающие суммы S(B) через суммы вида а?(В). В дальнейшем для нахождения асимптотики сумм S(B) необходимо получить оценку функционала 7г. Теорема 1.2.3 дает возможность при оценке к(В) ограничиться рассмотрением только тех множеств В, у которых количество компонент мало отличается от а1 (В). При выполнении некоторых условий это позволяет получить асимптотические формулы для сумм граничным функционалов, имеющих характеристику 3 (см. параграф 1.4). Если В С 2х, В Є X, то положим Лемма 1.2.1. Пусть даны функциональная пара I = (X, /) и функционал п. Тогда для любого семейства В С Л(1) и целого числа к 0 выполнено Доказательство.
Правая часть равенства (1.2.2) равна сумме произведений f{B)f(D)-K(B U D) по всем упорядоченным парам (B,D) таким, что В Є Ск(В), D Є Вд. Для каждой такой пары множество А — В U D принадлежит семейству Ck+i(B). При этом f(A)n(A) = f(B U D)ir(B U D) = f{B)f(D)n(B U D). Таким образом, каждая пара (B,D) определяет множество А Є Ck+i(B), причем каждое множество А порождается к + 1 раз. Отсюда следует (1.2.2). Пусть / = (X, /) — функциональная пара, А С X, Я С 2х. Через w{A) обозначим число компонент множества А, принадлежащих семейству Af. Если к натуральное, В С Л(1), то положим Пусть О, j — натуральные, Af, А4С2Х,АЇПА4 = 0) тогда положим Лемма 1.2.2. Пусть І = (X,f) — функциональная пара, функционал ж удовлетворяет условию (1.2.1), В\ С В С Л(/), «і = ск1(Б1) достаточно велико, Af С 2 , Л/" П #i = 0, # — натуральное число. Положим (1.2.2) получаем Отсюда следует (1.2.3). Теорема 1.2.3. Пусть I = (X,f) — функциональная пара, функционал ж удовлетворяет условию (1.2.1), Bi С В С Л(1), I — натуральное число. Пусть также В - (J Bt, ВІП Bj = 0 для всех і ф j, i t i и at = al(Bt) достаточно велики. Положим 6t — at + oct , Доказательство. Из леммы 1.2.2 следует, что для каждого t, 0 t I, последовательность является « -ограниченной. Теперь утверждение вытекает из следствия 1.2.1. Следствие 1.2.2. Пусть I = (X,f) — функциональная пара, В\ С В С .4(/), I — натуральное число. Пусть также В= [J Bt, Bif\Bj = для всех іфі, \ t i и at — al{Bt) достаточно велики. Положим 9t = at-\-at , Доказательство. Заметим, что по определению Функционал 7г(5) = 1, очевидно, удовлетворяет условию (1.2.1). 1.3 Отношения между суммами граничных функционалов В этом параграфе введен функционал специального вида 7Г и получены асимптотические формулы для сумм S(B) (теоремы 1.3.3, 1.3.4) в тех случаях, когда выполнены условия типа Для дальнейшей оценки сумм S(B) необходимо получить асимптотику функционала 7Г. Отметим, что значение функционала 7Г асимптотически равно 1, если выполнены условия теоремы 1.3.3, тем самым, задача об оценке сумм S(B) окончательно решена для функционалов с характеристикой 2. В параграфе 1.4 получена оценка 7г для функционалов с характеристикой Нам понадобятся обобщения введенных ранее сумм на случай семейств подмножеств. Пусть / = (X,f) — функциональная пара, введем понятие семейства ранга г над X. Произвольное подмножество А С X называется семейством ранга 1. Если Лі,. .., As — различные семейства ранга г, то F = {Ai,..., As} называется семейством ранга г + 1. Семейства Ai,... ,AS называются элементами семейства F. Множество всех семейств ранга г над X обозначается через Для произвольного семейства F ранга г по индукции определены величины \F\ — мощность семейства F, \\F\\ — мулътимощность семейства F, f(F) — значение функционала на семействе F и множество (F) — основа семейства F. Если F — семейство ранга 1, т.е. F С X, то F = \F\, где F — число элементов множества F, f(F) определяется функциональной парой / = (X,f), a (F) — F. Пусть для некоторого г 1 эти величины и множество определены, и пусть F — {Лі,... , As} — семейство ранга г + 1. Тогда Введем понятие связного семейства ранга г. Пусть I = (X, /) — функциональная пара. Для семейств ранга 1 связность определена ранее. Семейство F = {Лі,..., Л„} ранга г 1 называется связным, если каждое из АІ, г = 1,... , в, является связным семейством ранга г — 1 и (F) Є .4.(/). Множество всех связных семейств ранга г обозначается через Л (1). По определению Л 1\і) = Л(1).
Для произвольного подсемейства В С Л(/) определено семейство В связных подмножеств ранга г, порожденное множеством В. Положим В 1) = В. Если JB "1) определено, то Подсемейство В семейства F ранга г называется компонентой связности семейства F (обозначение В h F), если В Є Л (1) и (В) — компонента связности множества (F). Через n(F), как и раньпіе, обозначается число компонент связности семейства F. Пусть / = (X,f), В С Л (1). По аналогии со случаем г = 1 полагаем Далее доказываются некоторые соотношения между суммами граничных функционалов разных типов. Лемма 1.3.1.[23] Для любой функциональной пары I = (X,f), любого натурального г и любого В С Л (1) справедливо неравенство Пусть V = В{г 1\ через ТУ обозначим семейство Теорема 4.1 из статьи [23] легко переносится на случай семейства ранга г 1: Теорема 1.3.1. Пусть функциональная пара I = (X,f), натуральное г и подсемейство В С Л Т (1) таковы, что для некоторых положительных чисел ф и 6 выполняются неравенства Лемма доказана. Следствие 1.3.1. Пусть для функциональной пары I = (X,f), подсемейства В С Л{1) и положительных чисел ф, S выполнены неравенства (1.3.2) и (1.3.3). Тогда expja1 ) - 2ф - j В {В) ехр{ах(В)}. (1.3.10) Доказательство. Утверждение следует из теоремы 1.3.1 с г — 1 и того, что S(B)exp{-a1(B )} Теорема 1.3.3. Пусть даны функциональная пара I = (X,}), семейство В С Л(1) и натуральное число I. Кроме того, пусть В = (J Bt) В{ C)Bj — 0 для всех і ф j, i t i и at — а1(6() достаточно велики. Положим 9t = ctt + ctt , Пусть также для положительных чисел А и С, выполняются неравенства (1.3.5), (1.3.6) и для некоторых положительных j и р выполнено Теорема 1.3.4. Пусть даны функциональная пара I = (X,f) и подсемейство В С Л{1). Пусть также а1 (В) достаточно велико, для положительных А и( выполняются неравенства (1.3.5), (1.3.6) и для положительного выполнено Доказательство. С использованием неравенства In (1+ж) х — ж2/2+ж3/3 — ж4/4 при х О и условия (1.3.20) получаем С другой стороны, из неравенства х — х2/2 + ж3/3 In (1 + х) при х 0 следует, что Из (1.3.22), (1.3.23) и теоремы 1.3.2 вытекает (1.3.21). 1.4 Оценки сумм S(B) для ординарных функциональных пар В [23] определен класс так называемых ординарных функциональных пар, для которых условия теорем 1.3.1 - 1.3.4 выполняются автоматически, и с использованием аналога теоремы 1.3.3 получены асимптотические формулы для сумм S(B) в случае (2, /, 5, с)-ординарных функциональных пар. В данном параграфе получены асимптотические формулы для сумм S(B) (теорема 1.4.1), а также оценки функционала 7г (теорема 1.4.2, лемма 1.4.13) в случае регулярных (3, к, д, с)-ординарных функциональных пар. Результатом является асимптотика сумм S(B) (теорема 1.4.3). Пусть / = (X, /) — функциональная пара, В С X, т 0 целое, положим
Оценки сумм S{B) для регулярных семейств
Здесь рассматриваются так называемые регулярные семейства связных множеств. Получена асимптотическая формула для функционала к (В) в случае, когда множество В состоит из компонент мощности 1, находящихся на достаточно большом растоянии друг от друга. Пусть / = (X, /) — функциональная пара, семейство В С Л(1) назовем регулярным, если для любых {и}, {v} Є В выполняются равенства вма) = {{W,{W,M}} : W є в, {{и}, Ы} є в$іМ}. Замечание 1.4.1. Из доказательства теоремы 1.4.1 ясно, что при а1 (В) 2lS2K выполнены условия теоремы 1.3.1 с г = 1, S = 2 K+log2 к+9 и ф = 2кс2 к+1б2 г, следовательно, поэтому везде далее считаем, что Лемма 1.4.13. Пусть I = (X, /) является (3, к, q, с)-ординарной функциональной парой, В С Л (1) является регулярным семейством. Положим а — a1 d(fi 1 1 ); в = а + а9/14, г = (а - а9/14)(1 - 2- Доказательство. Покажем сначала, что при В Є Cte]{B i$ ) Оценим а сверху. Из включения В С Л (1) следует, что Поскольку В Є 0 (8 ! ), множество В состоит из d-компонент мощности 1, и г 1- 1 0- Из определения г и 0 следует, что существует , Є [—1,1], такое, что Отсюда и из (1-4.7) при m = l, r = 2ii/=l получаем Отсюда и из (1.4.37) следует (1.4.36). Докажем теперь утверждение леммы. По формуле включений-исключений имеем Пусть Н Є Вв 2, это значит, что существует вершина v Є В такая, что H#{v}. Если множество 5 удовлетворяет условию леммы, то оно состоит из компонент мощности 1, расстояние между которыми не меньше d, тогда при d 4 для любой вершины и Є В, отличной от г , выполнено Н {ТІ}. Следовательно, B,v\ ,2] I"1 {u} [2] ==0)11 все слагаемые, кроме первого, равняются нулю. Теперь из регулярности семейства В для произвольного {vo} Є В получаем Оценим первое слагаемое. Из регулярности В и определения BrJ } следует, что Из (1.4.36), (1.4.40) - (1.4.42) следует утверждение леммы. Теорема 1.4.3. Пусть I = (X,f) является (3, к, q, с) -ординарной функциональной парой, семейство В С Л-$(1) является регулярным. Тогда Утверждение вытекает из леммы 1.4.4 при Д = 3 и п(В) = 1 и из (1.4.43). Пусть / = (X,f) — функциональная пара, семейства В С А(1) и Т С .4(/), Б П 2? = 0, назовем сильно регулярными, если они являются регулярными, для любых {w},{v} Є $ выполняется (S U Х )V г [2]1 — 1( U Т )\и} [2]1 и Для любых {и}, Ы Є Р выполняется (В U V)$m\ = \(В U P)fJ},[2]l- Лемма 1.4.14. Пусть I = (X,f) является (3, к, q, с)-ординарной функциональной парой, семейства В,Т С Д- (І) являются сильно регулярными. Положим Доказательство. Доказательство утверждения аналогично доказательству леммы 1.4.13. Заметим, что Положим В = BX\JB2, где Вг Є С ] (# ?, ! ), В2 С Л](Р Й ). Аналогично (1.4.40) и (1.4.42) из сильной регулярности В и Т для произвольных {VQ} Є і?, {адо} Т следует Лемма доказана. Теорема 1.4.4. Пусть I = (X,f) является (3, к, /, с)-ординарной функциональной парой, семейства В С А$(1) и Т С .4 (/) являются сильно регулярными.
Тогда Доказательство. Поскольку семейства В и V являются сильной регулярными, условие (1.4.27) выполнено для а14(В 1 .), (D fly). Лемму 1.4.9 можно применить дважды. Теперь утверждение вытекает из следствия 1.4.2, теоремы 1.4.2 и леммы 1.4.14. Следствие 1.4.5. Пусть I — (X,f) является (3,к,q,с)-ординарной функциональной парой, г0 — \K,/(2q)], семейства В С Лр0(/) и Т С А 0(1) являются сильно регулярными. Положим В = В П Утверждение вытекает из следствия 1.4.4 и теоремы 1.4.4. 1.5 Оценки сумм S(В) для нерегулярных функциональных пар В данном параграфе рассматривается обобщение понятия (Д,к,д,с)-ординарности на нерегулярные функциональные пары. В результате получены оценки S(B) для граничных функционалов с характеристикой 2 (теоремы 1.5.1, 1.5.3). Функциональную пару / = (X,f) назовем (А,{кі,к2},д,с,р)-ординарной3, если к2 «і, log2 «і = 3В дальнейшем считаем, что к2 достаточно велико. Если какие-либо из неравенств (1.5.1) - (1.5.6) могут не выполняться для функциональной пары / = (X,/), то будем, как и раньше, ставить прочерки в соответствующих координатах. Следующие утверждения устанавливают связь между понятиями (Д,к, -ординарности и (Д, {к!,к2},д, с,р)-ординарности. Замечание 1.5.1. Из определения следует, что (Д, {—,к2}, 7 с, —)-ординарная функциональная пара является (Ді,к2,д,с)-ординарной, где Ді таково, что Лемма 1.5.1. Пусть I — (X,f) является (Д, {к,і,К2}-,Ц,с-,р)-ординарной функциональной парой, X — Х\ U Х2. Тогда функциональная пара Д = (X\,f) является (Д, «i,g, с)-ординарной, а функциональная пара /2 = (Х2,/) является (Д,к2,?,с)-ординарной.
Утверждение следует из определений. Следующие утверждения аналогичны утверждениям, сформулированным в [23] для (Д, к, д, с)-ординарных функциональных пар. Лемма 1.5.2. Пусть I = (X,/) является ( — ,{кі,к2},д, с,р)-ординарной функциональной парой, В Следствие 1.5.1. Пусть I = (X,/) является (Д,{кі,к2},д,с,р)-ординарной функциональной парой, и, г, j — произвольные фиксированные натуральные числа, В С А {1), т [«2/(2?)], к 2 достаточно велико. Тогда Доказательство. Верхняя оценка вытекает из (1.3.1) и леммы 1.5.3. Для доказательства нижней оценки воспользуемся теоремой 1.3.1. Покажем, что условия (1.3.2) и (1.3.3) выполнены при г = 1, ф = 2-18 1 и S = 2-215 1. Тогда утверждение будет следовать из (1.3.4). Пусть В = Ai(I), в силу (1.5.9) (1.5.10) с v = 1, г = 2 и jo — log2 к2 имеем при достаточно больших к2 Покажем, что условие (1.3.11) выполнено для 7 = 2 ї1І2К2. Пусть оі = о1 (Bi) и а2 = о1 (В2). Положим = oi + Oi/14 и ?2 = а2 + о2/14. Для 5 Є ( (##i) ПС?2 (ЯВ2) положим В — BiU В2, где ?і Є С(#0? a, В2 Є С(?2). Оценим Oi сверху. Поскольку в силу леммы 1.5.1 функциональная пара 1\ — (Лі,/) является (2, «i, q, с)-ординарной, то из (1.4.1) - (1.4.5) имеем Из включения В Є С (# Ві) П С (В]Вг) следует, что Вх состоит не более, чем из 6 і компонент, а В2 состоит не более, чем из 62 компонент. Поскольку каждая компонента принадлежит семейству Л (1), она содержит не более двух элементов, следовательно #!І 20! и \В2\ 292. Если а; 1 для і Є {1,2}, то ві 2 и ?j 4«». Тогда из (1.5.17) следует, что При достаточно больших к2 из (1.5.15) - (1.5.18) вытекает (1.3.11) с j = 2 2 4. Если а; 1 для какого-нибудь г, то В І 2 и \ВІ\ 4, тогда выполнение условия (1.3.11) с 7 = 2 11 К2 также вытекает из (1.5.17), (1.5.18). Докажем выполнение условия (1.3.6) при = 2- 2 К2. В силу (1.5.9), (1.5.10) с v = 2, г = 2 и jo = Отсюда вытекает (1.3.6) с ( = 2 2_К2. Докажем выполнение условия (1.3.12) при р — 2_ log2K2. д3 (1.5.1) - (1.5.4) и (1.5.6) ст=1 имеем аналогично (1.5.15), (1.5.16) Отсюда следует (1.3.12) с ip = 2 2loS2K2. Таким образом, условия теоремы 1.3.3 выполнены при указанных значениях параметров А, С, 7 и if. Теперь из (1.3.13), (1.5.14) и (1.5.18) - (1.5.20) вытекает (1.5.12), значит, утверждение доказано при условии (1.5.13). Пусть теперь следовательно, Покажем, что выполнены условия теоремы 1.3.1 при г = 1 и соответствующих ф и S. Тогда (1.5.12) будет следовать из (1.3.4). Проверим выполнение условия (1.3.2). В силу (1.5.3) и (1.5.21) при достаточно больших к2 имеем
Расширительность пар слоев S% с малыми к
Множество Lt(p) состоит из наборов, в которых значения первых р координат отличны от нуля. Нетрудно видеть, что іаді = (")( -1)я- . (2-2.22) Лемма 2.2.10. Пусть А С St, 0 t п - 1 и \А\ ()(fc - 1)п_ . Тогда Доказательство. Положим В = LA. В силу теоремы 2.2.2 имеем Поскольку \В\ ()(Jfe - 1)п \ то из (2.2.22) получаем Заметим, что rt+i(/5) = п — t для всякого $ из В, л т{(7) = ( + 1)(& — 1) для всякого -у из Tt+i(B). Число ребер Е(В) в двудольном графе (B,Tt+i(B)) удовлетворяет соотношениям Отсюда с учетом (2.2.24) получаем (2.2.23). Следствие 2.2.3. Пусть А С St, t п-1 и тв+1(А) ( )( - l)r_1. Тогда выполнено неравенство (2.2.23). Доказательство. Покажем, что Л (")(& — l)n. Утверждение будет вытекать из леммы 2.2.10. Предположим, что Л (")(& — I)"- . Пусть В = LA, тогда существует набор (3 из S \ Lt(n) такой, что Отсюда при t п — 1 получаем что противоречит условию. Лемма 2.2.11. Пусть t (те — /е)/(/г + 1) и Ft — (X, Z; Е) — двудольный граф с долями вершин X = S%t, Z = S%t+1 и множеством ребер Ё = {{aj} :aeXjeZ а X /3}. Пусть At — наименьшее число такое, что Тогда при достаточно больших п граф Г4 является полным (At, п — t, 1, -расширителем. Доказательство. Положим к = п — i, Si = к-1 logj к, #2 = -2 log2 «5 Зі = K3log27/t, Єї = gi/\Z\. Пусть Л С X = 5t. Проверим выполнение условий (2.1.1) - (2.1.5). Выполнение условия (2.1.1) следует из того, что степень любой вершины /З Є X равна те — t. Степень любой вершины а Є Z равна k(t + 1), кроме того, из условия следует, что поэтому выполнены условия (2.1.2) с р = 1 и (2.1.4). Условие (2.1.3) выполнено при д = 1, поскольку для любых а,$ Є X выполнение условия (2.1.5) следует из (2.2.25). При достаточно больших те имеем д\ L?J(fc — 1)п -1. Из следствия 2.2.3 вытекает, что для всякого АС. X такого, что rt+1(A) д выполнено неравенство Отсюда вытекает, что граф 1\ является граничным (єі,$і)-расширителем. В силу (2.2.26) выполнены условия леммы 2.2.2, следовательно, для всякого А С. X имеем Это означает, что граф Ft является простым (1, 2)-расширителем. Лемма доказана. Лемма 2.2.12. Пусть п достаточно велико и таково, что для некоторого целого т выполнено п = Доказательство. Из определения Lm(p) следует, что (2.2.28) эквивалентно следующему неравенству: \rm(Cn ([k/2\))\ \Slm\. Из (2.2.7) следует, что для любых к, п и т,р п выполнено При достаточно больших п и т = (п — к)/(к + 1) выполнено Теперь из (2.2.30) и (2.2.31) следует утверждение леммы.
Лемма 2.2.13. Пусть п = (к + 1)га + fc и Гга = (X, Z; .Є) — двудольный граф с долями вершин X Тогда граф Гт является (Дш,те — т, 1,1)-полурасширителем, где Дт = [ ±ilog3(fc +1)]- Доказательство. Положим к — п — т = k(n + l)/(fc + 1), Sx = /c_1log2 к, S2 = Av-Mog , 9l - следовательно, Из теоремы 2.2.2 и (2.2.32) вытекает, что В С Lm(p). Пусть абВ, тогда ни одна из первых р координат набора а не равна нулю. Это же свойство сохраняется у всех наборов из множества тт(В), поэтому Рассмотрим двудольный граф (В,тт(В)). Заметим, что rm+i(a) = к. Для /З Є тт+\(В) рассмотрим два случая. 2) В остальных случаях тто(/3) П В\ к. Положим где г-е слагаемое равно числу ребер, идущих из верпіинн /З Є rm+1(B) в множество тт((3)\В, причем среди первых р координат набора /3 ровно г имеют значение —1, а значение (р + 1)-ой координаты отлично от нуля. С использованием леммы 2.2.8 получим, что «---Ш"»-7)( Г- » Покажем, что при р [к/2\ 6Ф(р) rm+i(B). (2.2.38) Имеем при тп — (п — к)/(к + 1) Теперь из (2.2.34), (2.2.39), (2.2.40) и (2.2.37) вытекает (2.2.38). Отсюда и из (2.2.35) получаем, что при р [к/2\ Поскольку (2.2.27) справедливо и для га = (п — к)/(к + 1), то граф Гто является граничным (єі, 5і)-расширителем. Выполнение условий (2.1.1), (2.1.2) при р = 1 и (2.1.4) следует из того, что степень каждой вершины $ Є -X" U Z равна к = Проверим выполнение условия (2.1.5). Из (2.2.21) следует, что при Am=[ log2(fc +1)1-1 Следовательно, граф Г является (Дт,те — га, 1,1)-полурасширителем. Лемма доказана. 2.2.3 Доказательство основного результата Теорема 2.2.3. Пусть те = [к + 1)га + і для некоторых целых т и і, 0 і к. Положим Д = plog2(fc + 1) — 1- Тогда при достаточно больших т и 0 і к — 1 множество Sk является (А,те — га + 1,1,2, т,т)-унимодалъным. При і = к множество Sk является (Д, те — га, 1, 2, га, га + 1)-унимодальным. Доказательство. Положим к; = [&(те + 1)/(к + 1)]. При t (те — к)/(к + 1) степень вершины (З Є Skt в графе Tt равна те — /г. При і (те + l)/(fc + 1) степень вершины (З Є X = 5 t в графе Г" равна & к. Степень вершины (З Є S%t в 5 равна п + t(k — 1) 2к к2. Выполнение условия (2.1.5) следует из леммы 2.2.1, (2.1.6) и (2.2.21).
В силу леммы 2.2.4 при каждом t (те + 1)/(& + 1) граф Г" является полным (Д4, Ы, 1,1)-расширителем. Таким образом, множество (Skn, . , Sk г,п+1у,к+1 ) является полным (Д, к, 1, 2)-расширителем. В силу леммы 2.2.11 при каждом t (те — к)/(к + 1) граф Гг является полным (Д(,те —і, 1,1)-расширителем. Таким образом, множество (Sk0,. . ., Sk і,п_ку/к+1\ ) является полным (Д, к, 1,2)-расширителем. В силу лемм 2.2.9 и 2.2.13 при те = (к + 1)га + к графы Г и Гт являются (Дто,к, 1,1)-полурасширителями, поскольку Дто = Дш+і- Из сказанного вытекает утверждение. Обозначим через i (Sk) число антицепей в множестве Sk . Из теоремы 2.1.1 следует Теорема 2.2.4. Пусть те = (к + 1)га + і для некоторых целых т и і, 0 і к. Положим Д = ±1 log2(& + 1)-1. Тогда при достаточно больших т иО г к — 1 2.3 Асимптотика числа антицепей в SjJ В параграфе показано, что функциональные пары, порожденные тройками соседних центральных слоев 5 являются (3, к, q, с)-ординарными при подходящих re, q и с (лемма 2.3.1). С помощью теоремы 1.4.3 получена асимптотика числа антицепей (теорема 2.3.2). Обозначим через Г" = [Xt, Zt;Et) двудольный граф с долями вершин Xt ж Zt, где Xt — Sjt_l U St+1, Zt = S%t 1 t n — 1и множеством ребер Et = {{aj} : а Є XtJ Є Zt a f3 или 0 a}. Для А С Xt полагаем и ft{A) = 2- . Обозначим через /tn функциональную пару (Xt,ft), порожденную графом r? = a Лемма 2.3.1. Пусть п — m{k+l)-\-i для некоторых целых т ui, О і к. Пусть т достаточно велико, Д = - log2(A; + 1) —1, к = [fc(n+l)/(fc+l)]. Тогда если О г к — 1, то функциональная пара 1 — (Xm,fm) является (А,к,2,3) ординарной. Если і = к, то функциональные пары 1 — (- raj/m) " - m+i — (,Xm-\-i, /rn+i) являются (Д, к, 2,3) -ординарными. Доказательство. Убедимся сначала в выполнении условия (1.4.2). Это следует из того, что при 0 і к — 1 минимальная степень вершины (З Є Хт в графе Г равна (кп + к + i_+ 1)/ {к + 1), а при і = к минимальная степень вершин /З Є Хт в графе Г и а Є - m+i в графе Г +1 равна &(те + 1)/(к + 1), а также из того, что по определению ft{{(3}) = 2-ЗГ( »1. Проверим выполнение условия (1.4.1). Из (2.2.21) следует, что і о» I 9(1 1) bg2(fc+l) При достаточно больших те и (те — к)/(к + 1) t (те + 1)/(к + 1) из леммы 2.2.1 имеем у\_сп 1-і-К" I 9 . 9( +1) (fc+i) Положим Д = [ ±1log2(fc + 1)]-1, re = "/г(те + 1)/(/г + 1)]. Тогда при t Є {m,m + l} имеем \Xt\ 2 2 +1)1 1) 2(A+1)re-2lsi«_ (2.3.1) Из (2.3.1) при достаточно больших те вытекает справедливость (1.4.1). Убедимся в справедливости условия (1.4.3) при q = 2. Заметим, что в графе Г" = (Xt, Zt] Et) для любых двух вершин а,$ Є Xt справедливо
Нижняя оценка числа антицепей в средних слоях множества Е%
В этом параграфе доказана (2, {к!,К2},?,с,р)-ординарность функциональной пары /„, порожденной тремя центральными слоями трехзначной те-мерной решетки Е% (лемма 3.2.1). Это позволяет воспользоваться теоремой 1.5.2 и получить асимптотику сумм S(A${In)) (теорема 3.2.1). Набор a = (ai,...,an) Є #3 не превосходит набор /3 — (/Зі,. .., (Зп) Є Е% (т.е. а /3) тогда и только тогда, когда оц / для всех г, 1 г те. Следовательно, Е% является частично упорядоченным множеством. Наборы а,/3 Є Е% называются сравнимыми, если либо а /3, либо Обозначим через Гп = (Хп, Zn\En) двудольный граф с множествами вершин Хп = F(n,n — 1) U Для А С Хп положим и fn(A) — 2 э ". Обозначим через 1п функциональную пару (Xn,fn), порожденную графом Гп = (Х„, Zn\ „), в которой Демма 3.2.1. При достаточно больших п функциональная пара 1п = (Хп,/П) является (2, {к",«2},2,4,1)-ординарной с /t" = L0.53TiJ j к; = _0.5те_. Доказательство. Покажем, что условия (1.5.1) - (1.5.6) выполняются при указанных параметрах. Для 5 Є F{n, и—1) пусть j(a) — число двоек в наборе а, а для а. Є F(n, п-\-1) пусть j(a) — число нулей в наборе ос. Из определения следует, что 0 j(a) [(те — 1)/2] для всех а Є Хп. Степень вершины а Є Хп в графе Гп равна п — j(a). Следовательно, Пусть Хп — ХПіх U Хп 2, где ХПі1 — множество вершин а, для которых [0.53nJ \9({&})\,я, Хп 2 —множество вершин а, для которых [0.5raJ д({а}) [0.53те]. Таким образом, при достаточно больших п условие (1.5.2) выполняется ск"= [0.53nJ, а условие (1.5.3) — с к = [0-5 J. Кроме того, нетрудно видеть, что log2 «і — log2 к2 + 0(1) при достаточно больших п. Убедимся в выполнении условий (1.5.4) с q = 2 и (1.5.5) с р — 1. Заметим, что в графе Гп = (Хп, Zn; Еп) для любых двух вершин а,/3 Є Хп выполнено По формуле включений - исключений имеем \д(А)\ \в(А\0})\ + \д(0})\-2(\А\-1). Из определения функционала /„ следует, что Таким образом неравенство (1.5.4) справедливо при q = 2. Теперь убедимся, что при достаточно больших п свойство (1.5.6) выполнено при «2 = [0.5reJ и с = 4, т.е. для любого натурального т и любой а Є Хп справедливо Заметим, что В Є Л{а}(Іп) означает, что существует вершина (З Є В такая, что {а}#{/?}, и что множество В является 2-связным.
В свою очередь { 5}#{/?} означает, что prn(a,f3) 2. Пусть п2({а},а) — число всех 2-связных множеств А С X таких, что Л = а и а Є А. Граф Гп = (Хп, Zn; Еп) удовлетворяет условиям леммы 6.4 из [23] с А = 2п. Поскольку п 16, имеем Для заданной вершины а Є Хп вершину /З Є Хп такую, что ргп(а,(3) 2 можно выбрать не более, чем 2га2 способами. Из сказанного с учетом (3.2.2) при достаточно больших п следует, Неравенство (3.2.1), а тем самым и выполнение условия (1.5.6) доказано. Наконец, проверим выполнение условия (1.5.1). При к" = [0.53rtJ и Д = 2 из (3.1.29) следует, что при достаточно больших п Оценим теперь мощность множества Хп 2- Заметим, что Хп 2 состоит из таких наборов а Є Хп, для которых [0.47га] = га — /г j(a) те — к = [0.5га]. Аналогично (3.1.19) и (3.1.22) получаем, что при j га/3 количество вершин слоя F(n,n — 1) с j двойками равно а"-1, и количество вершин слоя F(n,n + 1) cj нулями равно а"-1, где Отсюда вытекает справедливость (1.5.1). Лемма доказана. Теорема 3.2.1. Пусть {In = {Хп, fn)} L1 — последовательность функциональных пар, порожденных графами Г.„ = (Хп, Zn; Еп), где Хп = F(n,n — 1) U F(n,n + 1), Zn — F(n,n) и fn(A) — 2 1а(л)1 для всякого А С Хп. Тогда при га — оо Из определения следует, что {й,/3} Є И.2(Л»)? если д({а}) П Э({/?}) 0. На рисунках 3.1 - 3.4 изображены множества вершин, принадлежащие семейству Л%(1п). Каждое такое множество является 2-связным в графе Гп = (Хп, Zn; Еп). Жирными точками изображены вершины, входящие в рассматриваемое множество, а простыми точками — вершины, принадлежащие множеству Zn. Вершины соединены отрезком, если в графе G/n, порожденном функциональной парой Jn, существует ребро, соединяющее их. Если две вершины образуют 2-связное множество, то наборы их координат отличаются в одной позиции. Рядом с каждой вершиной выписаны координаты, в которых она отличается от остальных вершин множества.
