2017/10/25 by Fidel Barrera-Cruz, Thomas Prag, Barrera-Cruz, Fidel +7
Computer Science · Mathematics · #05C35 #05D10 #06A07 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1710.09467
openalex publication_date 2017/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The original notion of dimension for posets is due to Dushnik and Miller and\nhas been studied extensively in the literature. Quite recently, there has been\nconsiderable interest in two variations of dimension known as Boolean dimension\nand local dimension. For a poset P, the Boolean dimension of P and the\nlocal dimension of P are both bounded from above by the dimension of P and\ncan be considerably less. Our primary goal will be to study analogies and\ncontrasts among these three parameters. As one example, it is known that the\ndimension of a poset is bounded as a function of its height and the tree-width\nof its cover graph. The Boolean dimension of a poset is bounded in terms of the\ntree-width of its cover graph, independent of its height. We show that the\nlocal dimension of a poset cannot be bounded in terms of the tree-width of its\ncover graph, independent of height. We also prove that the local dimension of a\nposet is bounded in terms of the path-width of its cover graph. In several of\nour results, Ramsey theoretic methods will be applied.\n