The bounded-expansion characterization by poset dimension
The bounded-expansion characterization by poset dimension
Let be a monotone class of graphs. For each fixed , consider posets of height at most whose cover graphs belong to . Bounded-expansion characterization. The class has bounded expansion if and only if these posets have bounded dimension for every fixed . This conjecture proposes that bounded expansion is exactly the graph-class condition governing dimension bounds for bounded-height posets; the forward direction follows from the results discussed in the paper, while the backward direction is identified as an open problem.
Sources & referencesView supporting material
Primary source
Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez and Veit Wiechert, “Nowhere Dense Graph Classes and Dimension”, arXiv:1708.05424 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.