INTERVAL DIMENSION IS A COMPARABILITY INVARIANT

被引：13
作者：
HABIB, M
KELLY, D
MOHRING, RH
机构：
[1] UNIV MANITOBA,DEPT MATH & ASTRON,WINNIPEG R3T 2N2,MANITOBA,CANADA
[2] TECH UNIV BERLIN,FACHBEREICH MATH,W-1000 BERLIN 12,GERMANY
来源：
DISCRETE MATHEMATICS | 1991年 / 88卷 / 2-3期
基金：
加拿大自然科学与工程研究理事会;
关键词：
D O I：
10.1016/0012-365X(91)90010-Y
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We allow orders (ordered sets) to be infinite. An interval order is an order that does not contain 2 + 2 as an induced suborder. The interval dimension of an order is the minimum number of interval orders (on the same set) whose intersection is the given order. We show that orders with the same comparability graph have the same interval dimension, answering a question raised by Dagan, Golumbic and Pinter for finite orders. We also obtain the analogous result for some other notions of dimension.
引用
收藏
页码：211 / 229
页数：19
相关论文
共 18 条
  • [1] ARDITTI JC, 1980, J LOND MATH SOC, V21, P31
  • [2] ON THE FERRERS DIMENSION OF A DIGRAPH
    COGIS, O
    [J]. DISCRETE MATHEMATICS, 1982, 38 (01) : 47 - 52
  • [3] COGIS O, 1980, THESIS U P M CURIE
  • [4] TRAPEZOID GRAPHS AND THEIR COLORING
    DAGAN, I
    GOLUMBIC, MC
    PINTER, RY
    [J]. DISCRETE APPLIED MATHEMATICS, 1988, 21 (01) : 35 - 46
  • [5] Partially ordered sets
    Dushnik, B
    Miller, EW
    [J]. AMERICAN JOURNAL OF MATHEMATICS, 1941, 63 : 600 - 610
  • [6] Fishburn P. C., 1985, INTERVAL ORDERS INTE
  • [7] TRANSITIV ORIENTIERBARE GRAPHEN
    GALLAI, T
    [J]. ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2): : 25 - &
  • [8] DIMENSION TRANSITIVE ORIENTIERBARER GRAPHEN
    GYSIN, R
    [J]. ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1977, 29 (3-4): : 313 - 316
  • [9] HABIB M, 1990, 2441990 TU BERL REP
  • [10] Hiraguchi T., 1951, SCI REP KANAZAWA, P77
12