Connectedness of spheres in Cayley graphs
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 o...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2018 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2018
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/188410 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Connectedness of spheres in Cayley graphs / J. Brieussel, A. Gournay // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 190–246. — Бібліогр.: 40 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862746476984139776 |
|---|---|
| author | Brieussel, J. Gournay, A. |
| author_facet | Brieussel, J. Gournay, A. |
| citation_txt | Connectedness of spheres in Cayley graphs / J. Brieussel, A. Gournay // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 190–246. — Бібліогр.: 40 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | 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² 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.
|
| first_indexed | 2025-12-07T20:45:33Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-188410 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T20:45:33Z |
| publishDate | 2018 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Brieussel, J. Gournay, A. 2023-02-27T15:54:28Z 2023-02-27T15:54:28Z 2018 Connectedness of spheres in Cayley graphs / J. Brieussel, A. Gournay // Algebra and Discrete Mathematics. — 2018. — Vol. 26, № 2. — С. 190–246. — Бібліогр.: 40 назв. — англ. 1726-3255 2010 MSC: Primary 20F65; Secondary 20E22, 20F10. https://nasplib.isofts.kiev.ua/handle/123456789/188410 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² 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. Supported by the ERC-StG 277728 “GeomAnGroup”. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Connectedness of spheres in Cayley graphs Article published earlier |
| spellingShingle | Connectedness of spheres in Cayley graphs Brieussel, J. Gournay, A. |
| title | Connectedness of spheres in Cayley graphs |
| title_full | Connectedness of spheres in Cayley graphs |
| title_fullStr | Connectedness of spheres in Cayley graphs |
| title_full_unstemmed | Connectedness of spheres in Cayley graphs |
| title_short | Connectedness of spheres in Cayley graphs |
| title_sort | connectedness of spheres in cayley graphs |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/188410 |
| work_keys_str_mv | AT brieusselj connectednessofspheresincayleygraphs AT gournaya connectednessofspheresincayleygraphs |