Polynomial dimension bound for planar cover graph posets

Open problem: dimension of posets with planar cover graphs vs. height · arXiv:1612.07540

arXiv Informal medium confidence— first stated 2017-09-23

Authors: Gwenaël Joret, Piotr Micek, Veit Wiechert

Status partial high confidence

The conjecture asks whether the dimension of posets with planar cover graphs is bounded by a polynomial (or linear) function of their height. Kozik, Micek, and Trotter (arXiv:1907.00380, 2019) resolved the polynomial part affirmatively by proving an O(h^6) upper bound; Gorsky and Seweryn (arXiv:2103.15920, 2021) subsequently improved this to O(h^3). Whether a linear bound holds—analogous to the main theorem of the source paper for genuinely planar posets—remains open.

Cited literature (2)

partial Dimension is polynomial in height for posets with planar cover graphs (2019)

Jakub Kozik, Piotr Micek, William T. Trotter · Journal of Combinatorial Theory, Series B · arXiv:1907.00380

Proves that height-h posets with planar cover graphs have dimension O(h^6), establishing the first polynomial upper bound and resolving the polynomial-existence part of the conjecture.
partial Posets with k-outerplanar cover graphs have bounded dimension (2021)

Maximilian Gorsky, Michal T. Seweryn · arXiv preprint · arXiv:2103.15920

As a secondary result, improves the polynomial upper bound for posets with planar cover graphs from O(h^6) to O(h^3); the primary result establishes that k-outerplanar cover graphs force dimension O(k^3).

Reviewer notes. The polynomial-existence part of the conjecture is resolved: dimension is O(h^3) for height-h posets with planar cover graphs (Gorsky-Seweryn 2021). The linear-bound part remains open. Planarity is essential: there exist posets with exponential dimension in height whose cover graphs exclude K_5 as a minor, showing minor-freeness alone is insufficient for polynomial bounds.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It is not known whether the dimension of posets with planar cover graphs is bounded by a linear function of their height (or any polynomial function for that matter).

Context

The paper's main result (Theorem 1) establishes a linear bound $\dim(P) \leq 192h + 96$ for planar posets. The Streib–Trotter theorem guarantees only that some (exponential) function $f(h)$ bounds the dimension for the broader class of posets with planar cover graphs. Whether a polynomial — let alone linear — bound holds in this more general setting is explicitly left open by the authors, who also provide an improved lower bound of $2h - 2$ (Theorem 3) for this class.

Notes. Stated in running prose without a labelled theorem environment; clearly identified as an open problem by the authors.

Source paper

Planar posets have dimension at most linear in their height
Gwenaël Joret, Piotr Micek, Veit Wiechert · 2017-09-23
https://arxiv.org/abs/1612.07540 PDF source