Boolean dimension and dim-boundedness: Planar cover graph with a zero

arXiv2206.06942MaRDI QIDQ6402072FDOQ6402072

Authors: Heather Smith Blake, Piotr Micek, William T. Trotter 

Publication date: 14 June 2022

Abstract: In 1989, Nev{s}etv{r}il and Pudl'ak posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most $13$. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of $mathcalO(logn)$ bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with $mathcalO(lo{g}^{2}n)$ bits [Thorup JACM 2004], and it remains open to determine whether a scheme using labels with $mathcalO(logn)$ bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.

This page was built for publication: Boolean dimension and dim-boundedness: Planar cover graph with a zero

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402072)