| Title:
|
Partial sum of eigenvalues of random graphs (English) |
| Author:
|
Rocha, Israel |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
65 |
| Issue:
|
5 |
| Year:
|
2020 |
| Pages:
|
609-618 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $G$ be a graph on $n$ vertices and let $\lambda _{1}\geq \lambda _{2}\geq \ldots \geq \lambda _{n}$ be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues $s_{k}=\sum _{i=1}^{k}\lambda _{i}$, for $1\leq k\leq n$, and show that a typical graph has $s_{k}\leq (e(G)+k^{2})/(0.99n)^{1/2}$, where $e(G)$ is the number of edges of $G$. We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix. (English) |
| Keyword:
|
sum of eigenvalues |
| Keyword:
|
graph energy |
| Keyword:
|
random matrix |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
07285948 |
| idMR:
|
MR4160784 |
| DOI:
|
10.21136/AM.2020.0352-19 |
| . |
| Date available:
|
2020-09-23T13:48:49Z |
| Last updated:
|
2022-11-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148368 |
| . |
| Reference:
|
[1] Das, K. C., Mojallal, S. A., Sun, S.: On the sum of the $k$ largest eigenvalues of graphs and maximal energy of bipartite graphs.Linear Algebra Appl. 569 (2019), 175-194. Zbl 1411.05156, MR 3904318, 10.1016/j.laa.2019.01.016 |
| Reference:
|
[2] Füredi, Z., Komlós, J.: The eigenvalues of random symmetric matrices.Combinatorica 1 (1981), 233-241. Zbl 0494.15010, MR 0637828, 10.1007/BF02579329 |
| Reference:
|
[3] Graovac, A., Gotman, I., Trinajstić, N.: Topological Approach to the Chemistry of Conjugated Molecules.Lecture Notes in Chemistry 4. Springer, Berlin (1977). Zbl 0385.05032, 10.1007/978-3-642-93069-0 |
| Reference:
|
[4] Hoeffding, W.: Probability inequalities for sums of bounded random variables.J. Am. Stat. Assoc. 58 (1963), 13-30. Zbl 0127.10602, MR 0144363, 10.2307/2282952 |
| Reference:
|
[5] Li, X., Shi, Y., Gutman, I.: Graph Energy.Springer, New York (2012). Zbl 1262.05100, MR 2953171, 10.1007/978-1-4614-4220-2 |
| Reference:
|
[6] Mohar, B.: On the sum of $k$ largest eigenvalues of graphs and symmetric matrices.J. Comb. Theory, Ser. B 99 (2009), 306-313. Zbl 1217.05151, MR 2482950, 10.1016/j.jctb.2008.07.001 |
| Reference:
|
[7] Nikiforov, V.: The energy of graphs and matrices.J. Math. Anal. Appl. 326 (2007), 1472-1475. Zbl 1113.15016, MR 2280998, 10.1016/j.jmaa.2006.03.072 |
| Reference:
|
[8] Nikiforov, V.: On the sum of $k$ largest singular values of graphs and matrices.Linear Algebra Appl. 435 (2011), 2394-2401. Zbl 1222.05172, MR 2811124, 10.1016/j.laa.2010.08.014 |
| Reference:
|
[9] Nikiforov, V.: Beyond graph energy: norms of graphs and matrices.Linear Algebra Appl. 506 (2016), 82-138. Zbl 1344.05089, MR 3530671, 10.1016/j.laa.2016.05.011 |
| Reference:
|
[10] Rocha, I.: Brouwer's conjecture holds asymptotically almost surely.Linear Algebra Appl. 597 (2020), 198-205. Zbl 07190773, MR 4082064, 10.1016/j.laa.2020.03.019 |
| Reference:
|
[11] Wigner, E. P.: On the distribution of the roots of certain symmetric matrices.Ann. Math. (2) 67 (1958), 325-327. Zbl 0085.13203, MR 0095527, 10.2307/1970008 |
| . |
