ﻻ يوجد ملخص باللغة العربية
The d-dimensional Hamming torus is the graph whose vertices are all of the integer points inside an a_1 n X a_2 n X ... X a_d n box in R^d (for constants a_1, ..., a_d > 0), and whose edges connect all vertices within Hamming distance one. We study the size of the largest connected component of the subgraph generated by independently removing each vertex of the Hamming torus with probability 1-p. We show that if p=lambda / n, then there exists lambda_c > 0, which is the positive root of a degree d polynomial whose coefficients depend on a_1, ..., a_d, such that for lambda < lambda_c the largest component has O(log n) vertices (a.a.s. as n to infty), and for lambda > lambda_c the largest component has (1-q) lambda (prod_i a_i) n^{d-1} + o(n^{d-1}) vertices and the second largest component has O(log n) vertices (a.a.s.). An implicit formula for q < 1 is also given. Surprisingly, the value of lambda_c that we find is distinct from the critical value for the emergence of a giant component in the random edge subgraph of the Hamming torus. Additionally, we show that if p = c log n / n, then when c < (d-1) / (sum a_i) the site subgraph of the Hamming torus is not connected, and when c > (d-1) / (sum a_i) the subgraph is connected (a.a.s.). We also show that the subgraph is connected precisely when it contains no isolated vertices.
We study the trajectory of a simple random walk on a d-regular graph with d>2 and locally tree-like structure as the number n of vertices grows. Examples of such graphs include random d-regular graphs and large girth expanders. For these graphs, we i
Suppose we choose $N$ points uniformly randomly from a convex body in $d$ dimensions. How large must $N$ be, asymptotically with respect to $d$, so that the convex hull of the points is nearly as large as the convex body itself? It was shown by Dyer-
We consider a simple random walk on $mathbb{Z}^d$ started at the origin and stopped on its first exit time from $(-L,L)^d cap mathbb{Z}^d$. Write $L$ in the form $L = m N$ with $m = m(N)$ and $N$ an integer going to infinity in such a way that $L^2 s
Bootstrap percolation on a graph is a deterministic process that iteratively enlarges a set of occupied sites by adjoining points with at least $theta$ occupied neighbors. The initially occupied set is random, given by a uniform product measure with
Let $mathbb{T}^d_N$, $dge 2$, be the discrete $d$-dimensional torus with $N^d$ points. Place a particle at each site of $mathbb{T}^d_N$ and let them evolve as independent, nearest-neighbor, symmetric, continuous-time random walks. Each time two parti