О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью

1.    Введение1.1.    Обозначения

В работе рассматриваются простые неориентированные графы. Мы будем использовать приводимые ниже обозначения, в целом согласующиеся с современной литературой (см., наир., [1, 2]).

• •    У (G) и Е (G) — множества верш ин и рёбер графа G соответственно.

• •    Через |G| будем обозначать чііо.то вершин в графе G .

• •    Е (А, В") — множество рёбер вина uv. где u Е A,v Е В. Если А = {v}. то будем сокращённо писать Е (v, В ) вместо Е ({v}, В).

• •    Положим Е(А) := Е (И, И) для произвольного подмножества вершин А исходного графа.

• •    Для графа G = ( V, Е ) и подмножества V ‘ С V через G — V ‘ обозначавм подграф G, порождаемый множеством V \ V '. Сокращённо будем писать G — г вместо G — V ', если V ‘ = { г }.

• •    Для графа. G = ( V, Е ) и подмножества Е ‘ С Е через G — Е ‘ обозначаем граф ( V, Е \ Е'). Сокращённо 'записываем G — е вместо G — Е'. если Е ‘ = { е }.

• •    L(G) — множество висячих вершин графа G.

• •    Lg ( b^ — множество висячих вершин в G, смежных с вершиной г.

• •    Н (G) — множество всех вершин G, смежных с листьями.

• •    Положим S(G) := G — (L(G) U Н (G)).

• e    deg_G(r) — степень вершины г в графе G.

1.2.    Графы с заданной последовательностью степеней

Невозрастающие последовательности натуральных чисел, содержащие ровно п элементов. будем называть п-послсдоватслииостями-. п-последователыюсть d с членами di > d^ >  ... > d_n называется графической, если существует простой граф на множестве вершин {гД”=ц такой, что degг, = di для каждого г Е {1,...,п}. Сам граф называется реализацией п-последовательности d. Последовательности, реализуемые графами (без ограничений на структуру), были полностью охарактеризованы Гавелом [3], Хакими [4], а также Эрдёшем и Галлаи [5].

В настоящей работе будем использовать критерий Эрдёша и Галлаи реализуемости целочисленной последовательности некоторым графом:

Теорема 1 (см. [5]). Последовательность di > d^ >  • • • >  d_n, состоящая из п > 2 неотрицательных целых чисел, реализуема некоторым графом тогда и только тогда, когда (ДГ =1 di ~ чётное число и при этом выполнено:

£« t(t — 1) + V min{ t,d i) V 1 6 t 6 п — 1 .

i =1                   i=t+1

Также сформулируем следующее свойство для степенной последовательности дерева, тривиальным образом следующее из леммы о рукопожатиях:

Утверждение 1. Для дерева на п вершинах, в котором степенная последовательность вершин имеет вид di > d^ >  ... > dk > 2 >  dk+i = ... = d_n = 1, верно соотношение

k

^ — 1)= п — 2 .

i=1

Через 9-будем обозначать класс связных графов, реализующих п-последовательность d. Интерес представляют только п-последовательности длины не менее трёх.

Для произвольного дерева Т определим усечение Т как дерево Т ' (в дальнейшем будем придерживаться именно такого обозначения для усечения Т), получающееся из Т удалением всех листьев. Само дерево Т будем при этом называть расширением дерева Т '. Нетрудно заметить, что степенная последовательность дерева Т' может быть получена из степенной последовательности Т отбрасыванием единичных элементов и уменьшением некоторых из оставшихся элементов (причём суммарное уменьшение равно числу единичных элементов в первоначальной последовательности). При |Т| > 3 усечённое дерево является непустым.

1.3.    Число связного доминирования и остовные деревья с большим числом листьев

Для произвольной пары смежных или совпадающих вершин v и w будем говорить, что вершина v нокрнвается вершиной w (или w нокривает v). Будем говорить, что вершина v покрывается множеством вершин W, если v покрывается w для некоторой w G W. Подмножество D вершин графа G называется доминирующим, если каждая вершина графа покрывается этим подмножеством. Если доминирующее множество D порождает связный подграф в исходном графе, то D называется связним доминирующим мномсеством. Величина 7_c(G) — это размер минимально возможного связного доминирующего множества графа G, она определена только для связных графов. По доминированию в графах имеется обширная литература, см., например, монографию [6].

Через l_c(G) обозначим максимально возможное число листьев в остовном дереве связ ного графа G.

Величины ^_c(G) и l_c(G) связаны простым соотношением:

Утверждение 2. Для любого связного графа G с хотя бы тремя вершинами выполняется

₇c(G) + lc(G) = |G|.

Утверждение 2 следует из того, что любое минимальное связное доминирующее множество D является множеством нелистовых вершин некоторого остовного дерева (в подграфе, порождаемом D, можно выделить остовное дерево, а затем добавить к нему оставшиеся вершины графа в виде листьев) и, наоборот, множество нелистовых вершин остовного дерева образует связное доминирующее множество.

Другими словами, задача поиска в G остовного дерева с максимальным числом листьев (или, что то же самое, с минимальным числом нелистовых вершин) равносильна задаче поиска минимального по размеру связного доминирующего множества.

Задача поиска остовного дерева с наибольшим числом листьев упоминается уже в статье В. Г. Визинга [7] 1968 года. Эта задача является NP-трудной даже для кубических графов [8], поэтому неудивительно, что имеется и продолжает появляться заметное количество работ, в которых приводятся различные нижние оценки величины l_c(G) (что согласно утверждению 2 соответствует верхним оценкам числа y_c(G)), а также относительно быстрые приближённые алгоритмы для данной задачи: [9-19]. В большинстве работ рассматриваются графы с определённой дополнительной информацией о структуре, например, с ограничением снизу на степени вершин или запретами на содержание определённых подграфов.

Термин «связное доминирование» впервые появляется в [20]. Терминология «связного доминирования» используется, например, и в работах [21-25], где авторы рассматривают не только верхние, но и нижние оценки yc(G).

Стоит отметить, что связные доминирующие множества находят практическое применение в целом ряде задач, возникающих в моделировании сетей, в основном беспроводных (см., например, [26,27]). В монографии [28] можно ознакомиться с более подробным списком исследований подобного рода.

В настоящей работе исследуется вопрос точной нижней оценки величины yc, которую можно получить, зная степенную последовательность графа. Другими словами, задача состоит в вычислении значения величины mineGg= {ус(G)} для фиксированной п-последова-5

тельности натуральных чисел d. Исследование диапазонов значений различных инвариантов графов с заданными степенными последовательностями можно встретить также в работах [29-32].

2.    Нижняя оценка числа связного доминирования

Для п-последовательности d введём обозначение

-min '  ■ m^°)}- к у d

Число -min

min

1с

(⁵^ =

определено для непустых классов '-. Из утверждения 2 очевидно следует п - maxGGg= {lc(G)} пр и п > 3. d •

Для получения нижней оценки числа связного доминирования графа G Е ''-, где d задаётся числами di > d2 >  ••• >  d_n, в статье [25] вводится величина ord_c(G), которую можно определить сразу и для всей последовательности d:

ord_c(d) := ord_c(G) = min <  к >  0 |    (dj

- 1) > п - 2

г =1

Тогда из определения ordc (d) очевидно следует неравенство "^ > [^] .

Известна оценка:

Теорема 2 (см. [25]). Для произвольного графа G Е ' -выполнено неравенство

-c(G) > ordc(G).

Обратим внимание, что при наличии в G доминирующей вершины (т. е. образующей одноэлементное доминирующее множество) неравенство обращается в равенство. Теорема 2 может быть доказана с использованием утверждений 1 и 2. Для класса ' - из теоремы 2 получаем

-?'" ('- > ordc(—                             <2)

Из соотношений (1) и (2) вытекает

Лемма 1. Пустъ дана п-последователъностъ d длины не менее трёх, для, которой класс '- не пуст. Тогда выполняется, неравенство

-mn ('- > [Д-2 ].

В статье [25] также приводится семейство графов, для которых оценка теоремы 2 точна, сформулируем соответствующий результат сразу на языке класса Т- всех деревьев, имеющих своей степенной последовательностью d;

Теорема 3 (см. [25]). Для любого дерева Т ЕТ-с хотя бы тремя вершинами выполнено

-с(Т ) = ordc(d).

Теорема 3 легко следует из утверждений 1 и 2.

Перейдём теперь к изложению новых результатов.

Укажем условие на последовательность, которое является достаточным для достижимости оценки из леммы 1, что позволит нам сформулировать точную нижнюю оценку на число связного доминирования для некоторых классов графов.

Теорема 4. Пусть дана п-последовательность d длины п >  3, состоящая из чисел

k = di = dy =

• • •

= d_m > d_m+1 >  • • • > d_n с чётной сум мой, и пусть т >  |" /( 2 + к. Тогда

класс 9- не пуст и для него выполнено

^i" (⁵— = [El ]•

Доказательство. Число |"n-y"] Д^ля удобства будем обозначать как q. Из леммы 1 сразу получаем оценку yCmi" ^9 — >  q (если класс графов не пуст). Осталось убедиться в том, что она достигается.

Итак, покажем, что существует G Е 9 — для которого y_c(G) = q, или, что то же самое, в G можно выделить остовное дерево с ровно q нелистовыми вершинами.

Поделим п — 2 с остатком на к — 1. получим

„   „ I И — 2І п — 2 = (к — 1) • к — 1 + г-

Построим цепь щиу • • • vi n-2 і и. Далее к vi присоединим к — 1 лист, ко всем последующим L fc-iJ вершинам цепи, кроме и, присоединим ровно по к — 2 листа, наконец, к и присоединим ровно т листьев. 11:з равенства (3) легко следует, что в получившемся дереве Т ровно п вершин. При этом нелистовых вершин в Т имеется как раз q, степень каждой вершины vi равна, к = dp а. степень вершины и равна, т + 1.

В таком случае, нам осталось провести в подграфе, порождённом множеством вершин L(T ) U {и}. новые рёбра (некоторые рёбра, пшщлептпые и. там уже

есть при т =  0), так, чтобы на этих рёбрах и

Граф Grem

вершинах получился под-

̃︀

, реализующий степенную последовательность drem, состоящую из чисел

к — 1 = di = d‘2 =

• • •

= d'm_ q > d'   +1 > • • • > d' I „-2 p me ° Дно ИД чисел d‘ равно к — т m 4 m 4+             n-L fc-iJ                          i

—1

(степень вершины и), а все остальные числа среди d' ^ , т — q + 1 6 j 6 п — ^П^-2] ’ образуют в точности невозрастающую последовательность d_m+i — 1 >  d_m+2 — 1 > • • • > d_n — 1. В результате объединения Т и G_rem получится граф G Е 5~ с остовным деревом Т, у которого |Т'| = q. что п требуется.

Осталось лишь обосновать графичность последовательности d_rem. Проверим, что для неё выполнены условия теоремы 1. Длина последовательности d_rem равна п — |_ П 2J > 2-Проверим чётность суммы чисел в d_rem:

n-L Ei J

n

n

Е dl = ЕЛ — EdegT (^) = Edi — 2п + 2.

i =1

i =1       -_и^ Т

i =1

n- I Е2 I

Из выражения (4) видно, что ^i=i ^{fc 1J} di — чётное число.

Пусть 1 6 t 6 к — 1. Тогда, так как m > q + к, то получаем следующую цепочку неравенств:

_t                                                                n-L J

^^ dj = t(k — 1) 6 t(m — q — 1) 6 t(m — q — 1) +  ^^ min {t, d'} = i=1                                                 i=m-4+1

n-L Й J                        n-LJ

= t(t — 1) + t(m — q — t) +   ^^ min {t,di} = t(t — 1) +    ^^ min {t, di} • (6)

i = m - 4 +1                             i = t +1

Пусть теперь t > к. Тогда

t

n-L 2 J

^Д di 6 t(к — 1) 6 t(t — 1) 6 t(t — 1) + ^С min {t, d’} .

i =1

i = t +1

̃︀

Таким образом, из теоремы 1 получаем, что требуемая остаточная последовательность drem действительно реа.тизуема. А так как к — 1 6 п —

|_ 1- 2 J — 1 (^слеДУ^{ет из} неравенства (5)

для t = 1), то, очевидно, на вершинах L(T) U {п} можно реализовать данную последовательность, не задействовав повторно ни одно из г рёбер T, инцидентных п и вершинам

□

из L(T ).

Из теоремы 4 легко следует асимптотика числа у_с при соответствующих условиях на п-последовательности.

Следствие 5. Пусти п ^ то, к = о(п). Пусти для каснсдого п задана п-носледователъ-ности d(п) с членами к = d1 = d2 = • • • = dm > dm+1 > • • • > dn, такими, что их сумма чётна и т > ["$—г"| + к- Тогда для соопівспшпвуютуа ш>слсдовапіслъноспш классов ^~ все её члени непусты и имеет место асимптотика min Гдс \   _

7с VW к

п

.

— 1

Через КУ _к будем обозначать класс связных к-регулярных графов на п вершинах. Для данного класса теорема 4 даёт

Следствие 6. При 2 6 к 6 п — 1 и чётном нроизведении кп класе К^ _к не пуст и для него

-mn (кд ) = щ .

Доказательство. Если к = п — 1, то КД = {Кп} и утверждение, очевидно, выполняется. Пусть далее к 6 п — 2. Докажем неравенство п — 21

п > к — 1 |

Неравенство (6) равносильно следующему: |" Д ²"|

+ к.

6 п — к. С учётом оценки целой части

п — 21 п

| к — 1 | ⁶ к

—

—

к

⁺ к

—

—

1 ^,

для обоснования (6) достаточно доказать неравенство ^-2 + ;-у 6 п — к. Запишем для этого цепочку равносильных преобразований:

п + к — 4 к — 1

п к

—

—

2 к

1 + к

—

—

у 6 п — к,

п + к — 4 6 (п — к)(к — 1) = пк к² — 4 6 п(к — 2).

—

к² — п + к,

Последнее неравенство действительно выполняется, так как к + 2 6 п.

Итак, регулярная п-последовательность имеет чётную сумму членов, равную пк, и удовлетворяет соотношению (6), тогда из теоремы 4 получаем, что КД не пуст и

7?™ (КД) = [S ] ■                                                  □

Отметим, что оценка 7m^m Кд^ >  |”^-2І ^{В Т0М ИЛИ ином ви}Д^е встречается в работах [24,33], но нигде не была показана достижимость данной оценки для произвольного 2 6 к 6 п — 1.

2.1.    Бирегулярные графы с листьями

Будем называть (к, t)-бupeгyляpнымu графы, в которых множество всех вершин можно разбить на два непустых подмножества, в одном из которых степень каждой вершины (относительно всего графа) равна к, а в другом — t. Соответственно, бирегулярные графи с листьями — это (к, 1)-бирегулярные графы при некотором к > 2. Обозначим через Нт _{k z} 1 класс связных (к, 1)-бирегулярпых графов с ровно т полистовыми вершинами и I листьями.

Из теоремы 4 для бирегулярных графов с листьями получаем следующий результат.

Следствие 7. Пусти натуральные числа т, I и к, к > 2, таковы, что тк + Z • 2 и т > |"т+--2"| + к- Тогда Нт к11 не пУст и для него тг (кт.ы.1) = [ к+    2 ] ■

Рассмотрим «меньшие» значения т.

Утверждение 3. Пусть класс Н т к I 1 ^{не П}У^СТ ^а т 6 к. Тогда для любого графа ^{G е} ^ т,к,і, 1^имеем 7 c ^{( g )} = ^т.

Доказательство. Так как т 6 к, то в любом графе G Е Н-тки каждая нелистовая вершина и может быть соединена максимум с к — 1 другими нелистовыми вершинами, таким образом, и обязательно смежна с некоторым листом. Листья графа G являются также листьями и в любом остовном дереве Т, поэтому и смежна с листьями в Т, откуда автоматически следует, что и сама не может быть листом в Т, так как вершин в G не менее трёх. В итоге, L(G) = L(T ), поэтому |Т‘| = т для любого остовного дерева Т, откуда получаем

7с (G) = т для каждого G Е ^.к./. 1

Итак, мы получили точные значения величины 7°"" (^т к i 1) Д^{ля с}лучаев т 6 к и т > |" ^т+--2 ~[ + к. Далее рассмотрим случай т = к + 1.

Теорема 8. Пусти дани целые нолосисителиные числа к, I, где I чётно. Пусть t — такое натуральное число, что t(t — 1) + 2 6 I 6 t(t + 1). Тогда класс Нк+1 к 11 ^{не п}У^ст тогда и только тогда, когда к > t + 1, причём для него выполнено равенство

7?" №+1 . кЩ = t + 2.

Доказательство. Для начала заметим, что число I в силу своей чётности и чётности чисел вида а(а + 1) всегда попадает в некоторый однозначно определённый промежуток вида [t(t — 1) + 2, t(t + 1)], поэтом у число t из условия определено корректно.

Покажем, что при к > t + 1 существует граф G Е Н- к +1_к11, для которого 7c(G) = t + 2, тем самым установим непустоту рассматриваемого класса и неравенство 7 ; °" Д_Ь+_1ЫЛ) <  t +2.

Пусть I = t (t — 1) + 2s, тогда из условия следует 1 6 s 6 t. Возьмём произвольный граф Н, имеющий t+1 верш ин и t—s рёбер. Такой граф, очевидно, несвязен. Кроме того, для каждой вершины и Е Н выпо.тпепо degy(и) <  t. а также вс>іполиеію VlHeh degn^(и) = ^{2(t — s)}. Дополним степень каждой вершины Н до t, присоединив к ней соответствующее число новых вершин-листьев, тогда каждая вершина Н будет смежна хотя бы с одним листом. Множество добавленных листьев обозначим за L, а получившийся в итоге граф за Н+L. Тогда выполнено следующее:

t +1

|L| = IE(Н, L)| = £ deg_H+_L^v) — £ deg_H (и) = £ t — 2(t — s) = t(t — 1) + 2s = I.

v e H v e H i =1

Значит, всего листьев в графе Н+L ровно I.

Пусть S — полный граф на множестве из к — t >  1 вершин, не имеющий общих вершин с Н+L. Каждую вершину Н соединим рёбрами со всеми вершинами S . Получившийся граф обозначим как G. Несложно убедиться, что G Е Kk +1 _к1 1. При этом S = S (G), V(Н ) = Н(G^L = L(G). ’ ”

Поскольку для любого остовного дерева Т графа G выполнены включения Н(G) С Н(Т) С V(Т‘), то в Т‘ обязаны войти все вершины из Н . Но при этом только вершин Н недостаточно, потому что Н — несвязный порождённый подграф в G. То есть необходимо добавить к Н по крайней мере одну вершину из S, чтобы получившееся множе- ство вершин образовывало связное доминирующее множество. С другой стороны, добавить одну вершину достаточно: любая вершина в Е S смежна со всеми вершинами Н и всеми оставшимися вершинами S, а все вершины Н в совокупности покрывают все листья. В итоге множество V(Н) U{v} образует связный порождённый подграф, который покрывает все вершины G. Таким образом. yc(G) = |Н| + 1 = t + 2.

Докажем для непустого класса Kk +1 _{к z} 1 оценку 7 Д ^1П ^Кк +1 к/₁) >  t + 2. Пусть G Е K_k+1 _к11, и пусть |Н(G)| = Һ. Тогда, так как |L(G)| = I > t(t — 1) + 2, то по принципу Дирихле некоторая вершина в Е Н(G) смежна по крайней мере с [~ ^{t ( t} Д⁾⁺² "| листьями.

Тогда среди нелистовых вершин Г t(t-1)+2"l минимум -—Д— полистовых шин через А. Каждая вершина

в имеет максимум к — [~ ^{t ( t} Д⁾⁺² "| соседей; соответственно, вершин не смежны с г, обозначим множество таких вер-из А имеет не более к — 1 нелистового соседа, а значит,

А С Н (G). Таким образом. Н (G) D A U {г}. что влечёт

Һ = |Н(G)| > |А| + 1 > l"⁸^^-^] + 1.

Неравенство (7), очевидно, не выполняется при Һ 6 t, следовательно, |Н(G)| = Һ > t + 1.

Допустим. |Н(G)| >  t + 2. Тогда, так как Н (G) С Н(Т ) С V (Т‘) для любого остовного дерева, Т. то y_c(G) > t + 2.

Осталось рассмотреть случай |Н(G)| = t + 1. Покажем, что в этом случае Н (G) порождает несвязный подграф в G.

Заметим, что k(t + 1)= £ degG(r) = 2|S(Н(G))| + |Е(Н(G), S(G))| + |Е(Н(G), L(G))| >

-ие н ( G )

> ^Е(Н (G))| + |Е(Н (G), S(G))| + t(t — 1) + 2.

Тогда, получаем

2|Е(Н(G))| 6 k(t + 1) — t(t — 1) — 2 — |Е(Н(G), S (G))|.                 (8)

Любая вершина S (G) не смежна с листьями и при этом число возможных соседей среди нелистовых вершин у неё не более |V(G) \ L(G)| — 1 = к. Отсюда немедленно следует, что каждая вершина S (G) смежна с каждой другой нелистовой вершиной, в частности, с каждой вершиной Н (G). Тогда выполнено равенство

|Е(Н(G), S(G))| = |Н(G)| • |S(G)| = (t + 1)(к — t).                     (9)

Из соотношений (8) и (9) получаем

2|Е(Н(G))| 6 k(t + 1) — t(t — 1) — 2 — (t + 1)(к — t) = 2t — 2, откуда |Е(Н(G))| 6 t — 1.

Тогда в подграфе, порождённом Н(Т), ровно t + 1 вершина, а рёбер не более чем t — 1. Таким образом, этот подграф действительно не может являться связным. Для любого остовного дерева Т имеем Н(G) С Н(Т) С V(Т‘), но Н(G) = V(Т'), поскольку Н(G) порождает несвязный подграф, в отличие от V(Т'). Зиачит, |Т‘| > |Н(G)|, то есть |Т'| > t + 2.

В итоге, 7c(G) > t+2 для любого графа G Е Кт _{k t} 1, поэтому ymin (кк_{+1 k t} /) >  t+2. Но тогда k+1 = m >  t+2, откуда k >  t+1. В итоге непустым соответствующий класс является в точности при k > t + 1, причём в таком случае выполнено равенство ymin ^Кк+i _k t^ = t + 2.

Перейдём к случаю k + 1 6 m 6 k + ^m+—-2~| -1' Р^анее рассмотренное значение m = k +1 также включено в указанный промежуток, поскольку позднее будет показана достижимость представленной в теореме 9 оценки как раз в случае m = k + 1 (см. утверждение 4).

Теорема 9. Рассмотрим непустой класс Кт k t i; ⁸де q : = ^mk —i ² , m = k + q — a, 1 6 a 6 q — 1- Пусти m + I — 2 = (k — 1)q — r, 0 6 r 6 k — 2. Тогда выполнено неравенство                                ______________

7m^m (^КД,к,/,i) >  ^{q +} \м^k   н ^r ■ ^ ^{— a +} 2 -

Доказательство. Требуемое неравенство равносильно тому, что в любом графе

G Е Кт к і 1 Д^ля любого его остовного дерева Т выполняется

|Т‘| >  q +

^a(k - 1) - г + 4 - ^{a +} 2.

Тогда пусть Т — некоторое остовное дерево произвольного графа G Е К ^кі i>^и пусть Т имеет степенную последовательность

1 = 1 = ••• = 1 < di 6 ^2 6 • • • 6 ds- т+і—s

Из леммы 1 следует, что s > q. Для каждого г Е {1, 2,..., s} поло жим d' := k — dp Ясно, что 0 6 di 6 k — 2. Пользуясь результатом утверждения 1 и условием теоремы, можем вычислить сумму:

S            S          S                         S

^£ di = ^£ k — ^£ d i = ks — s — ^^(di — 1) = (k — 1)s — (m + I — 2) = (k — 1)s — (k — 1)q + r, i =1        i =1       i =1                   i =1

в итоге получаем

S

^d‘i_i = ^{(k — 1)(s —} q) + ^r- i =1

Рассмотрим граф G', множеством вершин которого являются все m нелистовых вершин G, а множеством рёбер Е(G') = Е(G^\E(Т). В таком случае, степенная последовательность G' имеет вид k — 1 = k — 1 = • • • = k — 1 > di >d2 > • • • > d'S-                    (11)

т — s

Последовательность (11) реализуема графом G^z, тогда по теореме 1 для t = m — sc учётом равенства (10) имеет место неравенство

(k — 1)(m — s)= ^Т(k — 1) 6 t(t — 1) + £min{t,di} 6 (m — s)(m — s — 1) + Д di = i=i                        i=i                                         i=i

= (m — s)(m — s — 1) + (k — 1)(s — q) + r, откуда

(k + s — m)(m — s) 6 (k — 1)(s — q) + r-

Используя равенство т = к + q — а, выполним цепочку преобразований:

(к — 1)(s — q) + г > (к + s — т)(т — s) = (s — q + а)(к + q — s — а), к(s — q) — (s — q) + г > к(s — q) + ак — (s — q + а)² , (s — q)² + (2а — 1)(s — q) — (ак — а² — г) > 0.

неотри-

Рассмотрев (12) как квадратичное относительно (s — q) неравенство, с учётом пателыюсти (s — q) получаем s — q > —а + 2 +

^4а(к — 1) — 4г + 1

’

откуда

s > q +   а(к — 1) — г + 4

—

^{а +} 2 ’

что и требовалось.

Приведём асимптотическое следствие теоремы 9.

Следствие 10. Рассмотрим последователъностъ непустых классов Кт^/ i со

□

следую-

Доказателъство. Из условия следует, что т + I — 2 к — 1

- тк+^ ^а(к — 1) —

г + 4

—

а + 2 -

Подставляя эти соотношения в теорему 9, получаем требуемое.

□

Оценку теоремы 9 можно переписать без использования величины г, для этого сначала перепишем подкоренное выражение:

а(к — 1) — г + 4 = а(к — 1) — (к — 1)q + т + I — 2 + 4 =

— I + 4 — (к — 1)(q — а) + к + q — а — 2 — I + 4

— (к —

^{2)(q — а —} 1).

Таким образом, получаем оценку

⁷C m ⁱⁿ (^Km,fe,z, i ) > ^{q +} У^ ⁺ 4 ^{— (к — 2)(q — а —} 1) ^—

^{а +} 2.

Примечательно также следующее. Для фиксированных значений к и чётными) можно рассмотреть семейство последовательностей

I (положим их

∞

< dm | в dm ровно m членов равны к и I равны единице > т-

.

С некоторого момента т >  N все соответствующие классы Q~ = К Д_{к z} 1 d_m             , , ,

будут непусты

согласно следствию 7 (при достаточно больших т соответствующее неравенство из условия следствия соблюдается). Пусть

q^(m) := |"

т + I — к — 1

, г(т) := q(m) • (к — 1) — (т + I — 2).

Очевидно, 0 6 q(m + 1) — q(m) 6 1, при чём q(m + 1) — q(m) = 1 тогда и только тогда, когда r(m) = 0. Тогда при переходе от m к m + 1 во всех случаях m > к + q(m) значение 7miⁿ (9- )■ ptівное q(m) по следствию 7. увеличивается максимум на 1.

^Н т

Предположим, выполнено m = к + q(m) — 1, r(m) = 0, и при этом класс 9 ~ не пуст. В таком случае, исходя из теоремы 9:

l! > [VI—I] > 1.

7m^m (⁹ - )^— q^(m) >  ^{к — r(m) —} 3^— \ Н-т                                     I

При «малом» значении r(m) относительно к разность и вовсе получается существенно больше 1. напршюр. при r(m) = о(к), к ^ то. получается 7mⁱⁿ (9- ) — q(m) &  Vk.

й т

В то же время m +1 = к + q(m) = к + q(m + 1). поэтому 7mⁱⁿ (9~   ) = q(m +1) = q(m).

«т+Ы

То есть 7mⁱⁿ уменьшается. іі иногда существенно. при переходе от m к m +1. При дальнейшем же рассмотрении переходов от m + s к m + s + 1 величина 7mⁱⁿ меняет своё значение максимум на единицу, причём в сторону увеличения (на q(m + s + 1) — q(m + s)). Получается, что в точке m происходит своего рода «фазовый переход». Пример ситуации, когда «фазовый переход» происходит на существенно большую величину, будет получен позже в виде следствия утверждения 4.

Определим, насколько точна нижняя оценка в теореме 9 для случая, в котором уже было получено точное значение величины 7mⁱⁿ (^Д //^ ^то есть при m = к + 1. Поскольку данному значению m соответствует а = q — 1, то в форме (13) неравенство теоремы 9 принимает вид

⁷ mn (Я./₊ід/, і ) >  I ⁺ 4 ⁺ |.

Оказывается, оценка (14) точна, правда, с поправкой на целую часть:

Утверждение 4. Для непустого класса ^Д / / 1, где m = к + 1, выполнено равенство imn (кДл/,1) =  ^1

^{1 +} I ⁺ 2

.

Доказательство. Положим I Е [t(t — 1) + 2,t(t + 1)], t Е N. Тогда согласно теореме 8 имеем 7min ^Д / / 1) = t + 2. То есть необходимо убедиться, что

\'. ■3

= t + 2.

Воспользуемся определением величины t, получим

, R 1 3 Г 1 з R 1 3

^{t + 1} = V^{t — t +} I ⁺ 2 д^{1 +} I ⁺ 2 ⁶ v^{t + 1 +} I ⁺ 2= ^{t + 2,}

□

откуда немедленно следует равенство (15).

Пусть I — произвольное чётное, аг— произвольное нечётное натуральные числа, I Е [t(t — 1) + 2,t(t + 1)], t Е N. Положим k := I + г + 1, m := к + 1 = I + г + 2.

Тогда q(m) = [д+—-= [т+ДІ = 2, r(m) = q(m) • (к — 1) — (m + 1 — 2) = г. Также выполнено m = к + 1 = к + q(m) — 1. Очевидно, к > t +1, тогда из теоремы 8 и утверждения 4 получаем

7min (^m,fc,Z,1) = [V^+4 ⁺ 2 1 • ^{ТаК КаК Г(т)} =

г >  0, тот + 1 = к + q(m) = к + q(m + 1),

из следствия 7 получаем уД™ ^Д_{+1 kl}^ = q(m + 1) = q(m) =

2. То есть при переходе от

т к т + 1 число 7,m^m уменынас)тся с ^^І + 4 + 32 ,то 2. В то же время при любом М >  т выполнено М > к + q(M ). соответственно. при переходе от М к М + 1 по следствито 7

значение дтт увеличивается на 0 6 q(M + 1) — q(M) 6 1. Таким образом, при достаточно больших І «фазовый переход» в точке т происходит на существенную величину, а именно порядка VI■

3.    Заключение Остаётся те величине достижимы; открытым довольно широкий спектр вопросов по затронутой в данной рабо-^imin Qg^: нахождение условий, при которых оценки леммы 1 и теоремы 9 получение точных значений дД™ ^^ki^ при к + 1 < т < к + [~m+--2"|; точных значений yVin ^9д^ ПРИ т < к + |"£-2 "| Для более сложных п-последовательностей ∞ d, изучение поведения последовательностей ] dm [ до «фазовой» точки т. Также инте- I   J m=1 pec может представлять нахождение всех достижимых значений величины ус в некоторых классах 9~ аналогично работам [31.32]. том более при имеющихся опенках на y^ax Qg7^ (см., например, [9-19]).

Автор выражает признательность А. Б. Дайняку за многочисленные обсуждения, способствовавшие продвижению исследования и улучшению изложения в статье.