Optimization in graphical small cancellation theory

DOI10.1016/J.DISC.2023.113842MaRDI QIDQ6197706zbMATH OpenOpenAlexFDO

Publication date 19 February 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

Cayley graph graphical cancellation labelling

Infinite graphs (05C63) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Cancellation theory of groups; application of van Kampen diagrams (20F06) Geometric group theory (20F65)

Abstract: Gromov (2003) constructed finitely generated groups whose Cayley graphs contain all graphs from a given infinite sequence of expander graphs of unbounded girth and bounded diameter-to-girth ratio. These so-called Gromov monster groups provide examples of finitely generated groups that do not coarsely embed into Hilbert space, among other interesting properties. If graphs in Gromov's construction admit graphical small cancellation labellings, then one gets similar examples of Cayley graphs containing all the graphs of the family as isometric subgraphs. Osajda (2020) recently showed how to obtain such labellings using the probabilistic method. In this short note, we simplify Osajda's approach, decreasing the number of generators of the resulting group significantly.

Review text

Let \(\mathcal{G}=(G_{n})_{n \geq 1}\) be a sequence of bounded degree graphs, whose girth tends to infinity. The sequence \(\mathcal{G}\) is \(\mathsf{dg}\)-bounded if the ratio between the diameter and the girth of each \(G_{n}\) is bounded by a constant. \textit{M. Gromov} in [Geom. Funct. Anal. 13, No. 1, 73--146 (2003; Zbl 1122.20021)] proved that there is a finitely generated group \(\Gamma\) whose Cayley graph contains (in a certain metric sense) all the members of \(\mathcal{G}\). By choosing \(\mathcal{G}\) as a family of suitable expander graphs, this implies that such a group \(\Gamma\) has a number of pathological properties, in partucular \(\Gamma\) do not coarsely embed into an Hilbert space. If graphs in Gromov's construction admit graphical small cancellation labellings, then one gets similar examples of Cayley graphs containing all the graphs of the family as isometric subgraphs. \textit{D. Osajda} in [Acta Math. 225, No. 1, 159--191 (2020; Zbl 1512.05352)] showed how to obtain such labellings using the probabilistic method. In the paper under review the authors present a simplified version of the proof of existence of the labelling of Osajda, and significantly decrease the number of generators of \(\Gamma\), and thus the degree of the corresponding Cayley graph. As a concrete example they consider the \(\mathsf{dg}\)-bounded sequence \(\mathcal{G}=(G_{n})\) of cubic Ramanujan graphs introduced by \textit{P. Chiu} in [Combinatorica 12, No. 3, 275--285 (1992; Zbl 0770.05062)] and prove the existence of a group with 96 generators, whose Cayley graph contains all the graphs from \(\mathcal{G}\) as isometric subgraphs. For the same family, the construction of Osajda requires about \(10^{272}\) generators.

Recommendations

Cites work

Cited in

(1)

Small but unwieldy: a lower bound on adjacency labels for small classes

This page was built for publication: Optimization in graphical small cancellation theory

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