Constructing generalized Heffter arrays via near alternating sign matrices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910191062089728 |
|---|---|
| author | Mella, Lorenzo Traetta, Tommaso |
| author_facet | Mella, Lorenzo Traetta, Tommaso |
| contents | Let $S$ be a subset of a group $G$ (not necessarily abelian) such that $S\,\cap -S$ is empty or contains only elements of order $2$, and let $\mathbf{h}=(h_1,\ldots, h_m)\in \mathbb{N}^m$ and $\mathbf{k}=(k_1, \ldots, k_n)\in \mathbb{N}^n$. A generalized Heffter array GHA$^λ_S(m, n; \mathbf{h}, \mathbf{k})$ over $G$ is an $m\times n$ matrix $A=(a_{ij})$ such that: the $i$-th row (resp. $j$-th column) of $A$ contains exactly $h_i$ (resp. $k_j$) nonzero elements, and the list $\{a_{ij}, -a_{ij}\mid a_{ij}\neq 0\}$ equals $λ$ times the set $S\,\cup\, -S$. We speak of a zero sum (resp. nonzero sum) GHA if each row and each column of $A$ sums to zero (resp. a nonzero element), with respect to some ordering.
In this paper, we use near alternating sign matrices to build both zero and nonzero sum GHAs, over cyclic groups, having the further strong property of being simple. In particular, we construct zero sum and simple GHAs whose row and column weights are congruent to $0$ modulo $4$. This result also provides the first infinite family of simple (classic) Heffter arrays to be rectangular ($m\neq n$) and with less than $n$ nonzero entries in each row. Furthermore, we build nonzero sum GHA$^λ_S(m, n; \mathbf{h}, \mathbf{k})$ over an arbitrary group $G$ whenever $S$ contains enough noninvolutions, thus extending previous nonconstructive results where $\pm S = G\setminus H$ for some subgroup $H$~of~$G$.
Finally, we describe how GHAs can be used to build orthogonal decompositions and biembeddings of Cayley graphs (over groups not necessarily abelian) onto orientable surfaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_09948 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Constructing generalized Heffter arrays via near alternating sign matrices Mella, Lorenzo Traetta, Tommaso Combinatorics 05B20, 05C10, 05C51 Let $S$ be a subset of a group $G$ (not necessarily abelian) such that $S\,\cap -S$ is empty or contains only elements of order $2$, and let $\mathbf{h}=(h_1,\ldots, h_m)\in \mathbb{N}^m$ and $\mathbf{k}=(k_1, \ldots, k_n)\in \mathbb{N}^n$. A generalized Heffter array GHA$^λ_S(m, n; \mathbf{h}, \mathbf{k})$ over $G$ is an $m\times n$ matrix $A=(a_{ij})$ such that: the $i$-th row (resp. $j$-th column) of $A$ contains exactly $h_i$ (resp. $k_j$) nonzero elements, and the list $\{a_{ij}, -a_{ij}\mid a_{ij}\neq 0\}$ equals $λ$ times the set $S\,\cup\, -S$. We speak of a zero sum (resp. nonzero sum) GHA if each row and each column of $A$ sums to zero (resp. a nonzero element), with respect to some ordering. In this paper, we use near alternating sign matrices to build both zero and nonzero sum GHAs, over cyclic groups, having the further strong property of being simple. In particular, we construct zero sum and simple GHAs whose row and column weights are congruent to $0$ modulo $4$. This result also provides the first infinite family of simple (classic) Heffter arrays to be rectangular ($m\neq n$) and with less than $n$ nonzero entries in each row. Furthermore, we build nonzero sum GHA$^λ_S(m, n; \mathbf{h}, \mathbf{k})$ over an arbitrary group $G$ whenever $S$ contains enough noninvolutions, thus extending previous nonconstructive results where $\pm S = G\setminus H$ for some subgroup $H$~of~$G$. Finally, we describe how GHAs can be used to build orthogonal decompositions and biembeddings of Cayley graphs (over groups not necessarily abelian) onto orientable surfaces. |
| title | Constructing generalized Heffter arrays via near alternating sign matrices |
| topic | Combinatorics 05B20, 05C10, 05C51 |
| url | https://arxiv.org/abs/2306.09948 |