RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 2018, том 26, выпуск 2, страницы 190–246 (Mi adm680)

Эта публикация цитируется в 1 статье

RESEARCH ARTICLE

Connectedness of spheres in Cayley graphs

Jérémie Brieussela, Antoine Gournayb

a Université de Montpellier, Institut Montpelliérain Alexander Grothendieck, 34095 Montpellier, France
b Institut für Geometrie, Fachrichtung Mathematik, TU Dresden, 01062 Dresden, Germany

Аннотация: We introduce the notion of connection thickness of spheres in a Cayley graph, related to dead-ends and their retreat depth. It was well-known that connection thickness is bounded for finitely presented one-ended groups. We compute that for natural generating sets of lamplighter groups on a line or on a tree, connection thickness is linear or logarithmic respectively. We show that it depends strongly on the generating set. We give an example where the metric induced at the (finite) thickness of connection gives diameter of order $n^2$ to the sphere of radius $n$. We also discuss the rarity of dead-ends and the relationships of connection thickness with cut sets in percolation theory and with almost-convexity. Finally, we present a list of open questions about spheres in Cayley graphs.

Ключевые слова: connectedness, sphere, connection thickness, Cayley graphs, dead-ends, wreath products.

MSC: 20F65

Поступила в редакцию: 06.02.2017
Исправленный вариант: 12.11.2018

Язык публикации: английский



© МИАН, 2024