July 31, 2001
Similar papers 2
October 28, 2009
We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvect...
March 14, 2021
We analyse the eigenvalues of Erd\"os--R\'enyi random bipartite graphs. In particular, we consider $p$ satisfying $n_{1}p=\Omega(\sqrt{n_{1}p}\log^{3}(n_{1})),$ $n_{2}p=\Omega(\sqrt{n_{2}p}\log^{3}(n_{2})),$ and let $G\sim G(n_{1},n_{2},p)$. We show that with probability tending to $1$ as $n_{1}$ tends to infinity: $$\mu_{2} (A(G))\leq 2[1+o(1)](\sqrt{n_{1}p}+\sqrt{n_{2}p}+\sqrt{(n_{1}+n_{2})p}).$$
May 31, 2007
The largest eigenvalue of the adjacency matrix of a network plays an important role in several network processes (e.g., synchronization of oscillators, percolation on directed networks, linear stability of equilibria of network coupled systems, etc.). In this paper we develop approximations to the largest eigenvalue of adjacency matrices and discuss the relationships between these approximations. Numerical experiments on simulated networks are used to test our results.
April 10, 2017
We consider inhomogeneous Erd\H{o}s-R\'enyi graphs. We suppose that the maximal mean degree $d$ satisfies $d \ll \log n$. We characterize the asymptotic behavior of the $n^{1 - o(1)}$ largest eigenvalues of the adjacency matrix and its centred version. We prove that these extreme eigenvalues are governed at first order by the largest degrees and, for the adjacency matrix, by the nonzero eigenvalues of the expectation matrix. Our results show that the extreme eigenvalues exhib...
March 18, 2023
This paper investigates the asymptotic nature of graph spectra when some edges of a graph are subdivided sufficiently many times. In the special case where all edges of a graph are subdivided, we find the exact limits of the $k$-th largest and $k$-th smallest eigenvalues for any fixed $k$. It is expected that after subdivision, most eigenvalues of the new graph will lie in the interval $[-2,2]$. We examine the eigenvalues of the new graph outside this interval, and we prove s...
September 15, 2011
Let $H=(V,E)$ be an $r$-uniform hypergraph with the vertex set $V$ and the edge set $E$. For $1\leq s \leq r/2$, we define a weighted graph $G^{(s)}$ on the vertex set ${V\choose s}$ as follows. Every pair of $s$-sets $I$ and $J$ is associated with a weight $w(I,J)$, which is the number of edges in $H$ passing through $I$ and $J$ if $I\cap J=\emptyset$, and 0 if $I\cap J\not=\emptyset$. The $s$-th Laplacian $\L^{(s)}$ of $H$ is defined to be the normalized Laplacian of $G^{(s...
September 13, 2021
We consider an Erd\H{o}s-R\'{e}nyi graph $\mathbb{G}(n,p)$ on $n$ vertices with edge probability $p$ such that \[ \sqrt{\frac{\log n}{\log \log n}} \ll np \le n^{1/2-o(1)}, \label{eq:abs} \tag{$\dagger$} \] and derive the upper tail large deviations of $\lambda(\mathbb{G}(n,p))$, the largest eigenvalue of its adjacency matrix. Within this regime we show that, for $p \gg n^{-2/3}$ the $\log$-probability of the upper tail event of $\lambda(\mathbb{G}(n,p))$ equals to that of pl...
December 9, 2015
Lower bounds for the first and the second eigenvalue of uniform hypergraphs which are regular and linear are obtained. One of these bounds is a generalization of the Alon-Boppana Theorem to hypergraphs.
April 10, 2020
In this paper we study the spectrum of the random geometric graph $G(n,r)$, in a regime where the graph is dense and highly connected. In the \erdren $G(n,p)$ random graph it is well known that upon connectivity the spectrum of the normalized graph Laplacian is concentrated around $1$. We show that such concentration does not occur in the $G(n,r)$ case, even when the graph is dense and almost a complete graph. In particular, we show that the limiting spectral gap is strictly ...
May 22, 2023
We investigate the statistics of the largest eigenvalue, $\lambda_{\rm max}$, in an ensemble of $N\times N$ large ($N\gg 1$) sparse adjacency matrices, $A_N$. The most attention is paid to the distribution and typical fluctuations of $\lambda_{\rm max}$ in the vicinity of the percolation threshold, $p_c=\frac{1}{N}$. The overwhelming majority of subgraphs representing $A_N$ near $p_c$ are exponentially distributed linear subchains, for which the statistics of the normalized l...