Counting substructures and eigenvalues II: quadrilaterals
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917003513561088 |
|---|---|
| author | Ning, Bo Zhai, Mingqing |
| author_facet | Ning, Bo Zhai, Mingqing |
| contents | Let $G$ be a graph and $λ(G)$ be the spectral radius of $G$. A previous result due to Nikiforov [Linear Algebra Appl., 2009] in spectral graph theory asserted that every graph $G$ on $m\geq 10$ edges contains a 4-cycle if $λ(G)>\sqrt{m}$. Define $f(m)$ to be the minimum number of copies of 4-cycles in such a graph. A consequence of a recent theorem due to Zhai et al. [European J. Combin., 2021] shows that $f(m)=Ω(m)$. In this article, by somewhat different techniques, we prove that $f(m)=Θ(m^2)$. We left the solution to $\lim\limits_{m\rightarrow \infty} \frac{f(m)}{m^2}$ as a problem, and also mention other ones for further study. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_15279 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Counting substructures and eigenvalues II: quadrilaterals Ning, Bo Zhai, Mingqing Combinatorics Let $G$ be a graph and $λ(G)$ be the spectral radius of $G$. A previous result due to Nikiforov [Linear Algebra Appl., 2009] in spectral graph theory asserted that every graph $G$ on $m\geq 10$ edges contains a 4-cycle if $λ(G)>\sqrt{m}$. Define $f(m)$ to be the minimum number of copies of 4-cycles in such a graph. A consequence of a recent theorem due to Zhai et al. [European J. Combin., 2021] shows that $f(m)=Ω(m)$. In this article, by somewhat different techniques, we prove that $f(m)=Θ(m^2)$. We left the solution to $\lim\limits_{m\rightarrow \infty} \frac{f(m)}{m^2}$ as a problem, and also mention other ones for further study. |
| title | Counting substructures and eigenvalues II: quadrilaterals |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2112.15279 |