| Успехи математических наук |
|
|
|
|
|
Краткие сообщения Об одном свойстве кратной системы Радемахера и его применении к задачам об уклонении в графах С. В. Асташкинabc, К. В. Лыковde a Самарский национальный исследовательский университет им. академика С. П. Королева b Московский государственный университет им. М. В. Ломоносова c Bahçesehir University, Istanbul, Turkey d Белорусский государственный университет e Институт математики НАН Беларуси
Англоязычная версия:
Russian Mathematical Surveys, 2024, Volume 79, Issue 4, Pages DOI: https://doi.org/10.4213/rm10185e 
Реферативные базы данных:
    1.Распределение сумм вида $\sum_{i,j}c_{i,j}\sigma_i\sigma_j$, где $\sigma_i=\pm 1$, а также оценка их экстремальных и средних значений имеют важное значение в различных разделах математики и ее приложений: от спиновых стекол [1] до геометрии банаховых пространств [2]. В зависимости от задачи коэффициенты $c_{i,j}$ могут быть детерминированными или случайными, равно как и величины $\sigma_i$. В настоящей заметке мы будем предполагать, что $\sigma_i=r_i(t)$, $\sigma_j=r_j(s)$, где $(t,s)\in I^2$, $I=[0,1]$, а $r_k(u)$ – функции Радемахера [3], т. е. $r_k(u):=(-1)^{[2^k u]}$, $k\in\mathbb{N}$, $u\in I$. В качестве $c_{i,j}$ будут выступать величины $r_{i,j}(\omega)a_{i,j}$, где $r_{i,j}$ – функции Радемахера, занумерованные в произвольном порядке парами $(i,j)$. Теорема 1. C универсальными константами для всех $n\in\mathbb{N}$ и $a_{i,j}\in\mathbb{R}$, $1\leqslant i,j\leqslant n$, имеют место двусторонние оценки: Первая эквивалентность в этой теореме означает, что $\{r_i(t)r_j(s)\}_{i,j=1}^\infty$ является системой случайной безусловной сходимости [4] в пространстве $L_\infty(I^2)$. Используя метод декаплинга [5], можно показать, что таким же свойством обладает и система $\{r_i(t)r_j(t)\}_{i\ne j}$ функций одной переменной (хаос Радемахера) в пространстве $L_\infty(I)$. Аналог теоремы 1 верен также для произведений функций Радемахера произвольной кратности. При доказательстве теоремы 1 используется, во-первых, равенство
$$
\begin{equation}
\biggl\|\sum_{1\leqslant i,j\leqslant n}b_{i,j}r_i(u) r_j(v)\biggr\|_{L_\infty(I^2)}=\|B\colon l_\infty^n\to l_1^n\|,
\end{equation}
\tag{1}
$$
справедливое для любой матрицы $B=(b_{i,j})_{1\leqslant i,j\leqslant n}$ (справа стоит норма оператора $B$ из пространства $l_\infty^n$ в пространство $l_1^n$), и, во-вторых, верхняя оценка для математического ожидания $\mathsf{E}\|G_B\colon l_\infty^n\to l_1^n\|$, где $G_B=(g_{i,j}b_{i,j})_{1\leqslant i,j\leqslant n}$ ($g_{i,j}$ – независимые стандартные гауссовские случайные величины), полученная в работе [6]. В частном случае $a_{i,j}=\pm1$ результат теоремы 1 известен достаточно давно (см. [7]).
2.При изучении эффективности аппроксимационных и вычислительных алгоритмов важную роль играет так называемая кат-норма (cut-norm) матрицы $(a_{i,j})_{i,j=1}^n$:
$$
\begin{equation*}
\|(a_{i,j})\|^{\vphantom{\sum}}_{\rm C}:=\max\biggl\{\biggl|\,\sum_{i\in I,j\in J} a_{i,j}\biggr|\colon I,J\subset\{1,2,\dots,n\}\biggr\}.
\end{equation*}
\notag
$$
Как показали Н. Алон и А. Наор [8; лемма 3.1], имеют место неравенства
$$
\begin{equation}
\|(a_{i,j})\|^{\vphantom{\sum}}_{\rm C}\leqslant \|(a_{i,j})\colon l_\infty^n\to l_1^n\| \leqslant 4\|(a_{i,j})\|^{\vphantom{\sum}}_{\rm C}.
\end{equation}
\tag{2}
$$
Это соотношение позволяет обнаружить связь между свойством кратной системы Радемахера из теоремы 1 и некоторыми проблемами экстремальной теории графов. Возьмем полный двудольный граф $K_{n,n}$, припишем каждому его ребру $(i,j)$ вес – вещественное число $a_{i,j}$ и зададимся вопросом отыскания величины
$$
\begin{equation*}
\operatorname{disc}(K_{n,n},\{a_{i,j}\}):=\min_{\omega\in[0,1]}\, \max\biggl\{\biggl|\,\sum_{i\in I,j\in J}r_{i,j}(\omega)a_{i,j}\biggr|\colon I,J\subset\{1,2,\dots,n\}\biggr\}.
\end{equation*}
\notag
$$
Задачи подобного рода известны как задачи об уклонении (discrepancy); см., например, [9], [10]. В нашем примере речь идет о реберной раскраске (расстановке $\pm$-знаков на ребрах). В невесовом случае соответствующая задача для полного графа $K_n$ была решена П. Эрдёшем и Дж. Спенсером [11]. Применяя теорему 1 и учитывая (1) и (2), получаем Другим приложением теоремы 1 является новый метод построения конкретных примеров гиперграфов с весами на вершинах, для которых достигается точность оценок уклонения (по порядку). В качестве вершин в этом случае следует рассматривать позиции в матрице $A=(a_{i,j})_{i,j=1}^n$, а в качестве гиперребер – набор позиций, определяемый подматрицами. Этот метод дополняет известные конструкции (см., например, [12]). Авторы благодарны А. М. Райгородскому и Д. Д. Черкашину за полезное обсуждение вопросов, рассматриваемых в этой заметке. 
Цитирование в формате AMSBIB
\RBibitem{AstLyk24} |
|
||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|