The bounded-expansion characterization via poset dimension

Let C\mathcal{C} be a class of graphs closed under taking subgraphs. For each integer h1h\geq 1, consider posets of height hh whose cover graphs belong to C\mathcal{C}.

Bounded-expansion characterization. The class C\mathcal{C} has bounded expansion if and only if, for each h1h\geq 1, the posets of height hh whose cover graphs are in C\mathcal{C} have bounded dimension.

The theorem proved in the paper establishes one of the two implications; the converse remains open. Thus the conjecture proposes a characterization of bounded-expansion graph classes in terms of uniformly bounded dimension for bounded-height posets with cover graphs in the class.

Sources & referencesView supporting material

Primary source

Gwenaël Joret, Piotr Micek and Veit Wiechert, “Sparsity and dimension”, arXiv:1507.01120 (2017).

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.