Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2512.23828 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914224909844480 |
|---|---|
| author | Galvin, David Marmorino, Phillip McMillon, Emily Nir, JD Redlich, Amanda |
| author_facet | Galvin, David Marmorino, Phillip McMillon, Emily Nir, JD Redlich, Amanda |
| contents | Given a graph $G$ and a target graph $H$, an $H$-coloring of $G$ is an adjacency-preserving vertex map from $G$ to $H$. The number of $H$-colorings of $G$, $\hom(G,H)$, has been studied for many classes of $G$ and $H$. In particular, extremal questions of maximizing and minimizing $\hom(G,H)$ have been considered when $H$ is a clique or $G$ is a tree.
In this paper, we develop a new technique using automorphisms of $H$ to show that $\hom(T,H)$ is minimized by paths as $T$ varies over trees on a fixed number of vertices. We introduce the term Hoffman-London to refer to graphs that are minimal in this sense. In particular, we define an automorphic similarity matrix which is used to compute $\hom(T,H)$ and give matrix conditions under which $H$ is Hoffman-London.
We then apply this technique to identify several families of graphs that are Hoffman-London, including loop threshold graphs and some with applications in statistical physics (e.g. the Widom-Rowlinson model). By combining our approach with a few other observations, we fully characterize the minimizing trees for all graphs $H$ on three or fewer vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23828 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hoffman-London graphs: When paths minimize $H$-colorings among trees Galvin, David Marmorino, Phillip McMillon, Emily Nir, JD Redlich, Amanda Combinatorics 05C05, 05C15, 05C35 Given a graph $G$ and a target graph $H$, an $H$-coloring of $G$ is an adjacency-preserving vertex map from $G$ to $H$. The number of $H$-colorings of $G$, $\hom(G,H)$, has been studied for many classes of $G$ and $H$. In particular, extremal questions of maximizing and minimizing $\hom(G,H)$ have been considered when $H$ is a clique or $G$ is a tree. In this paper, we develop a new technique using automorphisms of $H$ to show that $\hom(T,H)$ is minimized by paths as $T$ varies over trees on a fixed number of vertices. We introduce the term Hoffman-London to refer to graphs that are minimal in this sense. In particular, we define an automorphic similarity matrix which is used to compute $\hom(T,H)$ and give matrix conditions under which $H$ is Hoffman-London. We then apply this technique to identify several families of graphs that are Hoffman-London, including loop threshold graphs and some with applications in statistical physics (e.g. the Widom-Rowlinson model). By combining our approach with a few other observations, we fully characterize the minimizing trees for all graphs $H$ on three or fewer vertices. |
| title | Hoffman-London graphs: When paths minimize $H$-colorings among trees |
| topic | Combinatorics 05C05, 05C15, 05C35 |
| url | https://arxiv.org/abs/2512.23828 |