Technical Report 308-1991

Title

Colorings of Diagrams of Interval Orders and alpha-Sequences of Sets

Authors

Stefan Felsner and William T. Trotter

Publication

Discrete Mathematics, vol. to appear, 1991

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

defheight#1sf height(#1) We show that a proper coloring of the diagram of an interval order I may require 1 + lceillog₂heightI ceil colors and that 2 + lceillog₂heightI ceil colors always suffice. For the proof of the upper bound we use the following fact: A sequence C₁,ldots,C_h of sets (of colors) with the property hskip 1cm(α)quad `C_j otsubseteq C_i-1 cup C_i for all 1C<sub>i</sub>. We construct α-sequences of length `2^n-2 + lfloorn-1over 2 floor using n` colors. The lengh of α-sequences is bounded by `2^n-1 + lfloorn-1over 2 floor` and sequences of this lenght have some nice properties. Finally we use α-sequences for the construction of long cycles between two consecutive levels of the Boolean lattice. The best construction known until now could guarantee cycles of length Ω(N^c) where N is the number of vertices and c approx 0.85. We exhibit cycles of length geq 1over 4N.