Expose-and-merge exploration and the chromatic number of a random graph

The expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexityn ^O(logn) is described and used to show that the chromatic number of a random graph for any edge probability 0<p<1 falls in the interval $$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$ with probability approaching unity asn→∞.     

Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{\infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c _??(G) =? 1, and give an ${O( \mid V(G)\mid^2)}$ algorithm for their detection. We prove a lower bound for c _?? of expander graphs, and use it to prove three things. The first is that if ${np \geq 4.2 {\rm log}n}$ then the random graph ${G= \mathcal{G}(n, p)}$ asymptotically almost surely has ${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$ , for suitable positive constants ${\eta_{1}}$ and ${\eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{\infty}(G) = \Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 \leq c_{\infty}(G) \leq n/k}$ , where ${n = \mid V(G)\mid}$ and k is the number of vertices of the longest path.     

Precise asymptotics of complete moment convergence on moving average

Let {ξi,-∞i∞} be a doubly infinite sequence of identically distributed-mixing random variables with zero means and finite variances,{ai,-∞i∞} be an absolutely summable sequence of real numbers and X k =∑i=-∞+∞ aiξi+k be a moving average process.Under some proper moment conditions,the precise asymptotics are established for     

Unbounded graph-Laplacians in energy space, and their extensions

Our purpose is to develop computational tools for determining spectra for operators associated with infinite weighted graphs. While there is a substantial literature concerning graph-Laplacians on infinite networks, much less developed is the distinction between the operator theory for the ? ² space of the set V of vertices vs the case when the Hilbert space is defined by an energy form. A network is a triple (V,E,c) where V is a (typically countable infinite) set of vertices in a graph, with E denoting the set of edges. The function c is defined on E. It is given at the outset, symmetric and positive on E. We introduce a graph-Laplacian ??, and an energy Hilbert space $\mathcal{H}_{E}$ (both depending on c). While it is known that ?? is essentially selfadjoint on its natural domain in ? ²(V), its realization in $\mathcal{H}_{E}$ is not. We give a characterization of the Friedrichs extension of the $\mathcal{H}_{E}$ -Laplacian, and prove a formula for its computation. We obtain several corollaries regarding the diagonalization of infinite matrices. To every weighted finite-interaction countable infinite graph there is a naturally associated infinite banded matrix. With the use of the Friedrichs spectral resolution, we obtain a diagonalization formula for this family of infinite matrices. With examples we give concrete illustrations of both spectral types, and spectral multiplicities.     

A concentration function estimate and intersective sets from matrices

We give several sufficient conditions on an infinite integer matrix (d _ij ) for the set R = {Σ _{ij∈α, i>j} d _ij : α ? ?, |α| < ∞} to be a density intersective set, including the cases d _nj = j ⁿ (1 + O(1/n ^1+ε )) and \(0 < d_{nj} = o(\sqrt {n/\log n} )\). For the latter, a concentration function estimate that is of independent interest is applied to sums of sequences of 2-valued random variables whose means may grow as \(\sqrt {n/\log n} \).     

Anderson Polymer in a Fractional Brownian Environment: Asymptotic Behavior of the Partition Function

We consider the Anderson polymer partition function

$$\begin{aligned} u(t):=\mathbb {E}^X\left[ e^{\int _0^t \mathrm {d}B^{X(s)}_s}\right] \,, \end{aligned}$$

where \(\{B^{x}_t\,;\, t\ge 0\}_{x\in \mathbb {Z}^d}\) is a family of independent fractional Brownian motions all with Hurst parameter \(H\in (0,1)\), and \(\{X(t)\}_{t\in \mathbb {R}^{\ge 0}}\) is a continuous-time simple symmetric random walk on \(\mathbb {Z}^d\) with jump rate \(\kappa \) and started from the origin. \(\mathbb {E}^X\) is the expectation with respect to this random walk. We prove that when \(H\le 1/2\), the function u(t) almost surely grows asymptotically like \(e^{\lambda t}\), where \(\lambda >0\) is a deterministic number. More precisely, we show that as t approaches \(+\infty \), the expression \(\{\frac{1}{t}\log u(t)\}_{t\in \mathbb {R}^{>0}}\) converges both almost surely and in the \(\hbox {L}^1\) sense to some positive deterministic number \(\lambda \). For \(H>1/2\), we first show that \(\lim _{t\rightarrow \infty } \frac{1}{t}\log u(t)\) exists both almost surely and in the \(\hbox {L}^1\) sense and equals a strictly positive deterministic number (possibly \(+\infty \)); hence, almost surely u(t) grows asymptotically at least like \(e^{\alpha t}\) for some deterministic constant \(\alpha >0\). On the other hand, we also show that almost surely and in the \(\hbox {L}^1\) sense, \(\limsup _{t\rightarrow \infty } \frac{1}{t\sqrt{\log t}}\log u(t)\) is a deterministic finite real number (possibly zero), hence proving that almost surely u(t) grows asymptotically at most like \(e^{\beta t\sqrt{\log t}}\) for some deterministic positive constant \(\beta \). Finally, for \(H>1/2\) when \(\mathbb {Z}^d\) is replaced by a circle endowed with a Hölder continuous covariance function, we show that \(\limsup _{t\rightarrow \infty } \frac{1}{t}\log u(t)\) is a deterministic finite positive real number, hence proving that almost surely u(t) grows asymptotically at most like \(e^{c t}\) for some deterministic positive constant c.

     

On the Schröder equation and iterative sequences of C r diffeomorphisms in {\mathbb{R}^{N}} space

Let ${U \subset \mathbb{R}^{N}}$ be a neighbourhood of the origin and a function ${F:U\rightarrow U}$ be of class C ^r , r ≥ 2, F(0) = 0. Denote by F ⁿ the n-th iterate of F and let ${0<|s_1|\leq \cdots \leq|s_N| <1 }$ , where ${s_1, \ldots , s_N}$ are the eigenvalues of dF(0). Assume that the Schröder equation ${\varphi(F(x))=S\varphi(x)}$ , where S: = dF(0) has a C ² solution φ such that dφ(0) = id. If ${\frac{log|s_1|}{log|s_N|} <2 }$ then the sequence {S ^?n F ⁿ (x)} converges for every point x from the basin of attraction of F to a C ² solution φ of (1). If ${2\leq\frac{log|s_1|}{log|s_N|} }$ then this sequence can be diverging. In this case we give some sufficient conditions for the convergence and divergence of the sequence {S ^?n F ⁿ (x)}. Moreover, we show that if F is of class C ^r and ${r>\big[\frac{log|s_1|}{log|s_N|} \big ]:=p \geq 2}$ then every C ^r solution of the Schröder equation such that dφ(0) = id is given by the formula $$\begin{array}{ll}\varphi (x)={\lim\limits_{n \rightarrow \infty}} (S^{-n}F^n(x) + {\sum\limits _{k=2}^{p}} S^{-n}L_k (F^n(x))),\end{array}$$ where ${L_k:\mathbb{R}^{N} \rightarrow \mathbb{R}^{N}}$ are some homogeneous polynomials of degree k, which are determined by the differentials d ^(j) F(0) for 1 < j ≤  p.     

Gibbs rapidly samples colorings of G(n, d/n)

Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd?s–Rényi random graph G(n, d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n, d/n) is d(1?o(1)), it contains many nodes of degree of order (log n) / (log log n). The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n, d/n) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature β, the mixing time of Gibbs sampling is at least n ^{1+Ω(1 / log log} n) with high probability. High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including coloring. Almost all known sufficient conditions in terms of number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work we consider sampling q-colorings and show that for every d < ∞ there exists q(d) < ∞ such that for all q ≥ q(d) the mixing time of the Gibbs sampling on G(n, d/n) is polynomial in n with high probability. Our results are the first polynomial time mixing results proven for the coloring model on G(n, d/n) for d > 1 where the number of colors does not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). In previous work we have shown that similar results hold for the ferromagnetic Ising model. However, the proof for the Ising model crucially relied on monotonicity arguments and the “Weitz tree”, both of which have no counterparts in the coloring setting. Our proof presented here exploits in novel ways the local treelike structure of Erd?s–Rényi random graphs, block dynamics, spatial decay properties and coupling arguments. Our results give the first polynomial-time algorithm to approximately sample colorings on G(n, d/n) with a constant number of colors. They extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which there exists an α > 0 such that every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is the union of a tree and at most O(1) edges and where each simple path Γ of length O(log n) satisfies ${\sum_{u \in \Gamma}\sum_{v \neq u}\alpha^{d(u,v)} = O({\rm log} n)}$ . The results also generalize to the hard-core model at low fugacity and to general models of soft constraints at high temperatures.     

Abelian Cayley Graphs of Given Degree and Diameter 2 and 3

Let CC _d,k be the largest possible number of vertices in a cyclic Cayley graph of degree d and diameter k, and let AC _d,k be the largest order in an Abelian Cayley graph for given d and k. We show that \({CC_{d,2} \geq \frac{13}{36} (d + 2)(d -4)}\) for any d= 6p?2 where p is a prime such that \({p \neq 13}\) , \({p \not\equiv 1}\) (mod 13), and \({AC_{d,3} \geq \frac{9}{128} (d + 3)^2(d - 5)}\) for d = 8q?3 where q is a prime power.     

Error estimates in S P for cubature formulas exact for haar polynomials in the two-dimensional case

On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for $ \left\| {\delta _N (f)} \right\|_{S_p^* } On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for with the number of nodes N ∼ 2 ^d , where d → ∞. For N ∼ 2 ^d with d → ∞, it is shown that the norm of δ _N for the formulas under study has the best convergence rate, which is equal to N ^−1/p . Original Russian Text ? K.A. Kirillov, M.V. Noskov, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 1, pp. 3–13.     

On the second eigenvalue and random walks in randomd-regular graphs

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ₂, of (the adjacency matrix of) a randomd-regular graph,G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at thek-th step, for various values ofk. Our main theorem about eigenvalues is that $$E|\lambda _2 (G)|^m \leqslant \left( {2\sqrt {2d - 1} \left( {1 + \frac{{\log d}}{{\sqrt {2d} }} + 0\left( {\frac{1}{{\sqrt d }}} \right)} \right) + 0\left( {\frac{{d^{3/2} \log \log n}}{{\log n}}} \right)} \right)^m $$ for any \(m \leqslant 2\left\lfloor {log n\left\lfloor {\sqrt {2d - } 1/2} \right\rfloor /\log d} \right\rfloor \) , where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than \(2\sqrt {2d - 1} + 2\log d + C'\) with probability 1?n ^?C for constantsC andC′ for sufficiently largen.     

A law of the iterated logarithm for random walk in random scenery with deterministic normalizers

LetX, X _i ,i≥1, be a sequence of independent and identically distributed ? ^d -valued random vectors. LetS _o=0 and \(S_n = \sum\nolimits_{i = 1}^n {X_i } \) forn≤1. Furthermore letY, Y(α), α∈? ^d , be independent and identically distributed ?-valued random variables, which are independent of theX _i . Let \(Z_n = \sum\nolimits_{i = 0}^n {Y(S_i )} \) . We will call (Z _n ) arandom walk in random scenery. In this paper, we consider the law of the iterated logarithm for random walk in random scenery where deterministic normalizers are utilized. For example, we show that if (S _n ) is simple, symmetric random walk in the plane,E[Y]=0 andE[Y ²]=1, then $$\mathop {\overline {\lim } }\limits_{n \to \infty } \frac{{Z_n }}{{\sqrt {2n\log (n)\log (\log (n))} }} = \sqrt {\frac{2}{\pi }} a.s.$$      

A note on Hamiltonicity of uniform random intersection graphs

We consider a collection of n independent random subsets of [m] = {1, 2, . . . , m} that are uniformly distributed in the class of subsets of size d, and call any two subsets adjacent whenever they intersect. This adjacency relation defines a graph called the uniform random intersection graph and denoted by G _n,m,d . We fix d = 2, 3, . . . and study when, as n,m → ∞, the graph G _n,m,d contains a Hamilton cycle (the event denoted \( {G_{n,m,d}} \in \mathcal{H} \)). We show that \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = o(1) \) for d ² nm ^?1 ? lnm ? 2 ln lnm → ?∞ and \( {\mathbf{P}}\left( {{G_{n,m,d}} \in \mathcal{H}} \right) = 1 - o(1) \) for 2nm ^?1 ? lnm ? ln lnm → +∞.     

Maximal Marcinkiewicz multipliers

Let \(\mathcal{M} =\{m_{j}\}_{j=1}^{\infty}\) be a family of Marcinkiewicz multipliers of sufficient uniform smoothness in \(\mathbb{R}^{n}\). We show that the L ^p norm, 1<p<∞, of the related maximal operator

$$M_Nf(x)= \sup_{1\leq j \leq N} |\mathcal{F}^{-1} ( m_j \mathcal{F} f)|(x) $$

is at most C(log(N+2)) ^n/2. We show that this bound is sharp.

     

Entropy and Widths of Multiplier Operators on Two-Point Homogeneous Spaces

In this article we continue the development of methods of estimating n-widths and entropy of multiplier operators begun in 1992 by A. Kushpel (Fourier Series and Their Applications, pp. 49–53, 1992; Ukr. Math. J. 45(1):59–65, 1993). Our main aim is to give an unified treatment for a wide range of multiplier operators Λ on symmetric manifolds. Namely, we investigate entropy numbers and n-widths of decaying multiplier sequences of real numbers \(\varLambda=\{\lambda_{k}\}_{k=1}^{\infty}\), |λ ₁|≥|λ ₂|≥?, \(\varLambda:L_{p}(\mathbb{M}^{d}) \rightarrow L_{q}(\mathbb{M}^{d})\) on two-point homogeneous spaces \(\mathbb{M}^{d}\): \(\mathbb{S}^{d}\), ? ^d (?), ? ^d (?), ? ^d (?), ?¹⁶(Cay). In the first part of this article, general upper and lower bounds are established for entropy and n-widths of multiplier operators. In the second part, different applications of these results are presented. In particular, we show that these estimates are order sharp in various important situations. For example, sharp order estimates are found for function sets with finite and infinite smoothness. We show that in the case of finite smoothness (i.e., |λ _k |?k ^?γ (lnk)^?ζ, γ/d>1, ζ≥0, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \ll d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞, but in the case of infinite smoothness (i.e., \(|\lambda_{k}| \asymp e^{-\gamma k^{r}}\), γ>0, 0<r≤1, k→∞), we have \(e_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d})) \gg d_{n}(\varLambda U_{p}(\mathbb{S}^{d}), L_{q}(\mathbb{S}^{d}))\), n→∞ for different p and q, where \(U_{p}(\mathbb{S}^{d})\) denotes the closed unit ball of \(L_{p}(\mathbb{S}^{d})\).     

Bose–Einstein distribution as a problem of analytic number theory: The case of less than two degrees of freedom

The problem of finding the number and the most likely shape of solutions of the system \(\sum\nolimits_{j = 0}^\infty {{\lambda _j}{n_j}} \leqslant M,\;\sum\nolimits_{j = 1}^\infty {{n_j}} = N\), where λ_j,M,N > 0 and N is an integer, as M,N →∞, can naturally be interpreted as a problem of analytic number theory. We solve this problem for the case in which the counting function of λ_j is of the order of λ^d/2, where d, the number of degrees of freedom, is less than two.     

Rainbow Connection Number, Bridges and Radius

Let G be a connected graph. The notion of rainbow connection number rc(G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85–98, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) proved that for every bridgeless graph G with radius r, ${rc(G)\leq r(r+2)}$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D ^r  = {u}, then G has r?1 connected dominating sets ${ D^{r-1}, D^{r-2},\ldots, D^{1}}$ such that ${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$ and ${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1\leq i \leq r}$ . From the result, we can get that if ${b_i\leq 2i+1}$ for all ${1\leq i\leq r}$ , then ${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1\leq i\leq r}$ , then ${rc(G)= \sum_{i=1}^{r}b_i}$ , the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the number of bridges in G.     

A mean value theorem for the Dedekind zeta-function of a quadratic number field

Let \(K = \mathbb{Q}(\sqrt d )\) be any quadratic number field with discriminantd. ζ _K (s) denotes the Dedekind zeta-function. The purpose of this note is to prove the following asymptotic formula: $$\int\limits_0^T {|\zeta _K ({1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2} + it)|^2 dt = ({6 \mathord{\left/ {\vphantom {6 {\pi ^2 }}} \right. \kern-\nulldelimiterspace} {\pi ^2 }})} \prod\limits_{p/d} {(1 + {1 \mathord{\left/ {\vphantom {1 p}} \right. \kern-\nulldelimiterspace} p})^{ - 1} \cdot R_K^2 \cdot T \cdot \log ^2 T + O_\varepsilon \left\{ {\left| d \right|1 + \varepsilon \cdot T \cdot \log T} \right\},} $$ where the implied constant depends only on ε. HereR _K, denotes the residue of ζ _K (s) ats=1.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

Quasi–Monte Carlo rules for numerical integration over the unit sphere {\mathbb{S}^2}

We study numerical integration on the unit sphere ${\mathbb{S}^2 \subseteq\mathbb{R}^3}$ using equal weight quadrature rules, where the weights are such that constant functions are integrated exactly. The quadrature points are constructed by lifting a (0, m, 2)-net given in the unit square [0, 1]² to the sphere ${\mathbb{S}^2}$ by means of an area preserving map. A similar approach has previously been suggested by Cui and Freeden [SIAM J Sci Comput 18(2):595–609, 1997]. We prove three results. The first one is that the construction is (almost) optimal with respect to discrepancies based on spherical rectangles. Further we prove that the point set is asymptotically uniformly distributed on ${\mathbb{S}^2}$ . And finally, we prove an upper bound on the spherical cap L ₂-discrepancy of order N ^?1/2(log N)^1/2 (where N denotes the number of points). This improves upon the bound on the spherical cap L ₂-discrepancy of the construction by Lubotzky, Phillips and Sarnak [Commun Pure Appl Math 39(S, suppl):S149–S186, 1986] by a factor of ${\sqrt{\log N}}$ . Numerical results suggest that the (0, m, 2)-nets lifted to the sphere ${\mathbb{S}^2}$ have spherical cap L ₂-discrepancy converging with the optimal order of N ^?3/4.