| Russian Mathematical Surveys |
|
|
|
|
|
Brief communications One property of the multiple Rademacher system and its applications to problems of graph discrepancy S. V. Astashkinabc, K. V. Lykovde a Samara National Research University, Samara, Russia b Lomonosov Moscow State University, Moscow, Russia c Bahcesehir University, Istanbul, Turkey d Belarusian State University e Institute of Mathematics of the National Academy of Sciences of Belarus
Bibliographic databases:
    1.The distribution of sums $\sum_{i,j}c_{i,j}\sigma_i\sigma_j$, where $\sigma_i=\pm 1$, and estimates of their extreme and mean values have great importance in various branches of mathematics and its applications, which range from spin glasses [1] to the geometry of Banach spaces [2]. The coefficients $c_{i,j}$ and the quantities $\sigma_i$ are either deterministic or random, depending on the problem. In the present note we assume that $\sigma_i= r_i(t)$, $\sigma_j=r_j(s)$, where $(t,s)\in I^2$, $I=[0,1]$, and the $r_k(u)$ are the Rademacher functions [3], that is, $r_k(u):=(-1)^{[2^k u]}$, $k\in\mathbb{N}$, $u\in I$. As $c_{i,j}$ we take $r_{i,j}(\omega)a_{i,j}$, where $r_{i,j}$ are the Rademacher functions indexed by pairs $(i,j)$ in an arbitrary order. Theorem 1. For all $n\in\mathbb{N}$ and $a_{i,j}\in\mathbb{R}$, $1\leqslant i,j\leqslant n$, The first equivalence in the theorem means that $\{r_i(t)r_j(s)\}_{i,j=1}^\infty$ is a random unconditional convergence system [4] in $L_\infty(I^2)$. Using the decoupling method (see, for instance, [5]) it can be shown that this property is satisfied for the Rademacher chaos $\{r_i(t)r_j(t)\}_{i\ne j}$ in $L_\infty(I)$. Moreover, an analogue of Theorem 1 also holds for products of Rademacher functions of arbitrary multiplicity. The proof of Theorem 1 is based, first, on the equality
$$
\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}
$$
which holds for each matrix $B=(b_{i,j})_{1\leqslant i,j\leqslant n}$ (the norm on the right is the operator norm from $l_\infty^n$ to $l_1^n$), and, second, on an upper estimate from [6] for the expectation $\mathsf{E}\|G_B\colon l_\infty^n\to l_1^n\|$, where $G_B=(g_{i,j}b_{i,j})_{1\leqslant i,j\leqslant n}$ ($g_{i,j}$ are the independent standard Gaussian random variables). Note also that in the particular case when $a_{i,j}=\pm1$ the result of Theorem 1 has been known for quite a long time (see [7]).
2.The study of the efficiency of some approximative and numerical algorithms is facilitated by the use of the cut-norm of a matrix $(a_{i,j})_{i,j=1}^n$ defined by
$$
\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
$$
According to Alon and Naor (see Lemma 3.1 in [8]),
$$
\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}
$$
This inequality can be used to reveal relationships between the properties of the multiple Rademacher system obtained in Theorem 1 and some problems in extremal graph theory. Let us consider the complete bipartite graph $K_{n,n}$, and associate a weight (a real number) $a_{i,j}$ with each edge $(i,j)$ of this graph. The problem here is to evaluate the quantity
$$
\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
$$
Problems of this type are known as discrepancy problems (see, for example, [9] and [10]). Here, we speak about edge colouring (putting $\pm$ signs on the edges). In the unweighed case, the corresponding problem for the complete graph $K_n$ was solved by Erdős and Spencer [11]. The result below follows from Theorem 1 and (1), (2). Theorem 1 also gives a new method for the construction of concrete examples of vertex-allowbreak weighted hypergraphs for which the discrepancy estimates are (order) sharp. In this case, as vertices one should consider positions in the matrix $A=(a_{i,j})_{i,j=1}^n$, and as hyperedges, sets of positions specified by submatrices. This method supplements the available constructions (see, for example, [12]). The authors are grateful to A. M. Raigorodskii and D. D. Cherkashin for some helpful discussions. 
Citation in format AMSBIB
\Bibitem{AstLyk24} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|