Colouring random Hasse diagrams and box-Delaunay graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916575676727296 |
|---|---|
| author | Jin, Zhihan Kwan, Matthew Lichev, Lyuben |
| author_facet | Jin, Zhihan Kwan, Matthew Lichev, Lyuben |
| contents | Fix $d\ge2$ and consider a uniformly random set $P$ of $n$ points in $[0,1]^{d}$. Let $G$ be the Hasse diagram of $P$ (with respect to the coordinatewise partial order), or alternatively let $G$ be the Delaunay graph of $P$ with respect to axis-parallel boxes (where we put an edge between $u,v\in P$ whenever there is an axis-parallel box containing $u,v$ and no other points of $P$).
In each of these two closely related settings, we show that the chromatic number of $G$ is typically $(\log n)^{d-1+o(1)}$ and the independence number of $G$ is typically $n/(\log n)^{d-1+o(1)}$. When $d=2$, we obtain bounds that are sharp up to constant factors: the chromatic number is typically of order $\log n/\log\log n$ and the independence number is typically of order $n\log\log n/\log n$.
These results extend and sharpen previous bounds by Chen, Pach, Szegedy and Tardos. In addition, they provide new bounds on the largest possible chromatic number (and lowest possible independence number) of a $d$-dimensional box-Delaunay graph or Hasse diagram, in particular resolving a conjecture of Tomon. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Colouring random Hasse diagrams and box-Delaunay graphs Jin, Zhihan Kwan, Matthew Lichev, Lyuben Combinatorics Probability 52C45, 05C80, 06A07 Fix $d\ge2$ and consider a uniformly random set $P$ of $n$ points in $[0,1]^{d}$. Let $G$ be the Hasse diagram of $P$ (with respect to the coordinatewise partial order), or alternatively let $G$ be the Delaunay graph of $P$ with respect to axis-parallel boxes (where we put an edge between $u,v\in P$ whenever there is an axis-parallel box containing $u,v$ and no other points of $P$). In each of these two closely related settings, we show that the chromatic number of $G$ is typically $(\log n)^{d-1+o(1)}$ and the independence number of $G$ is typically $n/(\log n)^{d-1+o(1)}$. When $d=2$, we obtain bounds that are sharp up to constant factors: the chromatic number is typically of order $\log n/\log\log n$ and the independence number is typically of order $n\log\log n/\log n$. These results extend and sharpen previous bounds by Chen, Pach, Szegedy and Tardos. In addition, they provide new bounds on the largest possible chromatic number (and lowest possible independence number) of a $d$-dimensional box-Delaunay graph or Hasse diagram, in particular resolving a conjecture of Tomon. |
| title | Colouring random Hasse diagrams and box-Delaunay graphs |
| topic | Combinatorics Probability 52C45, 05C80, 06A07 |
| url | https://arxiv.org/abs/2501.12373 |