PreprintarXiv licencearXiv
Strong coloring numbers of grids
Abstract
For positive integers n and d, the d-dimensional grid of side length n is the graph G(n,d) with vertex set [n]d, in which two vertices are adjacent if they differ by $1$ in exactly one coordinate and agree in all the other coordinates. We determine, for every fixed d, the asymptotic growth in r of the rth strong coloring numbers of these grids. More precisely for n large enough, scolr(G(n,d)) = Ωd(rd−1) as r→∞. This matches an upper bound given by a volume packing argument, which holds more generally for touching graphs of unit balls in ℝd. For the lower bound, we construct in G(n,d) a bramble of order Ωd(nd−1) with each element of radius at most dn. This construction was found by OpenAI's GPT-5.6 Sol.
Related
- Sparse coloring for isosceles-free grids: an AI-assisted proof case study
- Strong edge coloring of graphs with maximum degree $6$
- Polynomially superlinear growth of set-coloring Ramsey numbers
- On the Classical and Parameterized Complexity of Strong Odd Coloring
- Strong law of large numbers for random semigroups in norm topology
BibTeX
@misc{micek2026strong,
title = {{Strong coloring numbers of grids}},
author = {Piotr Micek and Torsten Ueckerdt},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21506},
eprint = {2610.21506},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21506},
}
RIS
TY - UNPB
TI - Strong coloring numbers of grids
AU - Piotr Micek
AU - Torsten Ueckerdt
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21506
UR - https://arxiv.org/abs/2610.21506
AB - For positive integers n and d, the d-dimensional grid of side length n is the graph G(n,d) with vertex set [n]^d, in which two vertices are adjacent if they differ by $1$ in exactly one coordinate and agree in all the other coordinates. We determine, for every fixed d, the asymptotic growth in r of the rth strong coloring numbers of these grids. More precisely for n large enough, scol_r(G(n,d)) = Ω_d(r^d−1) as r→∞. This matches an upper bound given by a volume packing argument, which holds more generally for touching graphs of unit balls in ℝ^d. For the lower bound, we construct in G(n,d) a bramble of order Ω_d(n^d−1) with each element of radius at most dn. This construction was found by OpenAI's GPT-5.6 Sol.
ER -