arXiv preprint ·
The chromatic number of the associahedron: simple and logarithmic
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the $n$-dimensional associahedron has chromatic number at most $22500\cdot\log_3 n+O(1)$. We present a much simpler proof that the chromatic number of the $n-1$-dimensional associahedron is at most $6 \log_2 n + 18$. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to $O(\log \log n)$ by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach
Mutually unbiased bases: common states, completion, and extension obstructions
Polynomial directed treewidth forces a large bramble with congestion two
Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.