Interval Orders and Shift G raphs
Interval Orders and Shift G raphs
复制标题
区间阶数和移位图
DOI：
10.1016/0095-8956(77)90048-x
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
V. Rodl
中科院分区：
文献类型：
--
作者：
Furedi;P. Hajnal;V. Rodl
有限偏序集（偏序集）P = (A， P)，如果有一个1 - 1函数赋值给每个元素A，则称为区间或-阶；6一个闭区间(ax, bx)的实线R P当且仅当x < y bx < ay在R .偏序集(A, P),高(A, P)的最大数量分在一个链,而暗(A, P)的维数(A, P),线性订单的最小数量的十字路口上偏序P . 1972年,即Ra ~ binovitch证明函数f (n) = max{暗(A, P):高度(A, P) < n, P是一个区间}定义和满足f {n) < (n + 1)。本文证明了f(n) = lglgn + (1/2 + o(l))（lglglgn）。其中的证明技术包括建立区间阶维数之间的联系，移位图的色数，以及计算子集格中反链数的经典问题。
A finite partially ordered set (poset) P = (A, P) is called an interval or der if there is a 1 — 1 function which assigns to each element a; 6 A a closed interval [ax , bx ] of the real line R so that x < y in P if and only if bx < ay in R. For a poset (A, P), height (A, P) is the maximum number of points in a chain, while dim(A, P) is the dimension of (A, P), the minimum number of linear orders on A whose intersection is the partial order P. In 1972, I. Ra~ binovitch proved that the function f(n) = max{dim(A, P) : height (A, P) < n, P is an interval order} is defined and satisfies f{n) < [n + 1]. In this paper, we show that f(n) = lg lgn + (1/2 + o(l))(lg lg lgn). The proof techniques in clude establishing links between the dimension of interval orders, the chromatic number of shift graphs, and the classical problem of counting the number of antichains in the subset lattice.