Jagiellonian University Repository

Local dimension is unbounded for planar posets

pcg.skipToMenu

Local dimension is unbounded for planar posets

Show full item record

dc.contributor.author Bosek, Bartłomiej [SAP11019936] pl
dc.contributor.author Grytczuk, Jarosław [SAP11019186] pl
dc.contributor.author Trotter, William T. pl
dc.date.accessioned 2021-02-25T10:24:18Z
dc.date.available 2021-02-25T10:24:18Z
dc.date.issued 2020 pl
dc.identifier.issn 1097-1440 pl
dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/265754
dc.language eng pl
dc.rights Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa *
dc.rights.uri http://creativecommons.org/licenses/by-nd/4.0/pl/legalcode *
dc.title Local dimension is unbounded for planar posets pl
dc.type JournalArticle pl
dc.description.physical P4.28 pl
dc.abstract.en In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetřil and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. Since that time, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. pl
dc.description.volume 27 pl
dc.description.number 4 pl
dc.identifier.doi 10.37236/9258 pl
dc.identifier.eissn 1077-8926 pl
dc.title.journal The Electronic Journal of Combinatorics pl
dc.language.container eng pl
dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl
dc.subtype Article pl
dc.identifier.articleid P4.28 pl
dc.rights.original CC-BY-ND; otwarte czasopismo; ostateczna wersja wydawcy; w momencie opublikowania; 0 pl
dc.identifier.project 2013/11/D/ST6/03100 pl
dc.identifier.project 2015/17/B/ST1/02660 pl
dc.identifier.project Simons Foundation Collaborative Research Grant pl
dc.identifier.project ROD UJ / OP pl
.pointsMNiSW [2020 A]: 100


Files in this item

This item appears in the following Collection(s)

Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa Except where otherwise noted, this item's license is described as Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa