Keywords:-
Article Content:-
Abstract
In 1930, E. Szpilrajn proved that any order relation on a set $X$ can be extended to linear order on $X$. It also follows that order relation is the intersection of its linear extensions. In 1941 Dushnik and Miller introduced the concept of dimension of a poset $(X,P)$, denoted $Dim(X,P)$, as the smallest positive integer $n$ for which there exist linear extensions $L_1, L_2, ..., L_n$ of $P$ so that $P=L_1\cap L_2\cap ...\cap L_n$.
In this paper, we do literature survey of the research articles on dimension theory of posets. This survey provides an overview of key concepts, results, and challenges in dimension theory of posets. The survey also examines advanced topics like fractional dimension, geometric representations, and topological considerations. Open problems and future research directions, emphasizing the interdisciplinary potential of dimension theory in mathematics and computer science.
References:-
References
Edward Szpilrajn, `` Sur l'extension de l'ordre partiel," Fundamenta Mathematicae, vol.16 (1930), pp. 386-389.
Ben Dushnik and E. W. Miller ``Partially Ordered Sets" American Journal of Mathematics, Vol. 63, No. 3 (1941), pp. 600-610.
Horace Komm ``On the Dimension of Partially Ordered Sets" American Journal of Mathematics, Vol. 70, No. 3 (1948), pp. 507-520.
R. P. Dilworth ``A Decomposition Theorem for Partially Ordered Sets" Annals of Mathematics, Second Series, Vol. 51, No. 1 (1950), pp. 161-166.
Toshio Hiraguchi`` On the Dimension of partially Ordered Sets" The Science Reports of the Kanazawa University, Vol. 1, No. 2 (1951), pp. 77-94.
Toshio Hiraguchi ``On the Dimension of Orders" The Science Report of the Kanazawa University, Vol. IV, No. I, (1955), pp. l-20.
Baker, Flshburn and Roberts ``Partial Orders of Dimension 2, Interval Orders, and Interval Graphs." RAND Corporation, P-4376 (1970).
Kenneth P. Bogart``Maximal Dimensional Partially Ordered Sets I. HIRAGUCHI’S THEOREM" Discrete Mathematics vol. 5 (1973), pp. 21-31.
Kenneth P. Bogart and Willim T. Trotter, Jr.``Maximal Dimensional Partially Ordered Sets II. Characterization of $2n$-Element Posets with dimension $n$."Discrete Mathematics vol. 5 (1973), pp. 33-43.
Willim T. Trotter, Jr.``Dimension of the crown Skn" Discrete Mathematics, vol. 8 (1974), pp. 85-103.
David Kelly and Ivan Rival ``Crowns, Fences, and Dismantlable Lattices" Can. J. Math., Vol. XXVI, No. 5, (1974), pp. 1257-1271.
William T. Trotter, Jr.``Inequalities in Dimension Theory for Posets" Proceedings of the American Mathematical Society, Vol. 47, No. 2 (1975), pp. 311-316.
David Kelly and Ivan Rival``Planar Lattices" Can. J. Math., Vol. XXVII, No. 3, (1975), pp. 636-665.
Willim T. Trotter, Jr. ``Combinatorial Problems in Dimension Theory for Partially Ordered Sets "Discrete Mathematics vol. 16 (1976), pp. 361-381.
Willim T. Trotter, Jr., and John I. Moore, JR.``The Dimension of Planar Posets" Journal Of Combinatorial Theory, vol. (B) 22 (1977), pp. 54-67.
I. Rabinovitch ``The Dimension of Semiorders" Journal Of Combinatorial Theory, Series A25 (1978), pp. 50-61.
L. Babai and D. Duffus ``Dimension and automorphism groups ot lattices" Algebra Universalis, vol. 12 (1981), pp. 279-289.
M. K. Bennett ``The face lattice of an n-dimensional cube" Algebra Universalis, vol. 14 (1982), pp. 82-86.
Stefan Felsner, Irina Mustata and Martin Pergel ``The Complexity of the Partial Order Dimension Problem – Closing the Gap" SIAM Journal on Algebraic and Discrete Methods, vol. 3(3) (1982), pp. 351-358.
David Kelly and Willim T. Trotter, Jr.``Dimension Theory for Ordered Sets" Ordered Sets, ASIC,vol. 83 (1981), pp. 171-211.
Jeremy Spinrad and Jacobo Valdes ``Recognition and Isomorphism of Two Dimensional Partial Orders" Lecture Notes in Computer Science, vol. 154 (1983), pp. 676-686.
L. Hopkins`` Some problems involving combinatorial structures determined by intersections of intervals and arcs." Ph.D. thesis, University of South Carolina (1981)
Walter Schnyder ``Planar Graphs and Poset Dimension" Khmer Academy Pubhshers, Order, vol. 5 (1989), pp. 323-343.
P. Erdos, H. A. Kierstead and W. T. Trotter ``The Dimension of Random Ordered Sets" Random Structures and Algorithms, vol. 2(3) (1991), pp. 253-275.
G. R. Brightwell and E. R. Scheinerman`` Fractional Dimension of Partial Orders" Order, vol. 9 (1992), pp. 139-158.
Stefan Felsner and Willim T. Trotter ``On the fractional dimension of partially ordered sets" Discrete Mathematics, vol. 136 (1994), pp. 101-117.
Bayoumi, EL-Zahar And Khamis ``On recognizing the dimension of a poset" Journal of the Egyptian Mathematical Society, Vol. 6(1)(1998), pp. 1-8.
Serkan Hosten, and Walter D. Morris Jr.``The order dimension of the complete graph" Discrete Mathematics, vol. 201 (1999), pp. 133-139.
Michael Baym, Douglas B.West ``Bounds on the k-dimension of Products
of Special Posets" Order, vol. 30 (2013), pp. 779-796.
Bartłomiej Bosek, Kamil Kloch, Tomasz Krawczyk,
Piotr Micek``On-Line Dimension of Semi-Orders" Order, vol. 30 (2013), pp. 593-615.
Stefan Felsner, William T. Trotter, and Vett Wiechert ``The dimension of posets with planar cover graphs". Graphs Combin. vol 31(4) (2015), pp. 927-939.
Gwenael Joret, Piotr Micek, William T. Trotter, Ruidong Wang, Veit Wiechert``On the Dimension of Posets with Cover Graphs of Treewidth 2" Order vol. 34 (2017), pp. 185-234.
Jinha Kim, Ryan R. Martin, Tomas Masarik, Warren Shull, Heather C. Smith, Andrew Uzzell, and Zhiyu Wang ``On Difference Graphs and the local Dimension of Posets" European Journal of Combinatorics vol. 86 (2018) pp. 103074.
Alex Scott and David R. Wood ``Better Bounds for Poset Dimension
and Boxicity" Transactions of the American Mathematical Society vol. 373(3) (2019), pp. 2157-2172.
Fidel Barrera-Cruz, Thomas Prag, Heather C. Smith, Libby Taylor, William T. Trotter`` Comparing Dushnik-Miller Dimension,
Boolean Dimension and Local Dimension" Order, vol. 37 (2020), pp. 243-269.
Ashok Bhavale ``Dimension of dismantlable lattices" Journal of combinatorial theory, series A, (2024) (communicated).