The chromatic number of 4-dimensional lattices
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908406543024128 |
|---|---|
| author | Vallentin, Frank Weißbach, Stephen Zimmermann, Marc Christian |
| author_facet | Vallentin, Frank Weißbach, Stephen Zimmermann, Marc Christian |
| contents | The chromatic number of a lattice in n-dimensional Euclidean space is defined as the chromatic number of its Voronoi graph. The Voronoi graph is the Cayley graph on the lattice having the strict Voronoi vectors as generators. In this paper we determine the chromatic number of all 4-dimensional lattices. To achieve this we use the known classification of 52 parallelohedra in dimension 4. These 52 geometric types yield 16 combinatorial types of relevant Voronoi graphs. We discuss a systematic approach to checking for isomorphism of Cayley graphs of lattices. Lower bounds for the chromatic number are obtained from choosing appropriate small finite induced subgraphs of the Voronoi graphs. Matching upper bounds are derived from periodic colorings. To determine the chromatic numbers of these finite graphs, we employ a SAT solver. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_03513 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The chromatic number of 4-dimensional lattices Vallentin, Frank Weißbach, Stephen Zimmermann, Marc Christian Combinatorics Metric Geometry The chromatic number of a lattice in n-dimensional Euclidean space is defined as the chromatic number of its Voronoi graph. The Voronoi graph is the Cayley graph on the lattice having the strict Voronoi vectors as generators. In this paper we determine the chromatic number of all 4-dimensional lattices. To achieve this we use the known classification of 52 parallelohedra in dimension 4. These 52 geometric types yield 16 combinatorial types of relevant Voronoi graphs. We discuss a systematic approach to checking for isomorphism of Cayley graphs of lattices. Lower bounds for the chromatic number are obtained from choosing appropriate small finite induced subgraphs of the Voronoi graphs. Matching upper bounds are derived from periodic colorings. To determine the chromatic numbers of these finite graphs, we employ a SAT solver. |
| title | The chromatic number of 4-dimensional lattices |
| topic | Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2407.03513 |