Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T23:40:23.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximating Cayley Diagrams Versus Cayley Graphs

Published online by Cambridge University Press:  04 January 2012

ÁDÁM TIMÁR
ÁDÁM TIMÁR*
Affiliation:
Fakultät für Mathematik, Universität Wien, Nordbergstrasse 15, 1090 Wien, Austria (e-mail: madaramit@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 Hamiltonian cycle in one of them has a limit that is not approximable by any subgraph of the other. We give an example where this holds, but convergence is meant in a stronger sense. This is related to whether having a Hamiltonian cycle is a testable graph property.

Keywords

Primary 68R1020F65

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 4 , July 2012 , pp. 635 - 641
Copyright
Copyright © Cambridge University Press 2012

References

[1]Abért, M. and Szegedy, B. (2009) Residually finite groups, graph limits and dynamics. Banff reports, available at www.birs.ca/workshops/2009/09frg147/report09frg147.pdf.Google Scholar
[2]Aldous, D. and Lyons, R. (2007) Processes on unimodular random networks. Electr. Commun. Prob. 12 1454–1508.Google Scholar
[3]Aldous, D. and Steele, J. M. (2004) The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (Kesten, H., ed.), Vol. 110 of Encyclopaedia Math. Sci., Springer, pp. 1–72.Google Scholar
[4]Bollobás, B. (1981) The independence ratio of regular graphs. Proc. Amer. Math. Soc. 83 433–436.CrossRefGoogle Scholar
[5]de la Harpe, P. (2000) Topics in Geometric Group Theory, Chicago Lectures in Mathematics Series, The University of Chicago Press.Google Scholar
[6]Elek, G. (2010) Parameter testing in bounded degree graphs of subexponential growth. Random Struct. Alg. 37 248–270.CrossRefGoogle Scholar
[7]Elek, G. and Lippner, G. (2010) Borel oracles: An analytic approach to constant time algorithms. Proc. Amer. Math. Soc. 138 2939–2947.CrossRefGoogle Scholar
[8]Elek, G. and Szabó, E. (2005) Hyperlinearity, essentially free actions and L2-invariants: The sofic property. Math. Ann. 332 421–441.CrossRefGoogle Scholar
[9]Lovász, L. (2009) Very large graphs. In Current Developments in Mathematics 2008, International Press of Boston, pp. 67–128.Google Scholar
[10]Pestov, V. G. (2008) Hyperlinear and sofic groups: A brief guide. Bull. Symbolic Logic 14 449–480.CrossRefGoogle Scholar