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

DOI10.1016/J.JCTB.2013.04.003MaRDI QIDQ463287zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Mark F. Hagen

Publication date 16 October 2014

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

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

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)

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.

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

Cites work

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

Cited in

(16)

• Radial Schur multipliers on some generalisations of trees
• Coloring hyperplanes of CAT(0) cube complexes
• Lower bounds on cubical dimensionof $C’(1/6)$ groups
• Sample Compression Schemes for Balls in Graphs
• scientific article; zbMATH DE number 7561659 (Why is no real title available?)
• 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

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)