Search

We show that there exists an absolute constant $c > 0$, such that, for any finite set $A$ of quaternions, \[ \max\{|A+A, |AA| \} \gtrsim |A|^{4/3 + c}. \] This generalizes a sum-product bound for real numbers proved by Konyagin and Shkredov., Appeared in SIAM J. Discrete Math. This version corrects some errors from the previous version, and clarifies the analysis

Partly on the basis of heuristic arguments from physics, it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But, beyond intuition, there has been scant rigorous evidence that “practical” algorithms are affected by these phase transitions. In this paper we prove that Walksat, a popular randomized satisfiability algorithm, fails on random $k$-SAT formulas not very far above clause/variable density, where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove that Walksat is ineffective with high probability (w.h.p.) if $m/n>c2^k\ln^2k/k$, where $m$ is the number of clauses, $n$ is the number of variables, and $c>0$ is an absolute constant. By comparison, Walksat is known to find satisfying assignments in linear time w.h.p. if $m/n 0$ [A. Coja-Oghlan and A. Frieze, SIAM J. Comput., 43 (2...

We show that there is an absolute constant $c \leq 156$ such that in every finite family ${\cal F}$ of pseudodiscs in the plane one can find a member $D \in {\cal F}$ such that among all of the pseudodiscs in ${\cal F}$ intersecting $D$ there are at most $c$ pairwise disjoint sets.

Upper bounds of the absolute constant in the convergence rate estimate in the central limit theorem are sharpened in terms of truncated moments. It is shown that the absolute constant in the Osipov inequality does not exceed 2.011.

Let $G$ be a graph with $n$ vertices and independence number $\alpha$. Hadwiger's conjecture implies that $G$ contains a clique minor of order at least $n/\alpha$. In 1982, Duchet and Meyniel proved that this bound holds within a factor 2. Our main result gives the first improvement on their bound by an absolute constant factor. We show that $G$ contains a clique minor of order larger than $.504n/\alpha$. We also prove related results giving lower bounds on the order of the largest clique minor.

We bound the hereditary discrepancy of a hypergraph $\mathcal{H}$ in two colors in terms of its hereditary discrepancy in $c$ colors. We show that $\mathrm{herdisc}(\mathcal{H},2)\leq Kc$ $\mathrm{herdisc}(\mathcal{H},c)$, where $K$ is some absolute constant. This bound is sharp apart from the absolute constant.

A new proof of the absolute convergence of the Spitzer series is given which is based on the Berry–Esseen bound. Moreover, the upper bound is deduced for the sum of the series generated by the absolute values of the terms of the Spitzer series.

The upper bound of the absolute constant in the classical Berry–Esseen inequality for sums of independent identically distributed random variables with finite third moments is lowered to $C\leqslant 0.7056$.

Estimates are presented for the asymptotically exact constants in the estimates of the accuracy of the normal approximation for the distributions of sums of independent identically distributed random variables with finite moments of order $2+\delta$, $0

Presented are practically applicable estimates of the accuracy of the normal approximation for the distributions of sums of independent identically distributed absolutely continuous random variables with finite moments of order $2+\delta$, $0 < \delta\le 1$. The right-hand side of the estimate is the sum of two summands, the first being the Lyapunov fraction with the absolute constant arbitrarily close to the asymptotically exact one, whereas the second summand decreases exponentially fast.

Let $X_1,\ldots,X_n$ be independent random vectors taking values in ${\bf R}^d$ such that ${{\bf E} X_k =0}$ for all k. Write $S=X_1+\cdots+X_n$. Assume that the covariance operator, say $C^2$, of S is invertible. Let Z be a centered Gaussian random vector such that covariances of S and Z are equal. Let ${\cal C}$ stand for the class of all convex subsets of ${\bf R}^d$. We prove a Lyapunov-type bound for $\Delta =\sup_{A\in{\cal C}}|{\bf P}\{S\in A\}-{\bf P}\{Z\in A\}|$. Namely, ${\Delta \le c d^{1/4} \beta}$ with $\beta = \beta_1+\cdots+\beta_1$ and ${\beta_k={\bf E} |C^{-1}X_k|^3}$, where c is an absolute constant. If the random variables $X_1,\ldots,X_n$ are independent and identically distributed and $X_k$ has identity covariance, then the bound specifies to ${\Delta \le c d^{1/4} {\bf E} |X_1|^3/\sqrt{n}}$. Whether one can remove the factor $d^{1/4}$ or replace it with a better one (eventually by 1) remains an open question.

Let G be a graph on n vertices and suppose that at least $\epsilon n^2$ edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on $c k\,{\rm ln}\,k/ \epsilon^2$ vertices are not k-colorable, where c > 0 is an absolute constant. If G is as above for k=2, then most induced subgraphs on $\frac{({\rm ln} (1/\epsilon))^b}{\epsilon}$ are nonbipartite, for some absolute positive constant b, and this is tight up to the polylogarithmic factor. Both results are motivated by the study of testing algorithms for k-colorability, first considered by Goldreich, Goldwasser, and Ron in, [J. ACM, 45 (1998), pp. 653--750], and improve the results in that paper.

Let $\bar V_k (n)$ be the minimum average number of pairwise comparisons needed to find the kth largest of n numbers $(k \geqq 2)$, assuming that all $n!$ orderings are equally likely. D. W. Matula proved that, for some absolute constant c, $\bar V_k (n) - n \leqq ck\ln \ln n$ as $n \to \infty $. In the present paper, we show that there exists an absolute constant $c' > 0$ such that $\bar V_k (n) - n \geqq c'k\ln \ln n$ as $n \to \infty $, proving a conjecture of Matula.

Let $F_p^n (x)$ be an $(n,p)$ binomial distribution function, $\mathfrak{G}$ a set of all infinitely divisible laws and \[ \rho \left( {F_p^n ,\mathfrak{G}} \right) = \mathop {\inf }\limits_{G \in \mathfrak{G}} \mathop {\sup }\limits_x \left| {F_p^n (x) - G(x)} \right| . \] Then, a) $\mathop {\sup }\limits_{0 \leqq p \leqq 1} \rho _1 \left( {F_p^n ,\mathfrak{G}} \right) C(M)n^{ - {2/ 3}} \left( {\log n} \right)^{ - 1/ 4} $, whrer $C_0 $ is an absolute constant $C(M) > 0$ depends on M only, and \[ \begin{gathered} \mathfrak{G}_1^M (a) = \left\{ {G:G \in \mathfrak{G};\int_{ - \infty }^\infty {e^{itx} dG(x) = \exp \left[ {i\gamma t + \mathop \Sigma \limits_{|k| < M} \left( {e^{itk} - 1 } \right)q_k } \right]} ,} \right. \hfill \\ \phantom{ \mathfrak{G}_1^M (a) = \ } \left. {\int_{ - \infty }^\infty {xdG(x) = a,\quad q_k \geqq 0,k = 0, \pm 1 \cdots } } \right\}. \hfill \\ \end{gathered} \]The result ...

Let $F_p^n (x)$ be an $(n,p)$–binomial distribution function and be the set of all infinitely divisible laws. We define \[ \rho \left( {F_p^n ,\mathfrak{G}} \right) = \mathop {\inf }\limits_{G \in \mathfrak{G}} \mathop {\sup }\limits_x \left| {F_p^n (x) - G(x)} \right|. \]Then, \[ \mathop {\sup }\limits_{0 \leqq p \leqq 1} \rho \left( {F_p^n ,\mathfrak{G}} \right) < \frac{{C_0 }} {{\sqrt n }}, \] where $C_0 $ is an absolute constant.