Approximating Cayley diagrams versus Cayley graphs

DOI10.1017/S0963548311000733zbMATH Open1247.05106arXiv1103.4968OpenAlexW2056900544MaRDI QIDQ2908133FDOQ2908133

Ádám Timár

Publication date: 4 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We construct a sequence of finite graphs that weakly converge to a Cayley graph, but there is no labelling of the edges that would converge to the corresponding Cayley diagram. A similar construction is used to give graph sequences that converge to the same limit, and such that a spanning tree in one of them has a limit that is not approximable by any subgraph of the other. We give an example where this subtree is a Hamiltonian cycle, but convergence is meant in a stronger sense. These latter are related to whether having a Hamiltonian cycle is a testable graph property.

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

zbMATH Keywords

Hamiltonian cyclegraph sequences

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Geometric group theory (20F65)

Cites Work

• Title not available (Why is that?)
• Processes on unimodular random networks
• Hyperlinearity, essentially free actions and \(L^2\)-invariants. The sofic property
• Hyperlinear and Sofic Groups: A Brief Guide
• Borel oracles. An analytical approach to constant-time algorithms

Cited In (1)

• Why do mathematicians need different ways of presenting mathematical objects? The case of Cayley graphs

This page was built for publication: Approximating Cayley diagrams versus Cayley graphs

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