Curvature, diameter and signs of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916220896280576 |
|---|---|
| author | Chen, Wei Liu, Shiping |
| author_facet | Chen, Wei Liu, Shiping |
| contents | We prove a Li-Yau type eigenvalue-diameter estimate for signed graphs. That is, the nonzero eigenvalues of the Laplacian of a non-negatively curved signed graph are lower bounded by $1/D^2$ up to a constant, where $D$ stands for the diameter. This leads to several interesting applications, including a volume estimate for non-negatively curved signed graphs in terms of frustration index and diameter, and a two-sided Li-Yau estimate for triangle-free graphs. Our proof is built upon a combination of Chung-Lin-Yau type gradient estimate and a new trick involving strong nodal domain walks of signed graphs. We further discuss extensions of part of our results to nonlinear Laplacians on signed graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15594 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Curvature, diameter and signs of graphs Chen, Wei Liu, Shiping Combinatorics Differential Geometry Spectral Theory We prove a Li-Yau type eigenvalue-diameter estimate for signed graphs. That is, the nonzero eigenvalues of the Laplacian of a non-negatively curved signed graph are lower bounded by $1/D^2$ up to a constant, where $D$ stands for the diameter. This leads to several interesting applications, including a volume estimate for non-negatively curved signed graphs in terms of frustration index and diameter, and a two-sided Li-Yau estimate for triangle-free graphs. Our proof is built upon a combination of Chung-Lin-Yau type gradient estimate and a new trick involving strong nodal domain walks of signed graphs. We further discuss extensions of part of our results to nonlinear Laplacians on signed graphs. |
| title | Curvature, diameter and signs of graphs |
| topic | Combinatorics Differential Geometry Spectral Theory |
| url | https://arxiv.org/abs/2404.15594 |