On ultralimits of sparse graph classes

MaRDI QIDQ286118zbMATH OpenFDO

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, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p32

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

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

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.

Review text

Summary: 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)

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

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)