Geometric graphs with exponential chromatic number and arbitrary girth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929548019367936 |
|---|---|
| author | Bucić, Matija Davies, James |
| author_facet | Bucić, Matija Davies, James |
| contents | In 1975 Erdős initiated the study of the following very natural question. What can be said about the chromatic number of unit distance graphs in $\mathbb{R}^2$ that have large girth? Over the years this question and its natural extension to $\mathbb{R}^d$ attracted considerable attention with the high-dimensional variant reiterated recently by Alon and Kupavskii.
We prove that there exist unit distance graphs in $\mathbb{R}^d$ with chromatic number at least $(1.074 + o(1))^d$ that have arbitrarily large girth. This improves upon a series of results due to Kupavskii; Sagdeev; and Sagdeev and Raigorodskii and gives the first bound in which the base of the exponent does not tend to one with the girth. In addition, our construction can be made explicit which allows us to answer in a strong form a question of Kupavskii.
Our arguments show graphs of large chromatic number and high girth exist in a number of other geometric settings including diameter graphs and orthogonality graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_06898 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Geometric graphs with exponential chromatic number and arbitrary girth Bucić, Matija Davies, James Combinatorics Metric Geometry In 1975 Erdős initiated the study of the following very natural question. What can be said about the chromatic number of unit distance graphs in $\mathbb{R}^2$ that have large girth? Over the years this question and its natural extension to $\mathbb{R}^d$ attracted considerable attention with the high-dimensional variant reiterated recently by Alon and Kupavskii. We prove that there exist unit distance graphs in $\mathbb{R}^d$ with chromatic number at least $(1.074 + o(1))^d$ that have arbitrarily large girth. This improves upon a series of results due to Kupavskii; Sagdeev; and Sagdeev and Raigorodskii and gives the first bound in which the base of the exponent does not tend to one with the girth. In addition, our construction can be made explicit which allows us to answer in a strong form a question of Kupavskii. Our arguments show graphs of large chromatic number and high girth exist in a number of other geometric settings including diameter graphs and orthogonality graphs. |
| title | Geometric graphs with exponential chromatic number and arbitrary girth |
| topic | Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2312.06898 |