О реализации подграфов случайного графа графами диаметров на плоскости и в пространстве

Настоящая работа, посвящена, исследованию некоторых вероятностных характеристик, связанных с классической проблемой Борсука. Напомним, что эта проблема состоит в отыскании числа Борсука — величины f (d), равной минимальному количеству частей меньшего диаметра, на. которые можно разбить произвольное множество диаметра. 1 в пространстве RP:

f (d) = min{f : V В C R^d, diamH = 1, 3 H1,..., Н : В = Н U ... U Ну, V г diamH < 1}.

Гипотеза. Борсука, предложенная Борсуком в 1933 году (см. [1]), состояла, в том, что f (d) = d + 1. И ровно шестьдесят лет эта гипотеза оставалась ни доказанной, ни опровергнутой. Лишь в 1993 году Кан и Калан (см. [2]) нашли контрпримеры к гипотезе в размерностях d >  2015. Сейчас известно, что runотеза Борсука верна при d 6 3 и ложна при d >  298 (см. [3] - [13]).

С проблемой Борсука, тесно связано понятие графа диаметров. Назовем графом диаметров в R^d любой граф G = (V,E ). вершины которого — точки R^d, а ребра — пары вершин, отстоящих друг от друга на максимальное в множестве вершин расстояние:

V C R^d, |V| < то, E = {x, y} : |x — y| = diam V := max |x — y| . ^x,ycV

Понятно, что минимальное число частей меньшего диаметра, на которые разбивается V (число Борсука множества V), — это в точности хроматическое число x(G) графа G, т.е. наименьшее количество цветов, в которые можно так покрасить вершины, чтобы концы любого ребра имели разные цвета. Однако было бы некорректно сказать, что f (d) — это максимум таких хроматических чисел. Дело в том, что равенство хроматического числа, числу Борсука, справедливо лишь в случае конечных множеств; для бесконечных множеств равенства, вообще говоря, нет: например, если взять в качестве V сферу в R^d, то очевидно, что хроматическое число ее графа, диаметров (являющегося паросочетанием) равно двум, тогда как ее число Борсука есть d + 1 ввиду классической теоремы Борсука-Улама-Люстерника-Шнирельмана (см. [14] - [15]).

Как мы отметили выше, на. плоскости и в пространстве гипотеза. Борсука, доказана. Более того, существует достаточно много примеров графов диаметров в R² и R³ с хроматическими числами 3 и 4 соответственно. Интересно оценить, стало быть, насколько эти примеры часты или редки. Одним из инструментов для такой оценки служит случайный граф Эрдеша-Реньи (см. [16] - [22]). А именно, пусть V_n = {1,...,n}, р = p(n) Е [0,1]

и G(п,p) = (^_у, П_п, P_n,_p) — вероятностное пространство, в котором П_у — множество всех графов на ТУ без петель, кратных ребер и ориентации (так что |И„| = 2^С"), П_п = 2^”,

P»,p(G) = p^|E|(1 - p)^{c -|E|}.

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

Положим для d Е {2, 3}

Ud(п,p) = max

I k : P„,_p (3 H = (W,F ) C G :

) > D-

\W | = k, H = G\w, H — граф диаметров в R, x(H ) = d + 1

Таким образом, мы ищем максимальное количество вершин в индуцированном подграфе случайного графа, который одновременно реализуется графом диаметров на плоскости или в пространстве и имеет наибольшее возможное в этом случае хроматическое число. Если для любого k

Pn,p ^3 H = (W, F) C G : | W| = k, H = G\w, H — граф диаметров в Rd, x(H) = d + 1) 6 |, то полагаем ua(n,p) = 0.

Величина U2(п,p) была введена в работе [23], а похожие величины для так называемых дистанционных графов рассматривались в статьях [24] - [26]. В следующем разделе мы сформулируем результаты, доказанные в [23], их усиления и обобщения на случай R³.

2.    Формулировки результатов

В работе [23] были доказаны следующие утверждения.

Теорема 1. Пусть р = о (1). Тогда, при всех достаточно больших п Е N выполнено U2^,p) = 0.

Теорема 2. Пусть q := 1 — p = о (утл)- Тогда при всех достаточно больших п Е N выполнено u₂(п,p) = 3.

Теорема 3. Пусть q = о (у), но пр и этом q^'⁵ ^ то. Тогда при всех достаточно больших п Е N выполнено u₂(п,p) = 4.

Теорема 4. Полоэюим т(п) = pп и а(п) = q ln п. Пусть т(п) и ст(п) стремятся к бесконечности с ростом п. Тогда для любого е >  0 существует такое по, что при п > по выполнено

U2(п,p) 6 (2 + e)log 1 (пp).

1 - р

Теорема 5. Полосисим т (п) = ^Пу и а(п) = qln п. Пусть т (п) и а(п) стремятся к бесконечности с ростом п. Тогда для любого е >  0 существует такое по, что при п > по выполнено

4 ln p u2(n,p) > (j> - е + in(пp)Уogт-р ("p)-

Эти теоремы говорят о том, что если величины p и q не слишком малы, то

1пп k p 7

u₂(п,p) ~ 2 log 1 (пp) = Ө т-р

В частности, требуется, чтобы величина p не стремилась к нулю со скоростью п “ при а > 4 (теорема 5). Это ограничение можно существенно ослабить. Справедлива новая

Теорема 6. Зафиксируем некоторое число а Е (0, 2) и иоломсим т(п) = рп“. Пусти с некоторым С > 0 начиная, с некоторого п выполнено 1 < т(п) < С. Тогда для любого е > 0 существует такое по, что при п > по имеет место неравенство и2(п,р) > (2 — 2a — е)---.

Р

Теорема 6 дает принципиально новый в сравнении с теоремой 5 результат при а >  4. Однако и при меньших а новая теорема сильнее. А именно, если в теореме 5 взять р = п-“, то она (с точностью до вычитания е) даст оценку величиной

/2 +     ^{4 П п} \ (l-ojlnn = (2 —    ¹.

\    (1 — а) ln п у р                 р

В то же время в теореме 6 мы имеем оценку величиной (2 — 2а)ln^, и это намного больше.

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

Теорема 7. Пусти найдется такое с< 1, чтор < ^. Тогда при всех достаточно болиших п Е N витолнено пз(п,р) = 0.

Теорема 8. Пусти q = о (^т:5)- Тогда при всех достаточно болиших п Е N выполнено из(п,р) = 4.

Теорема 9. Полосисим т(п) = рп и сг(п) = q ln п. Пусти т(п) и сг(п) стремятся к бесконечности с ростом п. Тогда для любого е > 0 существует такое по, что при п > по выполнено из(п,р) 6 (2 + e)log 1 (пр).

1 - р

Теорема 10. Пусти для всякого а > 0 выполнено рп“ ^ то и qlnп ^ то при п ^ то. Тогда для любого е > 0 существует такое по, что при п > по выполнено из(п,р) > (2 — е)1од_ж_(пр).

1 - р

Теорема 11. Зафиксируем некоторое а Е (0, 4) и поломсим т(п) = рп“. Пусти с некоторым С > 0 начиная с некоторого п выполнено 1 < т(п) < С. Тогда для любого е > 0 существует такое по, что при п > по имеет место неравенство из(п,р) > (2 — 4а — е)---.

Р

Доказательства теорем 7 и 8 очень просты, но мы их аккуратно проведем в разделе 3. Доказательство теоремы 9 весьма близко к доказательству теоремы 4, но есть нюансы, и мы докажем теорему 9 в разделе 4. Теоремам 10, б и 11 мы посвятим раздел 5 (именно в таком порядке).

3.    Доказательства теорем 7 и 8

Заметим, что если в графе диаметров в R³ число вершин к, то в нем не больше 2к — 2 ребер (см. [27]).

3.1.    Доказательство теоремы 7

Хорошо известно, что при ограничениях на р, заданных в формулировке теоремы, случайный граф с асимптотической вероятностью 1 является унициклическим. Но индуцированный подграф такого графа на любых к вершинах и с любым к Е {1,..., п} сам является унициклическим, т.е., в частности, имеет хроматическое число не больше трех. Значит, при достаточно больших п и всех к

Pn,P (3 Н = (W, F) С G : |W| = к, Н = G\w, Н — граф диаметров, х(Н) =4) < |, так что из(п,р) = 0. Теорема доказана.

3.2.    Доказательство теоремы 8

При q = о (щт5) ^с асимптотической вероятностью 1 дополнение G случайного графа G до полного графа К_п является паросочетанием. Значит, при больших п с вероятностью больше 2 граф G содержит К4, который имеет хроматическое число 4, у которого 4 вершины и который реализуется как граф диаметров (тетраэдр) в пространстве. Однако при к >  5 с той же вероятностью любой к-вершшшый индуцированный подграф Н случайного графа либо является полным графом без двух несмежных ребер (при к = 5), либо имеет строго больше, чем 2к — 2, ребер. В первом случае х(Н ) = 3; во втором случае Н нельзя реализовать графом диаметров в R³. Значит, при к >  5 требуемое свойство выполнено с вероятностью меньше половины. Теорема доказана.

4.    Доказательство теоремы 9

Зафиксируем е > 0 (см. условие теоремы) и положим к = к(п) = |"(2 + е) log 1 (пр)~| .

Прежде всего покажем, что к Д то. В самом деле, с учетом неравенства — 1п(1 — р) < т—р имеем

log 1 (пр) = 1 - р

1п(пр)

— 1п(1 — р)

(1 — р) 1п(пр) р

Значит, если р Д 1, то, поскольку пр Д то, получаем 1 — р = q на ^) (см. условие теоремы) и получаем, в к Д то. Белл же р Д 1. то заменяем свою очередь,

(1 — р) 1п(пр)     ст(п) 1п(пр)

----------- = ---:-----~ Дп) Д то.

р           р 1пп

Далее, как и в параграфе 3.2, воспользуемся тем фактом, что у любого графа диаметров в R³, имек:>щего к вершин, число jзебер не больше 2к — 2.

Обозначим через Вк событие, состоящее в том, что у любого индуцированного подграфа Н случайного графа G. имеющего к вершин, число petзер строго больше 2к — 2. Положим Рк = Рп,р(Вк )• Если найдется такое по = п о (е), что пр и всех п > по выполнено Рк >  2, то с вероятностью, большей половины, в случайном графе G не найдется индуцированного подграфа Н, представимого как граф диаметров и имеющего к вершин. А значит, не найдется и такого подграфа большего размера, т.е. пз(п,р) <  к.

В дальнейшем мы покажем, что Рк Д 1 при п Д то, и это завершит доказательство теоремы.

Обозначим через Хк случайную величину, равную количеству индуцированных к- вершинных подграфов случайного графа, имеющих не более 2к — 2 ребер. Тогда Рк = Pn,_P(Xk = 0) и с учетом неравенства Маркова

Рк = Р„,р(Хк = 0) = 1 — Р„,р(Хк > 1) > 1 — МХк, так что остается доказать асимптотику МХк Д 0. За счет линейности математического ожидания получаем

2к

6 с,к £сс 2 р^і q^ck- . к

і=0

2к-2

МХк = с^к V сС 2 р\^с^ к

і=0

Убедимся в том, что в последней сумме максимальным является последнее слагаемое. Для этого разделим (г + 1)-е слагаемое на г-е (0 6 г 6 2k — 1) и проверим, что отношение не меньше единицы:

Л¹ ^ ^{+ 1} T? + 1 /7C fc—^—1      z-y9

' c р q 4       C — гр

-----------^----- =  • —.

CгГ, 2 ргдск-г        г + 1q ск с2—г убывает по г. Значит.

Понятно, что функция г +1

Ск — г р >  C2 — 2k + 1 р Ск — 2k р _ k — 5 р г +1 q ^/     2k       q 2k q 4 q

Мы хотим показать, что k — 5 р

4 q ’ а покажем даже, что k — 5 р 4 q     'Х.

Упростим, стало быть, запись и рассмотрим выражение ^. Поскольку пр ^ то и — 1п(1 — р) < Д-. имеем kр q

21п(пр)

— 1п(1 — р)

---- > 21п(пр) ^ то. 1 — р

Итак, при больших п

МХк 6 (2k + 1)Cк C%р^2кq*^^-2 . к

Воспользуемся простыми оценками C^ 6 (цу )^Ь и C 6 у!- Получаем

Ы (3п\к (C2)2к 2fc сз_2к „ /3п\к k4k 2к С2_2к „ мХк 6 2k . Д -Дтk2kqCk 2к 6 (т) Wр q    6

, / 3п\ ^к k⁴     „ Щ-1   /3 , V _b,t 2к к|к-=)   (3 2 , 2 4-5")^к

⁶ (т) WXF^{k р q 2 _} и у)^{п k р q 2 _} и ^enkvq У .

Теперь для завершения доказательства теоремы достаточно проверить, что в ее условиях ^к-⁵

величина пkр q 2 стремится к нулю. Итак, fc-5                      е пkр q 2 < exp 1 + - j

1п(пр)                                             1n(kр)

—----1п q + 1п(пр) + 1n( kр) _ exp 1п(пр) ——-— 1п q                                           1п(пр)

— i))

^ 0’

поскольку при достаточно больших п ln(np)

1n(kр)    ^{1п 3}- 1п(1-р) ^р)    1п(31п(пр))   1п3 + 1п1п(пр)   е

1п(пр)         1п(пр)            1п(пр)           1п(пр)        2

Теорема доказана.

5.    Доказательства теорем 10, 6, 115.1.    Общая идея

В каждой из перечисленных теорем нужно установить нижнюю оценку вида п^(п,р) >  k. Понятно, что достаточно найти конкретный граф на k вершинах, который имеет хроматическое число d + 1, реализуется как граф диаметров в R^d и с высокой вероятностью встречается в С(п,р). Для плоскости таким графом будет цикл нечетной длины.

Для пространства это будет пирамида, в основании которой лежит цикл нечетной длины и вершина которой соединена с каждой вершиной основания. По сути, уже сейчас ясно, откуда возникло различие в ограничениях, наложенных на а в теоремах 6 и 11. Дело в том, что у цикла плотность (отношение числа вершин к числу ребер) асимптотически вдвое выше, чем у пирамиды.

Начнем мы с доказательства теоремы 10, поскольку в нем слабее ограничения на вероятность ребра и это позволяет делать более грубые оценки. В теоремах б и 11 мы эти (или аналогичные) оценки значительно уточним.

5.2.    Доказательство теоремы 10

Зафиксируем е > 0 и положим к = [(2 - e)log 1—р

При доказательстве теоремы 9 мы уже убедились в том, что к ^ то. Нам достаточно показать, что при больших п выполнено из(п,р) > к. Наличие целой части не играет никакой роли, т.к. к ^ то и при необходимости мы просто можем заменить е на е‘ € (0, е). В дальнейшем некоторые неравенства будут выполнены лишь при п > пд, но мы не будем каждый раз говорить об этом.

Обозначим через Y_k случайную величину, равную количеству индуцированных к-вер-шинных подграфов случайного графа G, являющихся пирамидами с циклом длины к — 1 в основании. Если мы докажем, что при больших п выполнено P_n,_p(Yfe > 0) > 2, то при тех же п мы получим ид (п,р) >  к. Как всегда, мы до кажем еще больше: P_n,_P(Yfe > 0) ^ 1.

В силу неравенства Чебышёва имеем

DEL

Pn»(Yk >  0) =     ^Y > 1) > ¹ — ^ү^ .

MY_k = СДк ^{( к} — ^2)! p^2k-2q^C k ^-(2к-2) .

Нетрудно видеть, что поскольку р-1 не превосходит любую положительную степень п, то, по крайней мере, к = Ө (log 1—р(пр)) < Ө ( — ^1- р)) 6 Ө (1"рп) < Ө (п5 1Пп) = ° ^^ .

Поэтому с большим запасом СД ~ дт ^и

MY„ ~ ^ р²^^-^ =  ' р»^ .   >  1 „^ ^ = 1 , _..,'

к!      2                         2(к — 1)                     2к               2к

Поскольку к ^ то. для обоснован!ія асимптотики MYfe

^ то достаточно найти такое 5 > 0.

что

пр2дк/2

= exp

1п(пр) + 1n р +

21п q)

> 1 + 5.

Это равносильно существованию такого 5 > 0, что 1п(пр) + 1n р + ^fe 1n q > 5. После подстановки явного выражения для к имеем

1п(пр)+1пр+(2 — е ‘ ) — р^ 1n q = ( 1--( 1п(пр)+1п р = 1п(пр) (--1-- р | > — 1п(пр) ^ то,

—21n q               2                            2   1п(пр) у    4

т.к. в наших условиях рцу|) ^ 0, и все в порядке.

Проверим теперь асимптотику М² Үк ~ (МУк)²- Имеет место стандартное соотношение

М² Ү к = 52 МУс _{1 А} , С 1 ,С 2

где суммирование ведется по всем упорядоченным парам различных к-вершинных пирамид С1,С₂ С К_п, а УС1,С₂^— индикатор одновременного попадания пирамид С1,С₂ в случайный граф G в качестве индуцированных подграфов. Отдельно рассмотрим слагаемые с V(С1 ) ПР (С2) = 0 и слагаемые с V(С1) ПР(С2) = 0. В первом случае получаем выражение

S1 = с - С^ (к ^--^:< ².q ^{2 2} У ~ ( с- к (^—^ р²к^-2д^СМ²к^-2)^² = (MY_k )².

Предпоследний переход сделан за счет к = о ( 4—-). Если покажем теперь, что

S2 =52 УС1,С2 - S1 = о ((МУк)2) , С1 С то завершим доказательство теоремы. Для каждой пары пирамид С1,С2, которые различны, но пересекаются хотя бы по одной вершине (именно такие пары задают S2), можно найти число общих вершин (обозначим его через m = m(C1,C2)) и число общих ребер (обозначим его через I = Z(C1,C2)). Очевидно, что m Е {1,...,к}, I Е {0,..., 2m — 2}. Таким образом,

S2 6 52 Е СкС^С^ (к ^{( к} — ^2)! 2 р^4к-4-q^M²^-^+1 т=1 1=0                          '

.

Допустим, мы доказали, что при всех m, I

СПС^С^ (к ^((к-^ )² р^4к-4-у^(С_к²-^(2к-2))-^С^⁺

= ^

СпС-_-к (к(^ p^^qCl ^-(2к-2))²

Тогда

S2 6 2к²ск си (к   / ! .             :' о (-1) =

= о((МУ к )²),

_   / ркрк        ^{(к — 2)!} 2к-2 С2- 2 -(2 к -2)

= ^о I ^С п ^С п - к I ^к 2   ^    ⁹

и теорема доказана. Итак, имеем

С ^ С^С ^ ( к ( ^ -^ ) ² p 4/= ^- 4 ^- Z ₉ 2( C 2 ^- (2/_C ^- 2)) ^- C ^ +1

С ^ С^ ( к ( ^ -2)! p^ k-Z g CYEXk-i^

^{к(к —} 1) • ... • ^{(к — m} +¹)    _{С m} _ - _{t n}_ c2 _m + ; ₆

(п — 2к + 1) • ... • (п — 2к + m) ^к

6 2 ^k2m n ^-m p ^-l q ^-c ^ ^+l 6 2к ^{2 т} п ^-т p ^{- 2 m +2} 9 ^-C 2 .

Остается показать, что при всех m Е {1,..., к} выполнено к2к2тп-тр-2т+29-Ст = exp ((2m + 2) ln к — mInn — (2m — 2) Inp — C^ Inq) ^ 0.

Если рассмотреть выражение в показателе экспоненты как функцию от т, то ввиду неравенства ln q <  0 это квадратичная функция с положительным коэффициентом при т². Значит, ее максимум по т достигается либо при т = 1, либо при т = к. При т = 1 имеем (с учетом к = о (^/п))

4 ln к — ln п = ln

( - )

= ln(o(1)) ^ —то,

и все в порядке. При т = к имеем

(2к + 2) ln к — к ln п — (2к — 2)ln p — C t ln q = к

( ln(к ² ) +

21nk к

— ln(np) —

^к-^— -2 ln р — ^{к —} -^ln q)

6 к fln(к ² ) + ^ln^ — ln(np) — ln р — (2 — e ‘ ) ^{ln( np )} ln q) = к                           —2 ln q

—e'                    21nk                        e ‘    ln(к ² )     21nk      ln p

= к       + b(t ) + — — InpJ = к 1„Ы - + l-^--) + ^^ — —J ^ -„ поскольку к ^ то. np ^ то. іП(у||) ^ 0 ii q i / 2 ln(n|) \ п i / 2 ln(n|) \

1n(k²)    ^2ln - in(i- i ) у    ^2ln(^    | J 2(ln2 + lnln(np) — ln p)

ln(np)        ln(np)            ln(np)                 ln(np)

Снова все в порядке, и теорема доказана.

• 5.3.    Доказательство теоремы 6

Как и в доказательстве теоремы 10, зафиксируем e > 0, но на сей раз положим lnn"l к = (2 — 20 — е) —  .

В данном случае очевидно, что к ^ то. И целая часть нас по-прежнему не беспокоит.

Обозначим через Ук случайную величину, равную количеству индуцированных к-вер-шинных подграфов случайного графа G, являющихся циклами. Если мы докажем, что при больших п выполнено Р_п,_|(Ук > 0) > 2, то при тех же п мы получим U2(n,p) >  к. Как всегда, мы докажем еще больше: Р^ДУк > 0) ^ 1.

Как и в параграфе 5.2, пользуемся неравенством Чебышёва, так что достаточно проверить справедливость соотношений МУк ^ то и М²Уіс ~ (МУк)²- С одной стороны, дальнейшие выкладки будут крайне похожи на выкладки из доказательства теоремы 10. С другой стороны, нынешняя величина Үк слегка отличается от одноименной величины из параграфа 5.2, а главное, если в параграфе 5.2 вероятность p ребра случайного графа обладала свойством pn“ ^ то при любом а, то здесь, напротив, p = Ө (п^-“) при тех или иных а € (0, 2). Поэтому мы приведем выкладки во всех подробностях.

Итак, начинаем с математического ожидания. За счет его линейности имеем

МҮк = C^   2 ' ^! p^k q .

Нетрудно видеть, что при а € (0, |), т € (1, С) выполнено к = ө (ln^ ) =ө (^) = о (СП).

Поэтому (уже без какого-либо запаса) Ск ~ дт и пк (к — 1)!    (72 Ь пк Ь Ср — к    1         2/2    1            к

МҮк ~ fe!    ₂   p^kq^{к к} = -кP^кq^{к к} > 2k  p^kq^{k /2} = 2к (npq^k/2) .

Поскольку к ^ то, для обоснования асимптотики МУк ^ то достаточно найти такое 6 > 0, что

npqk/2

= exp

^ ln( rip)

к А

⁺ 2^{1П q})

> 1 + 6.

Это равносильно существованию такого 6 > 0, что ln(np) + 2 ln q > 6. После подстановки явного выражения для к с учетом p < — ln q имеем ln(np) + ^1

-

a —

^ln q

---ln n > p

ln(np) — ^1

-

a —

e’A , — ln n.

2/

Теперь вспомним, что p >  n “, и оценим снизу первое слагаемое:

(1 — a) ln n —

— a

-

ln n = — ln n ^ то 2

и все в порядке.

Проверим теперь асимптотику М)Ук — (МУк)2- Как и прежде,

М / Y_k = Е МУ с і ,С 2 ,

C 1 ,C ₂

где суммирование ведется по всем упорядоченным парам различных к-вершинных циклов С1,С2 С К_к, а Yc1 ,с₂ — индикатор одновремеиного попадания циклов С1,С2 в случайный граф G в качестве индуцированных подграфов. Рассмотрим отдельно слагаемые с V(71 ) ПР (С2) = 0 и слагаемые с V(Сі) ПР(С2) = 0. В первом случае получаем выражение

51 = С к С к - k (₂ p^kq^c~^k У - (С к ₂ p^kя^^—к У = (MY k )².

Предпоследний переход сделан за счет к = о (Дп). Если покажем теперь, что

52 = Е Y c i ,C 2 —51 = o((MY k )²),

C 1 ,C 2 то завершим доказательство теоремы.

Для каждой пары циклов С1, С2, которые различны, но пересекаются хотя бы по одной вершине (именно такие пары задают 52), можно найти число общих вершин (обозначим его через т = т(С1,С₂)) и число общих ребер (обозначим его через I = 1(С₁,С₂'7 Очевидно, что m Е {1,..., к}. I Е {0,... , m — 1}. Таким образом.

к m— 1

52 6 ЕЕ С^к Ck—m Ст А(к,m,г)p^2k^q²^-^k>-^c m + < , т =1 1=0

где А(к, т, Г) — число способов образовать пару циклов с выбранными к вершинами для каждого, пересекающихся по выбранным т вершинам и каким-то I ребрам. Если в теореме 10 мы очень грубо оценили величину, аналогичную величине А(к,т, I), то теперь нам придется действовать значительно аккуратнее.

Обозначим количество изолированных цепей, по которым пересекаются два цикла, через г. Стоит отметить, что здесь мы рассматриваем и вырожденные цепи, состоящие из одной вершины. В каждой такой цепи количество вершин, разумеется, на единицу больше числа ребер. А значит, общее число вершин в пересечении в точности на г больше, чем число ребер. Иными словами, г = т — I. Заметим, что и дополнительное множество из к — т «свободных» вершин каждого цикла, по которым они не пересекаются, также состоит из г цепей.

Будем конструировать нашу пару циклов следующим образом. Выберем сперва г цепей из т вершин в пересечении (обозначим это число норе:;: д(т, г)), а потом г пеней среди свободных к — т вершин каждого цикла (соответственно, д(к — т, г)). Ясно, что каждая пара циклов задается подобным выбором, а значит, мы имеем оценку сверху:

А(к, т, І) 6 д(т, т — І)д‘²(к — т,т — І).

Осталось понять, как выбрать г цепей из т вершин. Для этого сначала расставим всевозможными способами все вершины, а потом между ними на т — 1 место поставим г — 1 перегородку. Получаем д(т, г) = т!Ст—¹1- Окончательно имеем

А(к, т, І) 6 т'С .' ' ((к — т)!С^-\ )2 .

Покажем теперь, что |2 = о(1), и завершим тем самым доказательство теоремы. Итак, имеем к т— 1

6 ЕЕ 8к2п—тСт—і т=1 l=0

( гчт—1 — 1 5 ²

^Ск—т— 1)

nal е

'У ^п - “

^Е ^ С^С^-^С^А(к, т, Dp^k-lq^^^ l -k^-C ^ +1 т=1 Ы      С^С^-_—к (( " -^)² p^2kq²^^

к т— 1 /     , , 6 ЕЕ( т =1 l =o і(к—т)!

у (п — 2к)!  c т -1-y(k-m)!c; тт :Д р—    +, 6 (п — 2к + т)!           ( ( к —1)! 52

Здесь в последнем неравенстве мы пользуемся тем, что к = о (Дп), делая оценку

(п — 2к)!

(п — 2к + т)

6 2п^—т,

(п — 2к + 1) •... • (п — 2к + т)

справедливую при больших п.

Разобьем внешнюю сумму на две — ‘+ ‘ + ‘^' — и покажем, что обе они стремятся к нулю с ростом п. В первую войдут слагаемые при т <  ^Д а во вторую — оставшиеся, т.е. при т >  Д-. Рассмотрим первую из них. Заметим, что Ст_—1 < 2^т и Ск——^—1 6 Ст——¹- Более того,

С т ^—1—1  _______ (т — 1)(т — 2) • ... • (т — І) _______ _<  т¹  _ / 2т ^у

СД—1    (к — т + 2)(к — т + 3) • ... • (к — т + І + 1)   (к/2)l   у к / , ведь т = О (^) ,І = О (A-). Следовательно, СД—1—1 6 СД—1 (2Д)l 6 (5—L (2тД откуда

ЙТк т- 1 Е < ЕЕ т =1 / = 0	кт 1  /2т\Д    , т 2 — а 8к 2 п -т 2 т ((т — 1)!^ )р е ^"   6
Дк т- 1 6 Е 1 ЕЕ 8	( 2 У т ,2т____ 1____ ( 4т 2 Е е-2 „ — а = п        ((т — 1)!) 2    к 2

к lnk т-1  /9\т         2

к

1"к т-1  / 9\ т™2

= ЕЕ 8(²) к² ” тАо

\ п(т!)

т=1 / = 0       /’

( 4т 2       -22 -

— а

6 ЕЕ8(²) к2^т-т—

\ п        (т!еА<2т т=1 / = 0

( ^V е *-^—

к lnk т-1  /9\ т         2

6 ^{ЕЕ 8}Р ) к ^{2 т}

\ п        (т/е) ²

т =1 / =0

(#" ’ ) ' е* "

— а

1п^к к т- 1    / ₉ \ т

= ЕЕ 8(2) к-т

( Р,^ е ^^а 6

к т-1п 2 (2к2 -\т (42? аV

6 Е Е8т     е-а) (д2п ).

т =1 / = 0      V ^п /   \ ^к /

Все выражение, кроме последней скобки, от I не зависит. Значит, можно вынести его за внутреннюю сумму и рассмотретв ее отделвно:

^т-1 /Др2   \^{1   т-}1 /  -. „2 \1   ^т-1 / ч .1  т-1,^ .1

£ (42- • ) 6 е () - е ()⁶ е () < 2.

Возвращаясь к сумме по т, с учетом неравенств к 6 2п^: ln п и а < 2 имеем

к

к

, ln ^к         /₉а2      \^т ln^к /

£‘ < £ 16т² ( ^е^ )  6 £ ((16т²)¹ /

==

8п^2: ln² П __к__ ^т____________ е (ln к ) п^а

п

У " .

Легко видеть, что (16т²)^1/т — 0(1), е^{(ln к)} "“ — 0(1), a ^{8 n} 2“y ⁿ 2 ^п — о(1). Таким образом, мы имеем здесь сумму, ограниченную сверху геометрической прогрессией со знаменателем и первым членом, стремящимися к нулю, а это значит, наконец, что и вся сумма стремится к нулю.

Теперь рассмотрим случай т

СЩП 6 с т 6 (т)^т 6 (е '■ ■ Тогда

>

к ln к'

Здесь воспользуемся оценкой

Е"

к   т — 1

£ £ 8к2п—тст т= гД 1=0

in к

1 (с т—т— 11 ) ² п ^аг е " 22 -

— а

к

6 £ т= іД

т— 1

'£ 8к ² п

/ =0

-

^т 2 ^т (б ² ln ² к) ^т п “ ^те— "

-

а

6 £ 8тк2  ■■        “ 2-   ,  6

т= т^г in к

^£ 8 (к - 2е^: т= Д V

2 (ln ² к)п “ е 2"^а

п

у.

Как и в случае с ^ ' достаточно показать, что выражение в скобках стремится к нулю J3       3 ln к с ростом п. Первая его часть ограничена, поскольку к ™ 6 к к ^ 1. Рассмотрим вторую часть и подставим в экспоненту выражение для к:

(ln ² к)п “ ¹ exp

f.

V 2 п “)

„ 2 о 1     /(2 — 2а — е ) п “ !лп\     „ 2 .       ₃_„_ =       2 , _ =

6 (ln ² п)п “ ¹ exp ( -------- “I — (ln ² п)п “ ¹ п¹ “ ² — (ln ² п)п ² .

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

5.4.    Доказательство теоремы 11

Как всегда, зафиксируем е >  0 и возьмем

1пп"| ^{к — (2 —} 4а ^{— е)} -   .

Величина к слегка отличается от своего аналога в теореме 6, и мы совсем скоро поймем, за счет чего это отличие. Но сразу видно, что отличие лишь в константе, а поскольку ограничения в теореме 11 сильнее, чем в теореме 6, снова с запасом выполнено к ^ то и к — о (Дп) (на сам ом деле к — о (^/п)).

Действуем стандартно, доказывая, что МУк ^ то и М2Ук ~ (МУк)2- Разумеется, здесь Ук — число пирамид, как в теореме 10, а не число циклов, как в теореме 6. Тем не менее выкладки будут скорее подобны расчетам из параграфа 5.3.

В параграфе 5.2 мы убедились в том, что свойство МУк ^ то заведомо выполнено, коль скоро 1п(п-)+1п - + 2 ln q ^ то. Практически такое же условие мы проверяли и в параграфе

• 5.3,    причем там были как раз нынешние ограничения на параметры. Однако там не было слагаемого lnр, и именно с этим связано различие между нынешним видом функции к (с вычитаемым 4a) и видом аналогичной функции в 5.3 (с вычитаемым 2a):

ln(np) + ln р +— ln q = ln(np²) +— In q >  (1 — 2a) In n — (1 — 2a--J Inn = — In n ^ to. 2                    2                                        2)2

Займемся вторыми моментами. Здесв тоже имеет место «симбиоз» подходов и оценок из параграфов 5.2 и 5.3. По-прежнему все сводится к доказательству того, что |2 = о(1). И если 51 — в точности то же, что и в 5.2, то 52 оценивается настолько же аккуратнее, чем в 5.2, насколько аккуратнее это было сделано для одноименной величины в 5.3:

к 2m— 2

52 6 ^ ^ ^Скск_—^тств(к,т,1)р^4к^^4—q'²⁽^ l ^—(2k—2'y)-c ^ +i , m=1 1=0

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

Оценим величину B(к,т, Z). Прежде всего назовем главной вершиной пирамиды ту ее вершину, которая не принадлежит циклу. Пусть даны две пирамиды, у каждой из которых к вершин, а также т общих вершин и Z общих ребер. Обозначим множество общих вершин U, множество вершин первой пирамиды, не принадлежащих U, — Ui, множество вершин второй пирамиды, не принадлежащих U, — U2. Пусть Di,D2 — главные вершины наших пирамид. Возможны пять случаев: 1) D1 = D2 E U; 2) D1,D2 E U, но D1 = D2; 3) D1 E U, D2 E U2; 4) D2 E U, D1 E Up 5) D1 E U1, D2 E U2. В первом случае нашим пирамидам отвечают два цикла длины к—1, имеющие т—1 общих вершин и Z —т+1 общих ребер. Ясно, что таких пар пирамид не больше, чем тА(к—1, т—1,Z—т+1). Во втором случае основание первой пирамиды проходит через главную вершину второй пирамиды, а основание второй пирамиды проходит через главную вершину первой пирамиды. Естественно, у этих циклов только т — 2 общие вершины, а число их обттшх ребер лежит в пределах от Z до Z — 5. Поэтому в случае 2) пар пирамид не больше, чем т2(А(к — 1, т — 2,Z) + А(к — 1, т — 2,Z — 1) + А(к — 1, т — 2,Z — 2) + А(к — 1, т — 2,Z — 3) +

+ А(к — 1, т — 2,Z — 4) + А(к — 1, т — 2,Z — 5)).

Рассуждая аналогично, оцениваем число пар циклов в случаях 3) и 4), как

2(к — т)т(А(к — 1, т — 1,Z) + А(к — 1, т — 1,Z — 1) + А(к — 1, т — 1,Z — 2)), а в случае 5) — как

(к — т)²А(к — 1, т, Z) < к²А(к, т, I) 6 к²т!2^т ((к — т^Ск^—1) •

Всякий раз мы считаем А = 0, коль скоро один из параметров отрицательный. К каждой величине А применим оценку из параграфа 5.3:

А(к — 1,т — 2, Z) 6 д(т — 2, т — Z — 2)д 2 (к — т + 1,т — Z — 2) = (т — 2)!С ™- 3 -³ ( (к — т + 1)!С ™--³ ) 2 < < т!2 ^т к ² ( (к — т)!С “1 ^{- 3} ) ² ;

А(к—1,т— 2,Z — 1) 6 д(т—2,т—Z—1)д ² (к—т+1,т—Z—1) = (т—2)!С “- 3 -² ( (к — т + 1)!С ™--² ) 2 < т .> к ((к    - С             ;

А(к — 1, т — 2,Z — 2) 6 д(т — 2, т — Z)g ² (к — т + 1,т — Z) = (т — 2)!С ^^- 3 ^{- 1} ( (к — т + ^С ^- ^{-- 1} ) ² <

<т!2 ^т к ² ((к - т)!С Д^- 1 ) ² ;

А(к - 1,т - 2,Z -3) 6 д(т - 2,т - Z + 1)д ² (к- т + 1,т - Z +1) = (т -2)!С “- 3 ( (к - т + 1)!С ™—^ ) 2 <

<т!2 - к ² ((к - т)!С^ ) 2 ;

А(к-1, т-2, Z-4) 6 д(т-2, т-Z+2)g ² (к—т+1, т-Z+2) = (т-2)!С ™- 3 ⁺¹ ( (к - т + 1)!С^ ⁺¹ ) 2 < < т!2 ^т к ² ((к - т)!С “1⁺¹ ) 2 ;

А(к-1,m-2,Z-5) 6 g(m-2,m-Z+3)g ² (к-m+1,m-Z+3) = (т-2)!С ™- 3 ⁺ 2 ( (к - т + 1)!С^ ⁺² ) ² < < т!2 ^т к ² ( (к - С        ;

А(к - 1, т - 1,Z) 6 д(т - 1, т - Z - 1)д ² (к - т, т - Z - 1) = (т - 1)!С"' 2 ² ( (к - т)!С Д_-^- 2 ) ² < < т!2 ^т ( (к -т)!С Д1- 1 ) 2 ;

А(к - 1, т - 1, Z - 1) 6 д(т - 1, т - Z)g2(к - т, т - Z) = (т - 1)!С™-2-1 ((к - т)!СД-^-11)2 < т .> ((к -т)!СД1-1)2 ;

А(к - 1,т - 1, Z - 2) 6 д(т - 1, т - Z + 1)д ² (к - т,т - Z + 1) = (т - 1)!С ™ ^- 2 ( (к - т)!С Д—2- 1 ) 2 < т .> ( (к -т)!С Д1— 1 ) 2 ;

А(к-1,m-1,Z-m+1) 6 д(т-1,2m-Z-2)g ² (к-m, 2m-Z-2) = (т-1)!С ^ ^т: 2 ^1-3 ( (к - т)!С ^2т _т - 13 ) 2 < т .> ( (к -т)!С 2 ^т _т --1 ³ ) ² .

В итоге

В(к,тД) 6 т!2т((к- т)!)2

(ТГ1 (Лі2т—l—3А   I тД-2 ( (('гт.—І—зХI

( ^т\^Ск—т—1 ) ^{+т к} И^С к—т ) ⁺

। ( т—І—2\^ । ( гчт—l—1\^ । (^чт—І \^ । ( ^т—1+1\^ । / ^т—1+2\ + Ск—т + Ск—т    + Ск—т + Ск—т    + Ск—т

(рті^—І—2 А² । (р^т—1—1 V і (pm-^—l V ² (pmi-l^-1 \²

+ 2кт   Ск—т—1  + Ск—т—1  + Ск—т—1    + к Ск—т—1•

Более того, совсем тривиальна оценка

В(к, 1,Z) 6 к² ((Ц¹)!) .

Вернемся к дроби ^|2:

к 2т—2

І2 = ЕЕ

¹    т=1 1=0

С^к С^к—тС^тВ(к, т, Z) р^{4 к 4 l} V²'^С/ '^{2к 2}-^C '2 ^+l

<

С к Ск_—к (к( ^—^ Р2^к—2q^C2 ^{— (2к— 2)})²

<

к 2 т —2     /     ,. х 2

ЕЕ 4 УтО т =1 1 =0

^(га-2к)!  _в(кт_гг^ _р-і_п-с^+i

(п - 2к + т)! т!((к - 1)!)2

<

к 2 т —2

< Е Е 8к2п т=1 1=0

— т

^В(к,^m,^Z) _р — l _V С + І т!((к - т)!)²

Для дальнейшей оценки, как ив § 5.3, разобьем суммирование на Е’ и У’’, проводя границу на. прежнем т = ^.

Рассмотрим У’. Хорошо видно, что оценка величины В(к,т,1) отлично сокращается с величиной т!((к — т)!)², стоящей в знаменателе. В то же время при текущих ограничениях на т и I справедливы неравенства

2 т—' — 3 / f>2т—' — 1 / f>2т —' — 1 / z^2 m ^с к—т— 1 ^{6 с} к— т +1 ^{6 С} к       ^{6 С} к

■ ( 4т ) ' 6

к 2 т — 1

(2т — 1)!

( 4т ) ' •

т—' —3 / т —' — 2 / гm,—l — 2 / тт—! ( ^2т )

^С к—т ^{6 С} к—т +1 ^{6 С} к      ^{6 С} к      к

к ^т—1

(т — 1)!

( 2т)‘

т—' — 2 / г— — 1 — 1 / тт—І ^с к—т ^{6 с} к—т +1 ^{6 С} к

-

¹ 6 с т— ( ² т ) '

к ^т—1

(т — 1)!

( 2т )‘

т—' — ^с к—т

¹ 6 с ^—— '

¹ 6 с ^—

1 ( 2т у    кт—1  ( 2т у к )    (т — 1)! к ) ’

_гт—'   _гт— '   _гт ( ^2т ) ' ^{к —} ( ^2т ) '

Ск—т 6Ск   6Ск   к 6 т к ’ у-*т—' + 1 / /тт—Щ / тт /2тХ

^С к—т   ^{6 С} к      ^{6 С} к I )

- 1

к ^{т (} 2т V т! к

- 1

к ^{т +1 (} 2т ^у т! к ,

с_к ^к — ' ⁺² 6 с_к ^к— ' ⁺² 6 с_к ^{к +2} ( 2т ) ' 6 ^к —+Е ( 2т ) ' , ^{к т к         к} \ к У     (т + 2)! у к

z-» т—'— 2 / т^т—^ ^с к—т—1 ^{6 с} к — т+1

6с_к^{т —} ' 6с_к^т ( 2т ) 6 ^{к т} ( 2т ) , ^к           у к у     т! у к

т—' — 1 / гт—1

^С к—т—1 ^{6 С} к

-

1_<гт— 1 ( 2 т ) '     к ^{т— 1}   ( 2т ) '

^{6 С к} к ⁶ (т — 1)! к ,

т—' ^с к—т

. 6сг ‘ ^{6 с г (}2т У⁶ т!⁽2т^V ' .

При т > 4 имеем 4т — 2 > 2т + 6. При т = 3 слагаемого А(к — 1,т — 2, 1 — 5) в оценке величины В(к, I, т) нет, так что хватает неравенства 4т — 2 > 2т + 4. При т = 2 нет слагаемых А(к — 1,т — 2, 1 — 5),А(к — 1,т — 2,1 — 4), так что хватает неравенства 4т — 2 > 2т + 2. Так пли иначе

В(к, т,

т!2 ^т ((к —

6 Г

т)!)2    \

16т ²

к ²

((т

(тк ^4т—2 + 6т ² к ^{4 т— 2} + 6тк ^{4 т— 2} + к ^{4 т— 2} ) 6 1)!) ²

( 16т ² ) '

((т — 1)!) ²

• 24т ² к ^{4 т— 2} .

Значит,

У ’ 6 8к ² п

1 В(к, 1, 0) ((к — 1)!) ²

Д= 2 т — 2

+ ЕЕ 8к 2 п т =2 ' =0

-

^т 2 ^т • 24т ² к ^{4 т— 2} ( 162 2 )

((т

1)!) ^{2 Р}

I ^т2    -

' е ² "^а 6

2к ⁴

6 --+

п

Дк 2 т— 2 ,                  ,4

Е ^Е Д192т ² ) т е^ т =2 ' =0  '

т

^v т

т ⁴

^ т ^ ^2т

(^У 6

2к 4

п

+

Дк 2 т— 2 ,                   ,4

Е ^Е І(192т ² ) т е^ ^ т =2 ' =0  '

т

)

^т т ⁴

( m ) '

( ^У

2к ⁴ =--+

п

Дк 2т — 2 ,                ₉,₄

Е ^Е І(192т ⁶ ) т е^ ^

т =2 ' =0  '

т

) ^т (

16ет

к ²

п “ ) 6

k „     „

2к ⁴ ^А 2m - 2         I m 2к ^{4 m}( 16е „V

6 V + у у о192т )те2,“ тғ)  $нT ) ■ m=2 1 = 0

2 т —2            i

Ясно, что ^ ( к ^іб ^к Т^) < 2- откуда <: учетом к = о (/n) получаем 1 =0

ink /                    9i-4\ ^m

S ’ < о(1) + 2 ^y I (192^ 6 ) ™ е 2^--- I = о(1).

m =2 V                 Tl у

Перейдем к S". При т > іПкк ^в °Ц^енках биномиальных коэффициентов, из которых складывается величина В(к,т, I), вынужденно опустим сомножители типа ( 2—■^^l а сохранившееся к 'заменим на. 2к. Например.

(2^)2т—1

(2т - 1)!'

z-y 2т— I —3 / z-y2—— I —3+l+2 __ /-"ү2'т—1      / /-"ү2'т—1           __ /-"ү2'т—1   / /-"ү2'т—1 /

^k——- 1 ⁶ ^к—т—1+l+2    ^k ■ l т+1 ⁶ ^к+2т —2— т +1    ^к+т —1 ⁶ ^2к   ⁶

Далее, z^t 2m—I — 3

^ km — 1

6 к!-к 6 (— ( Г 6 т(е -)2 m .

Аналогично и каждый из оставшихся коэффициентов не превосходит 4fe2 (е2 ln2 fc)т. Получаем k   2m—2

S’’ 6 у у 8k2n m= ink '=0

-

^m 2 ^m • 21^ 2

• 32fe ⁵ ( е ⁴ ln ⁴ k^ ^m p

/ m2

¹ е 2™^Q

6 ^у 8k 2 n m= dr

-

^m 2 ^m ^48т 3 У2& ⁵ ( е ⁴ ln ⁴ k) ^m

2 ^m n^    е 2 ,»

<

k у (2е4 (2 • 104fe10) m m= 4

ln k

) m

]Т (2е4 (2 • 10Д10) m п2“—1 (ln4 к) exp ((1 - 2a - |) ln n)) m m= inkk у (2е4 (2 • 10Д10) 1n2» m= inkk

1 (ln ⁴ k)n ^1—2a— 2 )    = о(1).

Теорема доказана.

6.    Несколько заключительных комментариев Пусть p = n “. Мы зпасм. что при a > 1 выполнено П2(т,р) = 0. а. при a < U2(n,p) = 6 (lS;^) Аналогично при a > 1 выполнено пз(п,р) = 0, а при a < 2 выполнено 4 выполнено ^з(п,р) = ө lnn р . Иными словами, даже при таком грубом взгляде на функцию вероят ности ребра остается некоторый зазор между случаем, когда величина n^(n,p) равна нулю, и случаем, когда она отлична от нуля.

На самом деле, зазор, конечно, можно значительно сократить. Например, без труда доказываются следующие две теоремы.

Теорема 12. Пустъ р = n “, где a <  1. Тогда при всех достаточно больших n выполнено ^2(n,p) > 3.

Теорема 13. Пусть p = n^—“, где a <  |. Тогда при всех достаточно больших n выполнено ^3(n,p) > 4.

Теорема 12 следует из того простого факта, что в ее условиях случайный граф с вероятностью, стремящейся к 1, содержит треугольник, а в теореме 13 роль треугольника выполняет клика на четырех вершинах.

Разумеется, теоремы 12 и 13 можно уточнять. Однако именно это и сделано нами в настоящей работе. Просто нашей целью было найти те области изменения параметров, в которых верхние и нижние оценки по порядку или даже асимптотически совпадают. В больших областях мы эту цель пока не реализовали.

Еще один любопытный факт сформулирован ниже.

Теорема 14. Пусть р = п^-“, г de a >  3. Тогда, либо П3(п,р) = 0, либо для любого е >  0 при всех достаточно больших п выполнено П3(п,р) >  п^3а-2-е.

Теорема 14 дает «условный» результат в том смысле, что при a >  3 уже совсем не очевидно, что пз(п,р) = 0. Понятно, что и нижняя оценка в ней не может быть основана на какой-то явной конструкции графа диаметров с хроматическим числом 4.

Доказательство теоремы 14. Идея доказательства состоит в том, что у случайного графа при нынешних значениях р с большой вероятностью все подграфы на не более п^3а-2-е вершинах имеют хроматические числа не выше трех. Эта же идея использовалась в классических работах Боллобаша (см. [16]- [19], [28], [29]).

Положим t = п3"-2-е и докажем, что

Pn,p (V S, |S| 6 t, x №) 6 3) ^ 1, или, что то же самое,

P n,p (3 S, |S| 6 t, x №) > 3) ^ 0.

Действительно,

P n,p (3 S, |S| 6 t, x №) > 3) = P n,p (3 S, |S| 6 t, x №) > 3 V x E S x №\_W ) 6 3) 6

6 Pn» (3 s E [4, t]  3 S, |S| = s, |E (G| s ) | > 3?) 6 ^£ СПС^р³⁸/² 6

\                                             /8=4

t /              3         \ 8       t                                 tt

£ П^ (y 2 n-3?} = £ ^CnVsn-■)8 6 £ (cnVtn-■У = £ (сп-2У =

8=4 '                       8=4                   8=4

Настоящая работа выполнена при финансовой поддержке гранта РФФИ N 12-01-00683, гранта Президента РФ МД-6277.2013.1 и гранта НШ-2519.2012.1 поддержки ведущих научных школ.