论文标题
在混合订单维度上
On hybrid order dimension
论文作者
论文摘要
诺伯特·维纳（Norbert Wiener）\ cite {wie}引入了间隔顺序的概念，以阐明时间瞬间的概念与一段时间的概念之间的关系。这是贝特兰·罗素（Bertrand Russell）当时遇到的问题。间隔订单在许多领域的纯数学，图理论，计算机科学和工程学领域都起着重要作用。间隔顺序的特殊情况是半手和线性顺序。所有这些概念在研究二进制关系的线性间隔和线性回波维度方面尤其重要。我们称之为{\ it混合顺序维度}的这种维度给出了线性顺序和间隔顺序（半架）维度的共同概括，并且可以说是有序设置复杂性的最重要度量。在本文中，我们提出了混合阶维理论的三个主要结果。更具体地说，我们获得了二元关系的必要条件，以具有间隔顺序（分别线性间隔顺序，线性比较）的延伸，以及间隔顺序的间隔订单实现（分别线性间隔顺序，线性式轴承）。我们还获得了间隔顺序（分别线性间隔阶，线性比较）维度的表征。由于二进制关系的混合顺序维度小于其（线性）顺序维度，因此这些结果将能够通过识别更有效的算法来改善图理论和计算机科学的已知结果。
The notion of interval order was introduced by Norbert Wiener \cite{wie} in order to clarify the relation between the notion of an instant of time and that of a period of time. This was a problem on which Bertrand Russell \cite{rus} worked at the time. Interval orders play an important role in many areas of pure and applied mathematics, graph theory, computer science and engineering. Special cases of interval order are the semiorder and linear order. All of these notions are especially important in the study of linear-interval and linear-semiorder dimension of a binary relation. This kind of dimension, which we call {\it hybrid order dimension}, gives a common generalization of linear order and interval order (semiorder) dimension and is arguably the most important measure of ordered set complexity. In this paper, we present three main results of the theory of hybrid order dimension. More specifically, we obtain necessary and sufficient conditions for a binary relation to have an interval order (resp. linear-interval order, linear-simiorder) extension, as well as an interval order realizer of interval orders (resp. linear-interval orders, linear-simiorders). We also obtain a characterization of the interval order (resp. linear-interval order, linear-simiorder) dimension. Because a binary relation's hybrid order dimension is less than its (linear) order dimension, these results will be able to improve known results in graph theory and computer science by identifying more efficient algorithms.
