Maximizing subgraph counts in regular graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908916668956672 |
|---|---|
| author | Lippner, Gabor Miguel, Arturo Ortiz San |
| author_facet | Lippner, Gabor Miguel, Arturo Ortiz San |
| contents | Given a graph $H$, we investigate the $d$-regular graphs $G$ with the highest $H$-density. We reframe the problem as a continuous optimization problem on the eigenvalues of $G$ by relating injective homomorphism numbers from $H$ and homomorphism numbers from quotient graphs of $H$. For almost all $H$, this relation has non-spectral terms, which require bounding by spectral terms in a way that is sharp at the optimal graph.
For bipartite $H$ and $d$ large enough, we show $G$ consists of disjoint copies of $K_{d,d}$. For non-bipartite $H$ and $d$ sufficiently large, $G$ is a collection of disjoint $K_{d+1}$ graphs. For $H=C_5$ and $d=3$, disjoint Petersen graphs emerge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_20988 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximizing subgraph counts in regular graphs Lippner, Gabor Miguel, Arturo Ortiz San Combinatorics 05C35, 05C50 Given a graph $H$, we investigate the $d$-regular graphs $G$ with the highest $H$-density. We reframe the problem as a continuous optimization problem on the eigenvalues of $G$ by relating injective homomorphism numbers from $H$ and homomorphism numbers from quotient graphs of $H$. For almost all $H$, this relation has non-spectral terms, which require bounding by spectral terms in a way that is sharp at the optimal graph. For bipartite $H$ and $d$ large enough, we show $G$ consists of disjoint copies of $K_{d,d}$. For non-bipartite $H$ and $d$ sufficiently large, $G$ is a collection of disjoint $K_{d+1}$ graphs. For $H=C_5$ and $d=3$, disjoint Petersen graphs emerge. |
| title | Maximizing subgraph counts in regular graphs |
| topic | Combinatorics 05C35, 05C50 |
| url | https://arxiv.org/abs/2601.20988 |