×

Comparing Dushnik-Miller dimension, Boolean dimension and local dimension. (English) Zbl 1481.06003

Summary: The original notion of dimension for posets is due to Dushnik and Miller and has been studied extensively in the literature. Quite recently, there has been considerable interest in two variations of dimension known as Boolean dimension and local dimension. For a poset \(P\), the Boolean dimension of \(P\) and the local dimension of \(P\) are both bounded from above by the dimension of \(P\) and can be considerably less. Our primary goal will be to study analogies and contrasts among these three parameters. As one example, it is known that the dimension of a poset is bounded as a function of its height and the tree-width of its cover graph. The Boolean dimension of a poset is bounded in terms of the tree-width of its cover graph, independent of its height. We show that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of height. We also prove that the local dimension of a poset is bounded in terms of the path-width of its cover graph. In several of our results, Ramsey theoretic methods will be applied.

MSC:

06A07 Combinatorics of partially ordered sets
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barrera-Cruz, F.; Felsner, S.; Mészáros, T.; Micek, P.; Smith, H.; Taylor, L.; Trotter, WT, Separating tree-chromatic number from path-chromatic number, J. Combin. Theory Ser. B, 138, 206-218 (2019) · Zbl 1415.05113 · doi:10.1016/j.jctb.2019.02.003
[2] Biró, C.; Hamburger, P.; Pór, A.; Trotter, WT, Forcing posets with large dimension to contain large standard examples, Graphs Combin., 32, 861-880 (2016) · Zbl 1406.06001 · doi:10.1007/s00373-015-1624-4
[3] Bosek, B., Grytczuk, J., Trotter, W.T.: Local dimension is unbounded for planar posets. arXiv:1712.06099
[4] Dilworth, RP, A decomposition theorem for partially ordered sets, Ann. Math. (2), 41, 161-166 (1950) · Zbl 0038.02003 · doi:10.2307/1969503
[5] Dushnik, B., Concerning a certain set of arrangements, Proc. Amer. Math. Soc., 1, 788-796 (1950) · Zbl 0040.29501 · doi:10.1090/S0002-9939-1950-0038922-4
[6] Dushnik, B.; Miller, EW, Partially ordered sets, Amer. J. Math., 63, 600-610 (1941) · JFM 67.0157.01 · doi:10.2307/2371374
[7] Felsner, S., Mészáros, T., Micek, P.: Boolean dimension and Tree-width. arXiv:1707.06114
[8] Felsner, S.; Trotter, WT; Wiechert, V., The dimension of posets with planar cover graphs, Graphs Combin., 31, 927-939 (2015) · Zbl 1328.06004 · doi:10.1007/s00373-014-1430-4
[9] Gambosi, G., Nešetřil, J., Talamo, M.: Posets, Boolean representations and quick path searching. In: Automata, Languages and Programming, 14th International Colloquium, ICALP87, Proceedings, Lecture Note Series in Computer Science, vol. 267, pp 404-424 (1987) · Zbl 0642.68116
[10] Gambosi, G.; Nešetřil, J.; Talamo, M., On locally presented posets, Theoret. Comput. Sci., 70, 251-260 (1990) · Zbl 0701.06003 · doi:10.1016/0304-3975(90)90125-2
[11] Graham, RL; Rothschild, BL; Spencer, JH, Ramsey Theory (1990), New York: Wiley, New York · Zbl 0705.05061
[12] Hiraguchi, T., On the dimension of orders, Sci. Rep. Kanazawa Univ., 4, 1-20 (1955) · Zbl 0200.00046
[13] Hoşten, S.; Morris, WD, The dimension of the complete graph, Discrete Math., 201, 133-139 (1998) · Zbl 0932.06003 · doi:10.1016/S0012-365X(98)00315-X
[14] Howard, DM; Streib, N.; Trotter, WT; Walczak, B.; Wang, R., Dimension of posets with planar cover graphs excluding two long incomparable chains, J. Combin. Theory Ser. A, 164, 1-23 (2019) · Zbl 1407.05067 · doi:10.1016/j.jcta.2018.11.016
[15] Joret, G.; Micek, P.; Milans, K.; Trotter, WT; Walczak, B.; Wang, R., Tree-width and dimension, Combinatorica, 36, 431-450 (2016) · Zbl 1389.06004 · doi:10.1007/s00493-014-3081-8
[16] Joret, G., Micek, P., Ossona de Mendez, P., Wiechert, V.: Nowhere dense graph classes and dimension. arXiv:1708.05424 · Zbl 1463.05312
[17] Joret, G.; Micek, P.; Wiechert, V., Planar posets have dimension at most linear in their height, SIAM J. Discrete Math., 34, 1, 2754-2790 (2017) · Zbl 1423.06008 · doi:10.1137/17M111300X
[18] Joret, G.; Micek, P.; Trotter, WT; Wang, R.; Wiechert, V., On the dimension of posets with cover graphs of tree-width 2, Order, 34, 185-234 (2017) · Zbl 1387.06002 · doi:10.1007/s11083-016-9395-y
[19] Kelly, D., On the dimension of partially ordered sets, Discrete Math., 35, 135-156 (1981) · Zbl 0468.06001 · doi:10.1016/0012-365X(81)90203-X
[20] Kim, J., Martin, R.R., Masařík, T., Shull, W., Smith, H., Uzzell, A., Wang, Z.: On difference graphs and the local dimension of posets. arXiv:1803.08641 · Zbl 1437.05198
[21] Kimble, R.J.: Extremal Problems in Dimension Theory for Partially Ordered Sets, Ph.D. Thesis, Massachusetts Institute of Technology (1973)
[22] Kimble, R.J.: Personal communication
[23] Kleitman, DJ; Markovsky, G., On Dedekind’s problem: The number of isotone Boolean functions, II, Trans. Amer. Math. Soc., 213, 373-390 (1975) · Zbl 0321.05010
[24] Kozik, J., Krawczyk, T., Micek, P., Trotter, W.T.: Personal communication
[25] Mészáros, T., Micek, P., Trotter, W.T.: Boolean dimension, components and blocks. arXiv:1801.00288
[26] Micek, P., Walczak, B.: Personal communication
[27] Milliken, K., A Ramsey theorem for trees, J. Combin. Theory Ser. A, 26, 215-237 (1979) · Zbl 0429.05035 · doi:10.1016/0097-3165(79)90101-8
[28] Nešetřil, J.; Pudlák, P., A Note on Boolean dimension of posets, irregularities of partitions, Algorithms Combin., 8, 137-140 (1989) · Zbl 0683.06003
[29] Spencer, J., Minimal scrambling sets of simple orders, Acta Math. Hungar., 22, 349-353 (1972) · Zbl 0242.05001 · doi:10.1007/BF01896428
[30] Streib, N.; Trotter, WT, Dimension and height for posets with planar cover graphs, Europ. J. Comb., 35, 474-489 (2014) · Zbl 1325.06006 · doi:10.1016/j.ejc.2013.06.017
[31] Trotter, WT, Irreducible posets with arbitrarily large height exist, J. Combin. Theory Ser. A, 17, 337-344 (1974) · Zbl 0293.06001 · doi:10.1016/0097-3165(74)90098-3
[32] Trotter, WT, Inequalities in dimension theory for posets, Proc. Amer. Math. Soc., 47, 311-316 (1975) · Zbl 0314.06001 · doi:10.1090/S0002-9939-1975-0369192-2
[33] Trotter, WT, Combinatorics and Partially Ordered Sets: Dimension Theory (1992), Baltimore: The Johns Hopkins University Press, Baltimore · Zbl 0764.05001
[34] Trotter, WT; Moore, JI, The dimension of planar posets, J. Combin. Theory Ser. B, 21, 51-67 (1977) · Zbl 0307.06003
[35] Trotter, WT; Walczak, B., Boolean dimension and local dimension, Elec. Notes Discret. Math., 61, 1047-1053 (2017) · Zbl 1397.06003 · doi:10.1016/j.endm.2017.07.071
[36] Trotter, WT; Wang, R., Planar posets, dimension, breadth and the number of minimal elements, Order, 33, 333-346 (2016) · Zbl 1359.06003 · doi:10.1007/s11083-015-9369-5
[37] Ueckerdt, T.: Personal communication
[38] Trotter, W.T., Walczak, B., Wang, R.: Dimension and Cut Vertices: An Application of Ramsey Theory, Connections in Discrete Mathematics. In: Butler, S. et al. (eds.) , pp 187-199. Cambridge University Press (2018) · Zbl 1398.05215
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.