Sparsity and dimension

DOI10.1007/S00493-017-3638-4MaRDI QIDQ1715074zbMATH OpenOpenAlexFDO

Authors Gwenaël Joret, Piotr Micek, Veit Wiechert

Publication date 1 February 2019

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

sparsitycover graphsbounded expansionposets of bounded height

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07)

Abstract: We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nev{s}etv{r}il and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with bounded book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor. We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.

Recommendations

• Sparsity and dimension
• Minors and dimension
• Minors and dimension
• Nowhere dense graph classes and dimension
• Topological minors of cover graphs and dimension

Cited in

(15)

• Concepts of dimension for convex geometries
• scientific article; zbMATH DE number 6797621 (Why is no real title available?)
• Nowhere dense graph classes and dimension
• Statistical sparsity
• Minors and dimension
• Dimension is polynomial in height for posets with planar cover graphs
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Planar posets that are accessible from below have dimension at most 6
• Cover graphs and order dimension
• Minors and dimension
• Sparse Rational Univariate Representation
• Topological minors of cover graphs and dimension
• Better bounds for poset dimension and boxicity
• Sparsity and dimension
• Excluding a ladder

This page was built for publication: Sparsity and dimension

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