اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe maximal degree in random recursive graphs with random weights
68
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study a generalisation of the random recursive tree (RRT) model and its multigraph counterpart, the uniform directed acyclic graph (DAG). Here, vertices are equipped with a random vertex-weight representing initial inhomogeneities in the network, so that a new vertex connects to one of the old vertices with a probability that is proportional to their vertex-weight. We first identify the asymptotic degree distribution of a uniformly chosen vertex for a general vertex-weight distribution. For the maximal degree, we distinguish several classes that lead to different behaviour: For bounded vertex-weights we obtain results for the maximal degree that are similar to those observed for RRTs and DAGs. If the vertex-weights have unbounded support, then the maximal degree has to satisfy the right balance between having a high vertex-weight and being born early. For vertex-weights in the Frechet maximum domain of attraction the first order behaviour of the maximal degree is random, while for those in the Gumbel maximum domain of attraction the leading order is deterministic. Surprisingly, in the latter case, the second order is random when considering vertices in a compact window in the optimal region, while it becomes deterministic when considering all vertices.
قيم البحث
اقرأ أيضاً
We study geometric random graphs defined on the points of a Poisson process in $d$-dimensional space, which additionally carry independent random marks. Edges are established at random using the marks of the endpoints and the distance between points
in a flexible way. Our framework includes the soft Boolean model (where marks play the role of radii of balls centred in the vertices), a version of spatial preferential attachment (where marks play the role of birth times), and a whole range of other graph models with scale-free degree distributions and edges spanning large distances. In this versatile framework we give sharp criteria for absence of ultrasmallness of the graphs and in the ultrasmall regime establish a limit theorem for the chemical distance of two points. Other than in the mean-field scale-free network models the boundary of the ultrasmall regime depends not only on the power-law exponent of the degree distribution but also on the spatial embedding of the graph, quantified by the rate of decay of the probability of an edge connecting typical points in terms of their spatial distance.
The work continues the authors many-year research in theory of maximal branching processes, which are obtained from classical branching processes by replacing the summation of descendant numbers with taking the maximum. One can say that in each gener
ation, descendants of only one particle survive, namely those of the particle that has the largest number of descendants. Earlier, the author generalized processes with integer values to processes with arbitrary nonnegative values, investigated their properties, and proved limit theorems. Then processes with several types of particles were introduced and studied. In the present paper we introduce the notion of maximal branching processes in random environment (with a single type of particles) and an important case of a power-law random environment. In the latter case, properties of maximal branching processes are studied and the ergodic theorem is proved. As applications, we consider gated infinite-server queues.
We introduce a general recursive method to construct continuum random trees (CRTs) from independent copies of a random string of beads, that is, any random interval equipped with a random discrete probability measure, and from related structures. We
prove the existence of these CRTs as a new application of the fixpoint method for recursive distribution equations formalised in high generality by Aldous and Bandyopadhyay. We apply this recursive method to show the convergence to CRTs of various tree growth processes. We note alternative constructions of existing self-similar CRTs in the sense of Haas, Miermont and Stephenson, and we give for the first time constructions of random compact R-trees that describe the genealogies of Bertoins self-similar growth fragmentations. In forthcoming work, we develop further applications to embedding problems for CRTs, providing a binary embedding of the stable line-breaking construction that solves an open problem of Goldschmidt and Haas.
It is well known that the distribution of simple random walks on $bf{Z}$ conditioned on returning to the origin after $2n$ steps does not depend on $p= P(S_1 = 1)$, the probability of moving to the right. Moreover, conditioned on ${S_{2n}=0}$ the max
imal displacement $max_{kleq 2n} |S_k|$ converges in distribution when scaled by $sqrt{n}$ (diffusive scaling). We consider the analogous problem for transient random walks in random environments on $bf{Z}$. We show that under the quenched law $P_omega$ (conditioned on the environment $omega$), the maximal displacement of the random walk when conditioned to return to the origin at time $2n$ is no longer necessarily of the order $sqrt{n}$. If the environment is nestling (both positive and negative local drifts exist) then the maximal displacement conditioned on returning to the origin at time $2n$ is of order $n^{kappa/(kappa+1)}$, where the constant $kappa>0$ depends on the law on environment. On the other hand, if the environment is marginally nestling or non-nestling (only non-negative local drifts) then the maximal displacement conditioned on returning to the origin at time $2n$ is at least $n^{1-varepsilon}$ and at most $n/(ln n)^{2-varepsilon}$ for any $varepsilon>0$. As a consequence of our proofs, we obtain precise rates of decay for $P_omega(X_{2n}=0)$. In particular, for certain non-nestling environments we show that $P_omega(X_{2n}=0) = exp{-Cn -Cn/(ln n)^2 + o(n/(ln n)^2) }$ with explicit constants $C,C>0$.
For random $d$-regular graphs on $N$ vertices with $1 ll d ll N^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It im
plies that the eigenvalues of such random regular graphs are more rigid than those of ErdH{o}s-Renyi graphs of the same average degree. As a first application, for $1 ll d ll N^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2 + o(1)) sqrt{d - 1}$. As a second application, for $N^{2/9} ll d ll N^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52%$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2 sqrt{d - 1}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
