On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes

DOI10.1016/J.JCTB.2013.04.003zbMATH Open1301.05120arXiv1107.0863OpenAlexW8204747MaRDI QIDQ463287FDOQ463287

Authors: Victor Chepoi, Mark F. Hagen 

Publication date: 16 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We prove that the contact graph of a 2-dimensional CAT(0) cube complex $$ of maximum degree $Delta$ can be coloured with at most $epsilon(Delta)=MDelt{a}^{26}$ colours, for a fixed constant $M$. This implies that $$ (and the associated median graph) isometrically embeds in the Cartesian product of at most $epsilon(Delta)$ trees, and that the event structure whose domain is $$ admits a nice labeling with $epsilon(Delta)$ labels. On the other hand, we present an example of a 5-dimensional CAT(0) cube complex with uniformly bounded degrees of 0-cubes which cannot be embedded into a Cartesian product of a finite number of trees. This answers in the negative a question raised independently by F. Haglund, G. Niblo, M. Sageev, and the first author of this paper.

Full work available at URL: https://arxiv.org/abs/1107.0863

Recommendations

• Coloring hyperplanes of CAT(0) cube complexes
• Weak hyperbolicity of cube complexes and quasi-arboreal groups
• Finite asymptotic dimension for CAT(0) cube complexes.
• Automorphisms of contact graphs of CAT(0) cube complexes
• Graphs of some CAT(0) complexes

zbMATH Keywords

colouringisometric embeddinghyperplanemedian graphCAT(0) cube complexcontact graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Petri nets, event structures and domains. I
• Median algebras
• Cubulating small cancellation groups.
• Graphs of some CAT(0) complexes
• Embedding median algebras in products of trees.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of satisfiability problems
• The strong perfect graph theorem
• Retracts of hypercubes
• Title not available (Why is that?)
• Research announcement: The structure of groups with a quasiconvex hierarchy.
• Median Algebra
• Title not available (Why is that?)
• On a Coloring Problem.
• Title not available (Why is that?)
• Metric Ternary Distributive Semi-Lattices
• Cubulating spaces with walls.
• FROM WALL SPACES TO CAT(0) CUBE COMPLEXES
• The K(π, 1)-Problem for Hyperplane Complements Associated to Infinite Reflection Groups
• Ends of Group Pairs and Non-Positively Curved Cube Complexes
• Finiteness properties of cubulated groups.
• Codimension-1 subgroups and splittings of groups
• Title not available (Why is that?)
• Coxeter Groups act on CAT(0) cube complexes
• The singularity obstruction for group splittings
• Covering and coloring problems for relatives of intervals
• On the chromatic number of multiple interval graphs and overlap graphs
• Covering and coloring polygon-circle graphs
• Metric graph theory and geometry: a survey
• Graphs of acyclic cubical complexes
• Groups acting on cubes and Kazhdan’s property (T)
• Geodesics in CAT(0) cubical complexes
• Event structures and trace monoids
• Median graphs and Helly hypergraphs
• On the number of vertices and edges of the Buneman graph
• Finite labelling problem in event structures
• On groups acting on nonpositively curved cubical complexes
• Actions of picture groups on CAT(0) cubical complexes.
• On bounding the chromatic number of L-graphs
• The geometry and topology of reconfiguration
• Weak hyperbolicity of cube complexes and quasi-arboreal groups
• Combinatorics and geometry of finite and infinite squaregraphs
• Nice labeling problem for event structures: a counterexample
• Title not available (Why is that?)
• Embedding Topological Median Algebras in Products of Dendrons
• Stable networks and product graphs
• Isometries of CAT(0) cube complexes are semi-simple
• Median graphs, parallelism and posets
• From copair hypergraphs to median graphs with latent vertices
• Ramified rectilinear polygons: coordinatization by dendrons
• A Nice labelling for tree-like event structures of degree 3

Cited In (16)

• Coloring hyperplanes of CAT(0) cube complexes
• Lower bounds on cubical dimensionof $C’(1/6)$ groups
• Sample Compression Schemes for Balls in Graphs
• Title not available (Why is that?)
• The simplicial boundary of a CAT(0) cube complex
• Hyperbolic groups with almost finitely presented subgroups (with an appendix by Robert Kropholler and Federico Vigolo)
• Embedding median algebras in products of trees.
• Distance and routing labeling schemes for cube-free median graphs
• Weakly Modular Graphs and Nonpositive Curvature
• A counterexample to Thiagarajan's conjecture on regular event structures
• A Proof of Sageev’s Theorem on Hyperplanes in CAT(0) Cubical Complexes
• A new construction of \(\mathrm{CAT}(0)\) cube complexes
• Relating CAT(0) cubical complexes and flag simplicial complexes
• Embedding of two-colored right-angled Coxeter groups into products of two binary trees.
• Hierarchically hyperbolic spaces. I: Curve complexes for cubical groups
• Radial Schur multipliers on some generalisations of trees

This page was built for publication: On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463287)