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.
References
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
No solutions have been posted yet.