Доклады Российской академии наук. Математика, информатика, процессы управления. T. 495, Номер 1, 2020

  1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 495, № 1, 2020

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 495, № 1, стр. 74-77

О РАЗБИЕНИИ МНОЖЕСТВ НА ЧАСТИ МЕНЬШЕГО ДИАМЕТРА

А. М. Райгородский 1, 2, 3, 4, *

1 Московский физико-технический институт (национальный исследовательский университет)
Долгопрудный, Московская обл., Россия

2 Московский государственный университет имени М.В. Ломоносова
Москва, Россия

3 Кавказский математический центр Адыгейского государственного университета
Майкоп, Россия

4 Институт математики и информатики Бурятского государственного университета
Улан-Удэ, Россия

* E-mail: mraigor@yandex.ru

Поступила в редакцию 05.07.2020
После доработки 05.07.2020
Принята к публикации 17.09.2020

Полный текст (PDF)

Аннотация

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

Ключевые слова: разбиение, раскраска, точечные множества в пространствах, граф диаметров

Настоящая работа посвящена одному важному варианту классической проблемы Борсука о разбиении множеств на части меньшего диаметра (см. [1]).

Пусть $b \in (0,\;1]$, $n \in \mathbb{N}$. Определим величину $\chi (n,b)$ как минимальное количество частей диаметра строго меньше b, на которые может быть разбито произвольное множество диаметра 1 в пространстве ${{\mathbb{R}}^{n}}$. При b = 1 получаем в точности классическое число Борсука, про которое известно, что $\chi (1,\;1) = 2$, $\chi (2,\;1) = 3$, $\chi (3,\;1) = 4$,

(1)
$\mathop {\left( {\mathop {\left( {\frac{2}{{\sqrt 3 }}} \right)}\nolimits^{\sqrt 2 } + o(1)} \right)}\nolimits^{\sqrt n } \leqslant \chi (n,1{\text{)}} \leqslant \mathop {\left( {\sqrt {\frac{3}{2}} + o(1)} \right)}\nolimits^n $
(см. [1, 2]). При малых n и различных b множество результатов и ссылок можно найти в [1] и [3].

Нас будет интересовать случай, когда $n \to \infty $, а $b = b(n)$. В этом случае все известные верхние оценки экспоненциальны по n. Например, из работы Роджерса об упаковках сферических шапочек на сфере (см. [4]) следует неравенство

$\chi (n,b)\,\,\mathop { \leqslant \left( {\frac{{\sqrt 2 }}{b} + o(1)} \right)}\nolimits^n .$

Величину $\tfrac{{\sqrt 2 }}{b}$ можно уменьшить, применяя технику из работы [5].

Намного тоньше устроены нижние оценки. Грубо говоря, мы скоро увидим, что если $b(n) \leqslant c$ < < 1 при всех $n$, то и эти оценки экспоненциальны. Если же $b(n) \to 1$ при $n \to \infty $, то оценки становятся субэкспоненциальными, постепенно убывая (с ростом скорости стремления функции b к единице) до вида левой части оценки (1), т.е. асимптотической константы в степени $\sqrt n $. Аккуратным формулировкам соответствующих новых результатов и будет посвящена наша дальнейшая работа.

Справедлива следующая

Теорема 1. Пусть k = k(n) – произвольная функция со значениями во множестве $\left\{ {1,\; \ldots ,\;\tfrac{n}{2}} \right\}$. Рассмотрим для каждого n максимальное целое число a = a(n), с которым $\sqrt {1 - \tfrac{{a(n)}}{{k(n)}}} \geqslant b(n)$. Пусть $m(n,r,s)$ – максимальная мощность совокупности r-элементных подмножеств множества ${{\mathcal{R}}_{n}} = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}$, в которой каждые два множества имеют не менее $s$ общих элементов. Тогда

$\chi (n,b(n)) \geqslant \frac{{C_{n}^{{k(n)}}}}{{m(n,k(n),a(n) + 1)}}.$

Величина $m(n,r,s)$ найдена при всех $n$, r, s. Сформулируем для полноты картины соответствующий результат (см. [6]).

Теорема 2 (П. Франкл, Р.М. Уилсон, Р. Алсведе, Л. Хачатрян). Пусть $2r - n < s$, $1 \leqslant s \leqslant r \leqslant n$. Пусть, кроме того, при $0 \leqslant i \leqslant \tfrac{{n - s}}{2}$ и $i \leqslant r - s$ определена совокупность

$\begin{gathered} {{\mathcal{M}}_{i}}(n,r,s) = \\ = \{ M \subseteq {{\mathcal{R}}_{n}}{\text{:}}\;\left| M \right| = r,\;\left| {M \cap {\text{\{ }}1, \ldots ,s + 2i{\text{\} }}} \right| \geqslant s + i\} , \\ \end{gathered} $
т.е. ${{\mathcal{M}}_{i}}(n,r,s)$ – это совокупность всех возможных r-элементных подмножеств множества ${{\mathcal{R}}_{n}}$, у которых не менее s + i элементов взято из {1, ..., ..., $s + 2i{\text{\} }} \subseteq {{\mathcal{R}}_{n}}$. Если при некотором $l \in \mathbb{N} \cup {\text{\{ }}0{\text{\} }}$ выполнено соотношение
$(r - s + 1)\left( {2 + \frac{{s - 1}}{{l + 1}}} \right) \leqslant n < (r - s + 1)\left( {2 + \frac{{s - 1}}{l}} \right),$
то $m(n,r,s) = \left| {{{\mathcal{M}}_{l}}(n,r,s)} \right|$ $\left( {\,\,\,\,\,\tfrac{{}}{{}}} \right.$мы считаем, что $\tfrac{{s - 1}}{l} = \infty $, коль скоро l = 0 $\left. {\tfrac{{}}{{}}\,\,\,\,} \right)$.

Теорема 1 допускает уточнение.

Теорема 3. Пусть ${{k}_{{ - 1}}} = {{k}_{{ - 1}}}(n)$, ${{k}_{0}} = {{k}_{0}}(n)$, ${{k}_{1}} = {{k}_{1}}(n)$ – произвольные функции со значениями во множестве ${{\mathcal{R}}_{n}}$, удовлетворяющие соотношениям

$\begin{gathered} {{k}_{{ - 1}}}(n) + {{k}_{0}}(n) + {{k}_{1}}(n) = n, \\ {{k}_{{ - 1}}}(n) + {{k}_{1}}(n) \leqslant \frac{n}{2},\quad {{k}_{{ - 1}}}(n) \leqslant {{k}_{1}}(n). \\ \end{gathered} $

Рассмотрим для каждого $n$ максимальное целое число $a = a(n)$, с которым

$\sqrt {\frac{{{{k}_{1}}(n) + {{k}_{{ - 1}}}(n) - a(n)}}{{{{k}_{1}}(n) + 3{{k}_{{ - 1}}}(n)}}} \geqslant b(n).$

Пусть $f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)$ – максимальная мощность совокупности (–1, 0, 1)-векторов в ${{\mathbb{R}}^{n}}$, в которой каждый вектор имеет ровно ${{k}_{i}}$, $i \in {\text{\{ }} - {\kern 1pt} 1,\;0,\;1{\text{\} }}$, координат величины i и в которой скалярное произведение любых двух векторов не меньше s. Тогда

$\chi (n,b(n)) \geqslant \frac{{C_{n}^{{{{k}_{1}}(n)}}C_{{n - {{k}_{1}}(n)}}^{{{{k}_{{ - 1}}}(n)}}}}{{f(n,{{k}_{{ - 1}}}(n),{{k}_{0}}(n),{{k}_{1}}(n),a(n) + 1)}}.$

Суть уточнения в том, что при ${{k}_{{ - 1}}}(n)$, тождественно равной нулю, мы получаем в точности теорему 1: когда у векторов остаются только нулевые и единичные координаты, их скалярное произведение равно мощности пересечения множеств их единичных координат. Конечно, можно было бы давать еще более громоздкие обобщения, добавляя все новые и новые величины координат. Однако проблема в том, что даже величина $f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)$ в общем случае с трудом поддается оцениванию, но для нее оценки все же есть и они позволяют в ряде ситуаций уточнять теорему 1. Для других подобных величин известно крайне мало, и мы не видим смысла рассматривать их в текущем контексте.

Что касается оценок величины $f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)$, то тут есть, во-первых, гипотеза о ее точном значении, сформулированная в работе [7]. Также есть ряд недавних результатов Франкла и Купавского (см. [8]) и смежных результатов разных авторов (см. [9–15]). Но одним из наиболее эффективных инструментов здесь по-прежнему остается линейно-алгебраический метод (см. [1, 2, 12–15]). С его помощью можно доказать следующую теорему.

Теорема 4. Пусть даны все параметры из формулировки теоремы 3. Пусть $q = q(n)$ – минимальное число, равное степени простого, с которым выполнено неравенство ${{k}_{{ - 1}}}(n) + {{k}_{1}}(n) - q(n) \leqslant a(n)$. Тогда

$f(n,{{k}_{{ - 1}}}(n),{{k}_{0}}(n),{{k}_{1}}(n),a(n) + 1) \leqslant \sum\limits_{(i,j) \in \mathcal{A}} {C_{n}^{i}} C_{{n - i}}^{j},$
где

$\mathcal{A} = {\text{\{ }}(i,j){\text{:}}\;i + 2j \in {\text{\{ }}q(n) - 2,q(n) - 1{\text{\} \} }}.$

Можно произвести достаточно стандартный асимптотический анализ оценок из теорем 1 и 3. Аккуратная оптимизация затруднена, в том числе из-за того, что в теореме 4 оценка зависит от распределения простых в натуральном ряде. Тем не менее, сравнительно легко понять, что если $b(n) \leqslant c < 1$, где c – константа, то обе теоремы дают оценки вида ${{(C + o(1))}^{n}}$, где C > 1. Напротив, обе оценки становятся субэкспоненциальными, коль скоро $b(n) \to 1$ при $n \to \infty $. А если $b(n) = 1$, то обе оценки практически вырождаются, становясь равными n по порядку. Однако мы знаем неравенство (1), и это подсказывает нам, что теоремами 1 и 3 все не исчерпывается. Ниже мы приведем еще две новые теоремы, которые как раз работают в случаях, когда b(n) достаточно быстро стремится к единице.

Теорема 5. Пусть d = d(n) и a = a(n) таковы, что $d = 4q$, где q = q(n) – степень простого,

$n \geqslant C_{{d(n) - \left\lceil {a(n)/2} \right\rceil }}^{2},\quad \sqrt {1 - \frac{{{{a}^{2}}(n)}}{{{{d}^{2}}(n)}}} \geqslant b(n).$

Тогда

$\chi (n,b(n)) \geqslant \frac{{{{2}^{{d(n) - \left\lceil {a(n)/2} \right\rceil - 2}}}}}{{\sum\limits_{i = 0}^{q(n) - a(n) - 1} {C_{{d(n) - \left\lceil {a(n)/2} \right\rceil - 1}}^{i}} }}.$

Например, если $b(n) = 1 - \tfrac{1}{{\sqrt n }}$, то $d(n) = \Theta (\sqrt n )$, a(n) = $\Theta (\sqrt[4]{n})$, и оценка теоремы 5 становится похожа на нижнюю оценку в (1). Чем ближе b(n) к тождественной единице, тем ближе a(n) к нулю. При a(n) = 0 оценка теоремы 5 при огрублении в стиле неравенства (1) превращается с учетом формулы Стирлинга и плотности простых в натуральном ряде в неравенство

$\begin{gathered} \chi (n,1) \geqslant \mathop {\left( {2\mathop {\left( {\frac{1}{4}} \right)}\nolimits^{1/4} \mathop {\left( {\frac{3}{4}} \right)}\nolimits^{3/4} + o(1)} \right)}\nolimits^n = \\ = \;\mathop {\left( {\mathop {\left( {2\mathop {\left( {\frac{1}{4}} \right)}\nolimits^{1/4} \mathop {\left( {\frac{3}{4}} \right)}\nolimits^{3/4} } \right)}\nolimits^{\sqrt 2 } + o(1)} \right)}\nolimits^{\sqrt d } . \\ \end{gathered} $

Константа под знаком субэкспоненты меньше, чем константа в нижней оценке из (1). Улучшение, приводящее к той же константе, дает последняя теорема.

Теорема 6. Пусть d = d(n), q = q(n) и a = a(n) таковы, что q – степень простого, $q(n) \leqslant \tfrac{{d(n)}}{2}$,

$n \geqslant C_{{d(n) + 1}}^{2},\quad \sqrt {1 - \frac{{{{a}^{2}}(n)}}{{{{q}^{2}}(n)}}} \geqslant b(n).$

Тогда

$\chi (n,b(n)) \geqslant \frac{{{{2}^{{q(n) - a(n) - 1}}}C_{{d(n)}}^{{q(n)}}}}{{\sum\limits_{(i,j) \in \mathcal{A}} {C_{{d(n)}}^{i}} C_{{d(n) - i}}^{j}}},$
где

$\mathcal{A} = {\text{\{ }}(i,j){\text{:}}\;i + 2j \in {\text{\{ }}q(n) - a(n) - 2,q(n) - a(n) - 1{\text{\} \} }}.$

Список литературы

  1. Raigorodskii A.M. Cliques and cycles in distance graphs and graphs of diameters // Discrete Geometry and Algebraic Combinatorics // AMS, Contemporary Mathematics. 2014. V. 625. P. 93–109.

  2. Боголюбский Л.И., Райгородский А.М. Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками l1 и l2 // Матем. Заметки. 2019. Т. 105. № 2. С. 187–213.

  3. Филимонов В.П. О покрытии множеств в ${{\mathbb{R}}^{m}}$ // Матем. сб. 2014. Т. 205. № 8. С. 95–138.

  4. Rogers C.A. Covering a sphere with spheres // Mathematika. 1963. V. 10. P. 157–164.

  5. Bourgain J., Lindenstrauss J. On covering a set in ${{\mathbb{R}}^{d}}$ by balls of the same diameter / Geometric Aspects of Functional Analysis. J. Lindenstrauss and V. Milman, eds. Lecture Notes in Math. 1469, Berlin: Springer-Verlag, 1991. P. 138–144.

  6. Ahlswede R., Khachatrian L.H. The complete intersection theorem for systems of finite sets // Europ. J. Combin. 1997. V. 18. P. 125–136.

  7. Райгородский А.М., Харламова А.А. О совокупностях (–1, 0, 1)-векторов с запретами на величины попарных скалярных произведений / Труды по векторному и тензорному анализу. Т. 29. М.: Изд-во МГУ, 2013. С. 130–146.

  8. Frankl P., Kupavskii A. Erdős–Ko–Rado theorem for ${\text{\{ }}0, \pm 1{\text{\} }}$-vectors // J. Comb. Theory Ser. A. 2018. V. 155. P. 157–179.

  9. Frankl P., Kupavskii A. Incompatible intersection properties // Combinatorica. 2019. V. 39. № 6. P. 1255–1266.

  10. Kupavskii A. Degree versions of theorems on intersecting families via stability // J. Comb. Theory Ser. A. 2019. V. 168. P. 272–287.

  11. Купавский А.Б., Сагдеев А.А. Теория Рамсея в пространстве с чебышевской метрикой // УМН. 2020. Т. 75. № 5 (455). С. 191–192.

  12. Бобу А.В., Куприянов А.Э., Райгородский А.М. Об одном обобщении кнезеровских графов // Матем. заметки. 2020. Т. 107. № 3. С. 351–365.

  13. Raigorodskii A.M., Sagdeev A.A. On a Frankl–Wilson theorem and its geometric corollaries // Acta Math. Univ. Comenianae. 2019. V. 88. № 3. P. 1029–1033.

  14. Райгородский А.М., Шишунов Е.Д. О числах независимости некоторых дистанционных графов с вершинами в {–1, 0, 1}n // ДАН. 2019. Т. 485. № 3. С. 269–271.

  15. Пушняков Ф.А., Райгородский А.М. Оценка числа ребер в особых подграфах некоторого дистанционного графа // Матем. заметки. 2020. Т. 107. № 2. С. 286–298.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал