اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEdge rigidity and universality of random regular graphs of intermediate degree
139
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 implies 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}$.
قيم البحث
اقرأ أيضاً
We consider the sum of two large Hermitian matrices $A$ and $B$ with a Haar unitary conjugation bringing them into a general relative position. We prove that the eigenvalue density on the scale slightly above the local eigenvalue spacing is asymptoti
cally given by the free convolution of the laws of $A$ and $B$ as the dimension of the matrix increases. This implies optimal rigidity of the eigenvalues and optimal rate of convergence in Voiculescus theorem. Our previous works [3,4] established these results in the bulk spectrum, the current paper completely settles the problem at the spectral edges provided they have the typical square-root behavior. The key element of our proof is to compensate the deterioration of the stability of the subordination equations by sharp error estimates that properly account for the local density near the edge. Our results also hold if the Haar unitary matrix is replaced by the Haar orthogonal matrix.
Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $dgeq3$. We prove that, with probability $1-N^{-1+{varepsilon}}$ for any ${varepsilon} >0$, the following two properties hold as $N to infty$ pr
ovided that $dgeq3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten-McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in $N$, i.e. $lambda_2, |lambda_N|leq 2+N^{-c}$. (ii) All eigenvectors of random $d$-regular graphs are completely delocalized.
Consider a random regular graph with degree $d$ and of size $n$. Assign to each edge an i.i.d. exponential random variable with mean one. In this paper we establish a precise asymptotic expression for the maximum number of edges on the shortest-weigh
t paths between a fixed vertex and all the other vertices, as well as between any pair of vertices. Namely, for any fixed $d geq 3$, we show that the longest of these shortest-weight paths has about $hat{alpha}log n$ edges where $hat{alpha}$ is the unique solution of the equation $alpha log(frac{d-2}{d-1}alpha) - alpha = frac{d-3}{d-2}$, for $alpha > frac{d-1}{d-2}$.
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.
In [17], the authors have defined an annealed Ising model on random graphs and proved limit theorems for the magnetization of this model on some random graphs including random 2-regular graphs. Then in [11], we generalized their results to the class
of all random regular graphs. In this paper, we study the critical behavior of this model. In particular, we determine the critical exponents and prove a non standard limit theorem that the magnetization scaled by n 3/4 converges to a specific random variable, with n the number of vertices of random regular graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
