ДОКЛАДЫ АКАДЕМИИ НАУК, 2017, том 475, № 4, с. 365–368
МАТЕМАТИКА
УДК 519.112.74 + 519.176
О ЧИСЛЕ РЁБЕР ОДНОРОДНОГО ГИПЕРГРАФА С ДИАПАЗОНОМ
РАЗРЕШЁННЫХ ПЕРЕСЕЧЕНИЙ
© 2017 г.
А. В. Бобу1, А. Э. Куприянов1, А. М. Райгородский1,2,3,*
Представлено академиком РАН В.В. Козловым 19.01.2017 г.
Поступило 27.02.2017 г.
Настоящая работа посвящена исследованию величины ()
,.
pn kt t,, ,
tt
числа рёбер в k-однородном гиперграфе, обладающем тем свойством, что мощности попарных пересечений
рёбер лежат в отрезке []
12 – максимально возможного
данной величины. Приводятся новые оценки величины ()
DOI: 10.7868/S0869565217220017
HV E(, ), где V – некоторое конечное множество,
Напомним, что гиперграфом называется пара
=
а E – совокупность подмножеств множества V.
Множество V обычно называют множеством вершин,
а совокупность Е – множеством рёбер гиперграфа.
Гиперграф называется k-однородным, если
в каждом ребре содержится ровно k вершин.
В комбинаторике имеется ряд классических
экстремальных задач, связанных с изучением максимального
числа рёбер в однородном гиперграфе
с разрешёнными или запрещёнными пересечениями
рёбер. Мы рассмотрим задачи о максимальном
числе рёбер в гиперграфе в ситуации, когда имеется
ограничение на минимальное и максимальное пересечение
рёбер, а также при условии лишь одного
запрещённого пересечения. Речь идёт о величинах
fn kt
,,
()=∃ ()
∀∈ =
max{:, ,, ,
,
mH VE Vn Em
AE Ak
== =
∀∈ ∩≥
AB EA Bt}
,;
hn kt mH VE Vn Em
AE Ak
=∃ == =
∀∈ =
∀∈ ∩≤
AB EA Bt,| |};
1 Московский государственный университет
им. М.В. Ломоносова
2 Московский физико-технический институт
(государственный университет),
Долгопрудный Московской обл.
3 Институт математики и информатики
Бурятского государственного университета, Улан-Удэ
*E-mail: mraigor@yandex.ru
365
(, ,) max{ :( ,),| |, || ,
|| ,
mn kt mH VE Vn Em
AE Ak
=∃ == =
∀∈
=
∀∈ ∩≠
AB EA Bt,| |}.
Задача об отыскании величины ()
fn kt
,, полностью
решена Р. Алсведе и Л. Хачатряном (см.
[1]). Работа над второй проблемой всё ещё далека
от завершения: имеется довольно простая
нижняя оценка Р. Варшамова и Е. Гилберта (см.
[2, 3]) и ряд блестящих верхних границ, среди
которых можно отметить оценки Левенштейна
(см. [4]) и границу линейного программирования
(см. [5]). Наконец, получение нижних
оценок ()
mn kt
,, значительно продвинуло комбинаторную
геометрию ([6, 7]), а поиск верхних
оценок этой величины привёл к созданию
классического линейно-алгебраического метода
Франкла и Уилсона (см. [8]). Впоследствии появилось
большое количество работ, посвящённых
изучению различных ситуаций относительно
параметров k и t при n→∞ (см. [7, 9–13]).
Перейдём к формулировке нашей задачи. Она
будет состоять в отыскании величины pn kt12t,, ,() –
максимального числа рёбер в k-однородном гиперграфе
на n вершинах, все рёбра которого пересекаются
не менее чем по t1 элементам и не более
чем по t2 элементам, ≤≤ ≤
Стр.1
366
12
,
БОБУ и др.
Можно сформулировать данную проблему в терминах
теории кодирования: разрешение определённого
диапазона пересечений tt
[] эквивалентно
условию, что все хэмминговы расстояния
между кодовыми словами веса k заключены
в отрезке () ()
2,2.kt kt
Gn kt tV nk En kt t12 у которого
,,,, ,, ,, ,
12 = () ()
(, ,, ){ ,} :( ,) [, ].
ni
Vnkx xx
xx k
xy xy
1
n
En ktttt
x
()== …∈
+…+=
,, ,: 0,1,
,
{ () {}
1
12=∉12
{}
}
Напомним, что для произвольного графа G числом
независимости G
α ()
Gn kt12t,, ,,
α() называется максимальная
мощность множества вершин, никакие две
из которых не соединены ребром. В такой постановке
становится очевидно, что наша задача
эквивалентна поиску величины ()
поскольку последняя просто совпадает с искомой
pn kt t,, ,
()Наконец, дополнительной мо12
тивацией
для изучения поставленной проблемы
служат недавние работы о хроматическом числе
пространства с запрещёнными равнобедренными
треугольниками (см. [14, 15]).
pn kt t12
На сочетании этих двух результатов основана
идея нижней оценки величины ()
вые доказанной в работе [14].
pn kt t,, ,,
Те о рем а 3. Пусть ≤k n
2. Тогда
()≥−
+
,,,1.
tr
CC1
tr
+
it2
=+
∑1
k
jt tr ik
tr i
=++−
+
∑
1
,}
11
Перейдём к верхним оценкам. Для начала отметим,
что существуют два соотношения:
pn kt tpnk tk fn kt
pn kt tpnk t hnk t
,, ,,,,
12 22
≤=
Если значение величины fn kt
,,
1
рого N
r∈∪{0}
()
kt1 12
−+ + −
+
t1
r nk t1 12
1
1
()
≤< −+ + −
t1
r
1.
() () ()
() () ()
≤=
,, ,,,0,,,.
12 11
,, ,
() в точности известно,
выполняется следующее утверждение.
Те о р е м а 4. Пусть kt n
2 −≤ и для некотоmax{,}
min{
1+
1
22
−−
−−
1
1
r
CC CC 1
tr
j
tr j
1+−
kt r
ij
−−
−
1
nt r
kt r
nk r
kt ri j
−−
−− −+
12 вперописать
нашу задачу на языке теории дистанционных
графов. А именно, рассмотрим граф
() ()
−− 21 Кроме того, можно
1. ИЗВЕСТНЫЕ ОЦЕНКИ
pn kt t,, ,.
Перейдём к известным оценкам величины
()
нам потребуется сформулировать теорему Алсведе–Хачатряна,
которая даёт точное значение величины
()
12 Начнём с нижних оценок. Для этого
fn kt
r∈∪{0}
kt
Тогда
та, которая оценивает снизу величину ()
2 −≤ и для некоторого
Те о р ем а 1. Пусть kt n
N
() ()
−+ + −
+
12
t
r nk t
1
1
12
≤< −+ + −
t
r
причём при r = 0 формально полагаем, что − =∞t
r
1
fn kt
,,
() ∑=
=
ir
Те о рем а 2. Пусть kt n
C
hnk t
,,
()≥−
−
n
k
it
k
=+1 ∑ CC −
k
i
nk
ki
2 −≤ . Тогда
1.
(1)
min{2, }
rk t
−
CC
tr
ti
+
+
22.
nt r
kt i
−−
−−
1,
.
,, , и границу Варшамова–Гилберhnk
t,, .
Тогда
pn kttC C
() ∑≤
=
12
,,,.
ir
tr
ti
1 22
1
+
+
−−
−−
1
1
nt r
kt i
Обратимся теперь ко второму соотношению. Для
того чтобы его применить, нам потребуются некоторые
результаты теории кодирования. Первый из
них – граница Левенштейна – доказан в работе [4]
и звучит следующим образом.
Те о рем а 5. Пусть ≤k n
2 и
()
4
ij
−
02(),0 ij k
()
() ()
≤− ≤− ≤+ ≤
kj
− + +
ij nk
22
2
4 −+ +− −>0,
ij
nk j kt i
ДОКЛАДЫ АКАДЕМИИ НАУК том 475 № 4 2017
2,
min{2, −rk t1}
Стр.2
О ЧИСЛЕ РЁБЕР ОДНОРОДНОГО ГИПЕРГРАФА…
тогда справедливо следующее неравенство:
() ()
pn kt12t hnk t≤≤ Ч
CC−
,, ,, , 2
Ч 22
()
kj
ij
()
4
−
− 2
() () 2
− + +
() ()
−
Cn
+
k
kj
ij /2
nk
ij
− /2
4 −+ +− −
kt
ij
nk j kt i
Важной оценкой является и граница линейного
программирования, полученная в работе [5].
Те о рем а 6. Введём функции
()
Hx xx xx
gx H
22 2
=− −− −
log1 log(1);
()
()
0 12
= −−
2
Пусть ≤ ′ ≤ ′ ≤ ′ ≤tt k
nn
21 22 2
lim log, ,,
→∞
≤
pn kn tn tn
n
≤ lim log, ,
→∞
0, если tk ,
2
2
(),,
2
gu если tk2
′ ≤ ′
′ > ′
2
где () ()=− ′− ′ + ′′ − ′+
uk tt tk22 21.22 2
Наконец, с помощью простой модификации
теоремы Франкла–Уилсона, несложно получить
следующую границу.
венство:
Те о р е м а 7. Справедливо следующее нераtt
pn
kt tC,,,.
q
() ∑≤
=
21
−
12
0
2. ФОРМУЛИРОВКИ РЕЗУЛЬТАТОВ
Нами были получены новые нижняя и верхняя
оценки величины ()
0,01≤τ≤≤ ≤−τ – целые числа. Тогда
pn kt t CC
tr k
где
−−
CC −τ−− +
1
=∑∑
=τ
i
t
1−1
jr ik
ri
=ττ+ +−
τ+
,}
max{,}
min{
τ+r
j CC C
rj
r
τ+ −
kr
ij
−τ−
−
()≥
12
,,,1,
CC
τ+
τ+
22
12
r
r
−τ−
−τ−
+
nr
kr
−
nk r
kr ij
ДОКЛАДЫ АКАДЕМИИ НАУК том 475 № 4 2017
,
Рис. 1. Сравнение оценок теорем 3–9 при k' = 0,5
и t'1 = 0,1.
Т е о р е м а 8. Пусть ≤k n
2 и tr k0,01≤τ≤≤ ≤−τ
pn kt12t,, ,.
n
q
(2)
C2 =
hnk nt n
n
′′
11
2
1
2,
тогда
() ()≤
′′ ′
x
.
.
C2 =
= ∑
=+
k
it2 1
jr ik
ri
=ττ+ +−
τ+
∑
,}
max{,}
min{
CC CC ,
τ+r
j
r
τ+ −
rj
kr
ij
−τ−
−
1
nk r
kr ij
−−
−τ−− +
причём при τ= t1 формально полагаем =C 0.
Идейно доказательство устроено следующим
образом. На первом шаге мы берём конструкцию
из доказательства теоремы 1 так, чтобы попарные
пересечения её представителей были не меньше τ.
Затем с помощью алгоритма теоремы 2 мы удаляем
некоторые множества таким образом, чтобы пересечения
оставшихся лежали в отрезке []
tt
ло. Введём следующие обозначения:
nn tr k kt r
nt r t tt
01 0
=− −2;
′ = −−
−− ′ = −
1
1
2 ;
() 11
2
12 tr
k
n
n→∞n
n0
0,
n gu если tk
если tk
(),,′ > ′2
′ ≤ ′2
2
00
00 .
= −−
0
22 2
2
00 00
Hx xx xx
gx H
()=− −− −
;
uk tt tk
C
CC1
C 1+2
+
tr
nk
r
−
=− ′ − ′ + ′′ − ′ +
=
0
2( )2 (2 1);
lim 1 log,
log(1)log(1);
x
nt r2 ;
−−
21
1
12
,.
Сформулируем новую верхнюю оценку.
Те о р ем а 9. Пусть rk t
0≤< 2− – целое чис367
Стр.3