On ultralimits of sparse graph classes

zbMATH Open1336.05078arXiv1508.07256MaRDI QIDQ286118FDOQ286118

Authors: Michał Pilipczuk, Szymon Toruńczyk 

Publication date: 20 May 2016

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

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.

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

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

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

zbMATH Keywords

nowhere densenessquasi-widenesssplitter gameultraproduct

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)