共查询到20条相似文献,搜索用时 31 毫秒
1.
D. W. Matula 《Combinatorica》1987,7(3):275-284
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→∞. 相似文献
2.
Abbas Mehrabian 《Annals of Combinatorics》2012,16(4):829-846
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. 相似文献
3.
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 相似文献
4.
Palle E. T. Jorgensen 《Journal of Applied Mathematics and Computing》2012,39(1-2):155-187
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 ? 2 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 ? 2(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. 相似文献
5.
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 n (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} \). 相似文献
6.
Anderson Polymer in a Fractional Brownian Environment: Asymptotic Behavior of the Partition Function
Kamran Kalbasi Thomas S. Mountford Frederi G. Viens 《Journal of Theoretical Probability》2018,31(3):1429-1468
We consider the Anderson polymer partition function 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.
相似文献
$$\begin{aligned} u(t):=\mathbb {E}^X\left[ e^{\int _0^t \mathrm {d}B^{X(s)}_s}\right] \,, \end{aligned}$$
7.
Marek Cezary Zdun 《Aequationes Mathematicae》2013,85(1-2):1-15
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 n 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 2 solution φ such that dφ(0) = id. If ${\frac{log|s_1|}{log|s_N|} <2 }$ then the sequence {S ?n F n (x)} converges for every point x from the basin of attraction of F to a C 2 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 n (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. 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
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. 相似文献
11.
Joel Friedman 《Combinatorica》1991,11(4):331-362
The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ2, 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. 相似文献
12.
Thomas M. Lewis 《Journal of Theoretical Probability》1993,6(2):209-230
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 2]=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.$$ 相似文献
13.
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 2 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 → +∞. 相似文献
14.
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 is at most C(log(N+2)) n/2. We show that this bound is sharp.
相似文献
$$M_Nf(x)= \sup_{1\leq j \leq N} |\mathcal{F}^{-1} ( m_j \mathcal{F} f)|(x) $$
15.
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}\), |λ 1|≥|λ 2|≥?, \(\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 (?), ?16(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})\). 相似文献
16.
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. 相似文献
17.
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 i , N(D i )] 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. 相似文献
18.
Jürgen G. Hinz 《Monatshefte für Mathematik》1979,87(3):229-239
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. 相似文献
19.
Pawe? Pra?at 《Graphs and Combinatorics》2011,27(4):567-584
A model for cleaning a graph with brushes was recently introduced. Let α = (v
1, v
2, . . . , 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-(vi)={j: vj vi ? E and j < i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let ba(G)=?i=1n max{|N+(vi)|-|N-(vi)|,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}))}. 相似文献
20.
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]2 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 2-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 2-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 2-discrepancy converging with the optimal order of N ?3/4. 相似文献