On ultralimits of sparse graph classes

zbMATH1336.05078MaRDI QIDQ286118FDOQ286118

Authors Michał Pilipczuk, Szymon Toruńczyk

Publication date 20 May 2016

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

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

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

nowhere densenessquasi-widenesssplitter gameultraproduct

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Ultraproducts and related constructions (03C20)

Abstract: The notion of nowhere denseness is one of the central concepts of the recently developed theory of sparse graphs. We study the properties of nowhere dense graph classes by investigating appropriate limit objects defined using the ultraproduct construction. It appears that different equivalent definitions of nowhere denseness, for example via quasi-wideness or the splitter game, correspond to natural notions for the limit objects that are conceptually simpler and allow for less technically involved reasonings.

Recommendations

• Characterisations of nowhere dense graphs (invited talk)
• On nowhere dense graphs
• Extremal problems for sparse graphs
• Nowhere dense graph classes and dimension
• Sparsity. Graphs, structures, and algorithms

Cites work

• Algorithmic meta-theorems
• Borel determinacy
• Homomorphism preservation on quasi-wide classes
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Sparsity. Graphs, structures, and algorithms
• Stable graphs
• Stable theories

Cited in

(8)

• From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
• Existence of modeling limits for sequences of sparse structures
• An undecidability result on limits of sparse graphs
• A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
• Extremal problems for sparse graphs
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Modeling limits in hereditary classes: reduction and application to trees
• Nowhere dense graph classes and dimension

This page was built for publication: On ultralimits of sparse graph classes

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