Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEmergence of a Giant Component in Random Site Subgraphs of a d-Dimensional Hamming Torus
87
0
0.0
(
0
)
Authors
David Sivakoff
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 investigate percolative properties of the set of vertices not visited by the walk until time un, where u>0 is a fixed positive parameter. We show that this so-called vacant set exhibits a phase transition in u in the following sense: there exists an explicitly computable threshold u* such that, with high probability as n grows, if u<u*, then the largest component of the vacant set has a volume of order n, and if u>u*, then it has a volume of order log(n). The critical value u* coincides with the critical intensity of a random interlacement process (introduced by Sznitman [arXiv:0704.2560]) on a d-regular tree. We also show that the random interlacement model describes the structure of the vacant set in local neighbourhoods.
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-Furedi-McDiarmid that exponentially many samples suffice when the convex body is the hypercube, and by Pivovarov that the Euclidean ball demands roughly $d^{d/2}$ samples. We show that when the convex body is the simplex, exponentially many samples suffice; this then implies the same result for any convex simplicial polytope with at most exponentially many faces.
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 sim A N^d$ for some real constant $A > 0$. Our main result is that for $d ge 3$, the projection of the stopped trajectory to the $N$-torus locally converges, away from the origin, to an interlacement process at level $A d sigma_1$, where $sigma_1$ is the exit time of a Brownian motion from the unit cube $(-1,1)^d$ that is independent of the interlacement process. The above problem is a variation on results of Windisch (2008) and Sznitman (2009).
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 a low density $p$. Our main focus is on this process on the product graph $mathbb{Z}^2times K_n^2$, where $K_n$ is a complete graph. We investigate how $p$ scales with $n$ so that a typical site is eventually occupied. Under critical scaling, the dynamics with even $theta$ exhibits a sharp phase transition, while odd $theta$ yields a gradual percolation transition. We also establish a gradual transition for bootstrap percolation on $mathbb{Z}^2times K_n$. The main tool is heterogeneous bootstrap percolation on $mathbb{Z}^2$.
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 particles meet, they coalesce into one. Denote by $C_N$ the first time the set of particles is reduced to a singleton. Cox [6] proved the existence of a time-scale $theta_N$ for which $C_N/theta_N$ converges to the sum of independent exponential random variables. Denote by $Z^N_t$ the total number of particles at time $t$. We prove that the sequence of Markov chains $(Z^N_{ttheta_N})_{tge 0}$ converges to the total number of partitions in Kingmans coalescent.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
