On measure concentration in graph products (Q2809697)

Let \([k]\) denote the set \(\{0,1,2,\dots,k-1\}\). The author defines a metric \(d\) on \([k]\) in terms of a graph \(G\) with vertex set \([k]\) such that \(d(a,b)\) is the distance (shortest path) between the vertices \(a\) and \(b\). If \(d_i\) is such a metric induced by a graph \(G_i\), then the author states that the \(l_1\)-type metric \(d\) defined on the product space \([k]^n\) defined by \(d(a,b)=\sum\limits_{i=1}^nd_i(a_i,b_i)\) can be reconstructed from the Cartesian product of the graphs \(G_i;\, 1\leq i\leq n\).NEWLINENEWLINENEWLINEThe \(t\)-neighbourhood of a subset \(A\) of \(V(G)\), with \(|A|\geq \frac{|V|}{2}\), is the set \(A_t=\{a\in V:d(a,b)\leq t\mathrm{ for some }b\in B\}\). In case of the \(n\)-fold products of graphs of order \(k\), the lower bound for the \(t\)-neighbourhood has already been determined in certain studies done earlier that \(|A_t|\geq |B_k^{(n)}(r+t)\), where \(B_k^{(n)}(r)=\{a\in [k]^n: \sum_ia_i\leq r\}\).NEWLINENEWLINENEWLINEIn this paper, the above mentioned lower bound is interpreted in terms of probability. Let \(X_1,X_2,\ldots X_n\) be independent copies of a random variable, which is uniformly distributed over \([k]\) and let \(Y_i=X_i-E(X_i)\). Let \(\tau(b,\sigma^2)\) be a random variable which assumes the values \(\{-b,0,b\}\) with probabilities \(P(\tau=-b)=P(\tau=b)=\frac{\sigma^2}{2b^2}\) and \(P(\tau=0)=1-\frac{\sigma^2}{b^2}\). Then, the author proves the following three lemmas.NEWLINENEWLINENEWLINE (i) For any real \(h\), \(E(Y-h)_+^5=E(\tau-h)_+^5\), where \(\tau=\tau(\max Y, \mathrm{Var }Y)\).NEWLINENEWLINENEWLINE {(ii)} If \(\frac{\sigma^2}{b^2}\geq \frac{1}{3}\), then for real \(h\), \(E(\tau-h)_+^5\leq E(\eta-h)_+^5\), where \(\eta\) is a normal random variable with mean 0 and variance \(\sigma^2\).NEWLINENEWLINENEWLINE (iii) For any \(h<t\), \(E(S_n-h)_+^5\leq E(Z_n-h)_+^5\), where \(Z_n=\eta_1+\eta_2+\dots\eta_n\) such that \(\mathrm{Var } Z_n=\mathrm{Var }S_n=n\sigma^2\).NEWLINENEWLINENEWLINE In view of these lemmas, the author proves in the main theorem that if \(S_n=\sum\limits_{i=1}^{n}Y_i\), the author proves that NEWLINE\[NEWLINEP(S_n\geq t)\leq cI\left(\frac{t}{\sigma\sqrt{n}}\right)\leq \frac{c}{\sqrt{2\pi}}\frac{\sigma\sqrt{n}}{t}\exp\left\{ -\frac{t^2}{2n\sigma^2}\right\},NEWLINE\]NEWLINE where \(I(x)\) is the survival function of a standard normal variable, \(c=\frac{5!e^5}{5^5}\) and \(\sigma^2=\frac{\mathrm{Var }(S_n)}{n}\).NEWLINENEWLINENEWLINEThe article is well-written and the results proved are really nice and mathematically sound. The author deserves much appreciation for the approach in presenting the content in a remarkable way.