The bounded-expansion characterization by poset dimension

Let C\mathcal{C} be a monotone class of graphs. For each fixed h1h\geq 1, consider posets of height at most hh whose cover graphs belong to C\mathcal{C}. Bounded-expansion characterization. The class C\mathcal{C} has bounded expansion if and only if these posets have bounded dimension for every fixed hh. 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

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.