An undecidability result on limits of sparse graphs

MaRDI QIDQ426892zbMATHFDO

Authors Endre Csóka

Publication date 12 June 2012

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

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

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

zbMATH Keywords

bounded degree graphsunimodular random graph

Mathematics Subject Classification ID

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

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.

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

Cited in

(2)

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

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)