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
- Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez and Veit Wiechert, “Nowhere Dense Graph Classes and Dimension”, arXiv:1708.05424 (2019).
Progress summary
Never refreshed
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.