The Smith normal form of distance matrices of high dimensional trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908577365491712 |
|---|---|
| author | Alfaro, Carlos A. Medrano, Jesús Uriel Téllez, Iván Téllez |
| author_facet | Alfaro, Carlos A. Medrano, Jesús Uriel Téllez, Iván Téllez |
| contents | Graham-Lovász-Pollak \cite{GL,GP} obtained the celebrated formula $$\det({\sf D}(T_{n+1}))=(-1)^nn2^{n-1},$$ for the determinant of the distance matrix ${\sf D}(T_{n+1})$ for any tree $T_{n+1}$ with $n+1$ vertices. Later, Hou and Woo \cite{HW} extended this formula to the Smith normal form (SNF) obtaining that $\SNF({\sf D}(T_{n+1}))={\sf I}_2\oplus 2{\sf I}_{n-2}\oplus [2n]$, for any tree $T_{n+1}$ with $n+1$ vertices.
A $k$-{\it tree} is either a complete graph on $k$ vertices or a graph obtained from a smaller $k$-tree by adjoining a new vertex together with $k$ edges connecting it to a $k$-clique. If $τ$ and $τ'$ are $d$-cliques in a $k$-tree $T$, a $d$-{\it walk} between $τ$ and $τ'$ is a finite sequence $τ_1σ_1τ_2σ_2\cdotsτ_l$, where $τ_1=τ$, $τ_l=τ'$, and the $d$-cliques $τ_i$ and $τ_{i+1}$ are incident to the same $(d+1)$-clique $σ_i$. For $d\in\{1,\dots,k\}$, the $d$-{\it distance} from the $d$-cliques $τ$ and $τ'$ is the number of $(d+1)$-cliques in a minimum $d$-walk from $τ$ and $τ'$, and is denoted by $\dist^d(τ,τ')$. Let $c_d$ denote the number of $d$-cliques in the $k$-tree $T$. Then the $d$-distance matrix ${\sf D}^d(T)$ of the $k$-tree $T$ is the $c_d\times c_d$ matrix, indexed by the $d$-cliques of $T$, such that the $(i,j)$-entry is $0$ if $i=j$, and $\dist^d(τ_i,τ_j)$ otherwise. Here, we show that, for $k$ and $n$ fixed, the SNF of the $k$-distance matrix is the same for any $k$-tree with $n$ vertices. Specifically, for any $k$-tree $T_{n}$ with $n$ vertices such that $n\geq k+2$, the Smith normal form of ${\sf D}^{k}(T_{n})$ is $${\sf I}_{(k-1)(n-k)+2}\oplus (k+1){\sf I}_{n-k-2}\oplus [k(k+1)(n-k)],$$ which extends Graham-Lovász-Pollak and Hou-Woo results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04471 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Smith normal form of distance matrices of high dimensional trees Alfaro, Carlos A. Medrano, Jesús Uriel Téllez, Iván Téllez Combinatorics 05C50, 05E45, 57M15, 57Q05 Graham-Lovász-Pollak \cite{GL,GP} obtained the celebrated formula $$\det({\sf D}(T_{n+1}))=(-1)^nn2^{n-1},$$ for the determinant of the distance matrix ${\sf D}(T_{n+1})$ for any tree $T_{n+1}$ with $n+1$ vertices. Later, Hou and Woo \cite{HW} extended this formula to the Smith normal form (SNF) obtaining that $\SNF({\sf D}(T_{n+1}))={\sf I}_2\oplus 2{\sf I}_{n-2}\oplus [2n]$, for any tree $T_{n+1}$ with $n+1$ vertices. A $k$-{\it tree} is either a complete graph on $k$ vertices or a graph obtained from a smaller $k$-tree by adjoining a new vertex together with $k$ edges connecting it to a $k$-clique. If $τ$ and $τ'$ are $d$-cliques in a $k$-tree $T$, a $d$-{\it walk} between $τ$ and $τ'$ is a finite sequence $τ_1σ_1τ_2σ_2\cdotsτ_l$, where $τ_1=τ$, $τ_l=τ'$, and the $d$-cliques $τ_i$ and $τ_{i+1}$ are incident to the same $(d+1)$-clique $σ_i$. For $d\in\{1,\dots,k\}$, the $d$-{\it distance} from the $d$-cliques $τ$ and $τ'$ is the number of $(d+1)$-cliques in a minimum $d$-walk from $τ$ and $τ'$, and is denoted by $\dist^d(τ,τ')$. Let $c_d$ denote the number of $d$-cliques in the $k$-tree $T$. Then the $d$-distance matrix ${\sf D}^d(T)$ of the $k$-tree $T$ is the $c_d\times c_d$ matrix, indexed by the $d$-cliques of $T$, such that the $(i,j)$-entry is $0$ if $i=j$, and $\dist^d(τ_i,τ_j)$ otherwise. Here, we show that, for $k$ and $n$ fixed, the SNF of the $k$-distance matrix is the same for any $k$-tree with $n$ vertices. Specifically, for any $k$-tree $T_{n}$ with $n$ vertices such that $n\geq k+2$, the Smith normal form of ${\sf D}^{k}(T_{n})$ is $${\sf I}_{(k-1)(n-k)+2}\oplus (k+1){\sf I}_{n-k-2}\oplus [k(k+1)(n-k)],$$ which extends Graham-Lovász-Pollak and Hou-Woo results. |
| title | The Smith normal form of distance matrices of high dimensional trees |
| topic | Combinatorics 05C50, 05E45, 57M15, 57Q05 |
| url | https://arxiv.org/abs/2510.04471 |