On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916325998198784 |
|---|---|
| author | Lau, Lap Chi Tjowasi, Dante |
| author_facet | Lau, Lap Chi Tjowasi, Dante |
| contents | Houdré and Tetali defined a class of isoperimetric constants $φ_p$ of graphs for $0 \leq p \leq 1$, and conjectured a Cheeger-type inequality for $φ_\frac12$ of the form $$λ_2 \lesssim φ_\frac12 \lesssim \sqrt{λ_2}$$ where $λ_2$ is the second smallest eigenvalue of the normalized Laplacian matrix. If true, the conjecture would be a strengthening of the hard direction of the classical Cheeger's inequality. Morris and Peres proved Houdré and Tetali's conjecture up to an additional log factor, using techniques from evolving sets. We present the following related results on this conjecture.
- We provide a family of counterexamples to the conjecture of Houdré and Tetali, showing that the logarithmic factor is needed.
- We match Morris and Peres's bound using standard spectral arguments.
- We prove that Houdré and Tetali's conjecture is true for any constant $p$ strictly bigger than $\frac12$, which is also a strengthening of the hard direction of Cheeger's inequality.
Furthermore, our results can be extended to directed graphs using Chung's definition of eigenvalues for directed graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_11357 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Houdré-Tetali conjecture about an isoperimetric constant of graphs Lau, Lap Chi Tjowasi, Dante Data Structures and Algorithms Discrete Mathematics Combinatorics Houdré and Tetali defined a class of isoperimetric constants $φ_p$ of graphs for $0 \leq p \leq 1$, and conjectured a Cheeger-type inequality for $φ_\frac12$ of the form $$λ_2 \lesssim φ_\frac12 \lesssim \sqrt{λ_2}$$ where $λ_2$ is the second smallest eigenvalue of the normalized Laplacian matrix. If true, the conjecture would be a strengthening of the hard direction of the classical Cheeger's inequality. Morris and Peres proved Houdré and Tetali's conjecture up to an additional log factor, using techniques from evolving sets. We present the following related results on this conjecture. - We provide a family of counterexamples to the conjecture of Houdré and Tetali, showing that the logarithmic factor is needed. - We match Morris and Peres's bound using standard spectral arguments. - We prove that Houdré and Tetali's conjecture is true for any constant $p$ strictly bigger than $\frac12$, which is also a strengthening of the hard direction of Cheeger's inequality. Furthermore, our results can be extended to directed graphs using Chung's definition of eigenvalues for directed graphs. |
| title | On the Houdré-Tetali conjecture about an isoperimetric constant of graphs |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2407.11357 |