Click here to flash read.
arXiv:2404.15167v1 Announce Type: new
Abstract: Let $G$ be a graph on $n$ vertices, with complement $\overline{G}$. The spectral gap of the transition probability matrix of a random walk on $G$ is used to estimate how fast the random walk becomes stationary. We prove that the larger spectral gap of $G$ and $\overline{G}$ is $\Omega(1/n)$. Moreover, if all degrees are $\Omega(n)$ and $n-\Omega(n)$, then the larger spectral gap of $G$ and $\overline{G}$ is $\Theta(1)$. We also show that if the maximum degree is $n-O(1)$ or if $G$ is a join of two graphs, then the spectral gap of $G$ is $\Omega(1/n)$. Finally, we provide a family of graphs such that the larger spectral gap of $G$ and $\overline{G}$ is $O(1/n^{3/4})$.
Click here to read this post out
ID: 820859; Unique Viewers: 0
Unique Voters: 0
Total Votes: 0
Votes:
Latest Change: April 24, 2024, 7:32 a.m.
Changes:
Dictionaries:
Words:
Spaces:
Views: 8
CC:
No creative common's license
No creative common's license
Comments: