Geodesic
An undecidability result on limits of sparse graphs
Endre Csóka1
1Eötvös Loránd University, Budapest, Hungary
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a set $\mathcal{B}$ of finite rooted graphs and a radius $r$ as an input, we prove that it is undecidable to determine whether there exists a sequence $(G_i)$ of finite bounded degree graphs such that the rooted $r$-radius neighbourhood of a random node of $G_i$ is isomorphic to a rooted graph in $\mathcal{B}$ with probability tending to 1. Our proof implies a similar result for the case where the sequence $(G_i)$ is replaced by a unimodular random graph.
DOI : 10.37236/2340
Classification : 05C42, 05C80, 05C07
Mots-clés : bounded degree graphs, unimodular random graph

Endre Csóka  1

1 Eötvös Loránd University, Budapest, Hungary 
@article{10_37236_2340,
     author = {Endre Cs\'oka},
     title = {An undecidability result on limits of sparse graphs},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {2},
     doi = {10.37236/2340},
     zbl = {1244.05134},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2340/}
}
TY  - JOUR
AU  - Endre Csóka
TI  - An undecidability result on limits of sparse graphs
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2340/
DO  - 10.37236/2340
ID  - 10_37236_2340
ER  - 
%0 Journal Article
%A Endre Csóka
%T An undecidability result on limits of sparse graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2340/
%R 10.37236/2340
%F 10_37236_2340
Endre Csóka. An undecidability result on limits of sparse graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2340

Cité par Sources :