An undecidability result on limits of sparse graphs

zbMATH Open1244.05134arXiv1108.4995MaRDI QIDQ426892FDOQ426892

Authors: Endre Csóka 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Given a set 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 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.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On ultralimits of sparse graph classes
• On limits of sparse random graphs
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• Limits of near-coloring of sparse graphs
• From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
• On limits of finite graphs
• Undecidability of linear inequalities in graph homomorphism densities
• Extremal results in sparse pseudorandom graphs
• On Turan's theorem for sparse graphs

zbMATH Keywords

bounded degree graphsunimodular random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Cited In (2)

• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• Undecidability of Winkler's \(r\)-neighborhood problem for covering digraphs

This page was built for publication: An undecidability result on limits of sparse graphs

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