CAT(0) square complexes that do not embed into finite products of trees

Abstract

Answering a question of Chepoi and Hagen, we give two constructions of bounded degree CAT(0) square complexes that cannot be isometrically embedded into any finite product of trees. The first is based on Burling graphs and has degree at most five, which is optimal. These square complexes topologically embed into R³ since we further prove that every CAT(0) square complex whose vertices have degree at most five can be topologically embedded into the product of a line and a star. It turns out that in this setting, Burling graphs are the only obstruction: we prove that CAT(0) square complexes that topologically embed into R³ and whose crossing graph forbids some induced Burling graph can be isometrically embedded into a finite product of trees. Our second CAT(0) square complex has degree at most six and its crossing graph forbids an induced Burling graph. Of independent graph-theoretic interest, along the way we construct intersections of chordal and interval graphs with arbitrarily large girth and chromatic number. We also discuss connections to nice labellings of event structures.

Product subcomplexes and intersection complexes of weakly special square complexes
Sangrok Oh
arXiv21 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Geometry & topologyarXiv
Horocyclic products of trees
Laurent Bartholdi, Markus Neuhauser, Wolfgang Woess
J. Eur. Math. Soc. (JEMS)3 Nov 2026Peer-reviewedLicence not statedFull text56 citedCombinatorics & discrete mathematicsHAL
On the residual finiteness of the non-abelian exterior square of wreath products and the Grigorchuk group
Ayrton Anjos Teixeira, Dessislava H. Kochloukova
arXiv7 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Square products of factorials and a conjecture of Erdős and Graham
Fedir Yudin
arXiv1 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Piercing boxes and products of trees
Wei Rao, Taehyun Eom, Minki Kim
arXiv12 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{davies2026cat0,
  title = {{CAT(0) square complexes that do not embed into finite products of trees}},
  author = {James Davies and Harry Petyt},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17285},
  eprint = {2609.17285},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17285},
}

RIS

TY  - UNPB
TI  - CAT(0) square complexes that do not embed into finite products of trees
AU  - James Davies
AU  - Harry Petyt
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.17285
UR  - https://arxiv.org/abs/2609.17285
AB  - Answering a question of Chepoi and Hagen, we give two constructions of bounded degree CAT(0) square complexes that cannot be isometrically embedded into any finite product of trees. The first is based on Burling graphs and has degree at most five, which is optimal. These square complexes topologically embed into R^3 since we further prove that every CAT(0) square complex whose vertices have degree at most five can be topologically embedded into the product of a line and a star. It turns out that in this setting, Burling graphs are the only obstruction: we prove that CAT(0) square complexes that topologically embed into R^3 and whose crossing graph forbids some induced Burling graph can be isometrically embedded into a finite product of trees. Our second CAT(0) square complex has degree at most six and its crossing graph forbids an induced Burling graph. Of independent graph-theoretic interest, along the way we construct intersections of chordal and interval graphs with arbitrarily large girth and chromatic number. We also discuss connections to nice labellings of event structures.
ER  -

Abstract

Related

Cite