4
$\begingroup$

Given any poset $(P,\leq)$ we define the "direct neighbor graph" as follows. Let $$E_P = \big\{\{a,b\}: (a<b \text{ or } a>b) \text{ and } \; ]\min\{a,b\},\max\{a,b\}[ = \emptyset\big\}.$$ It is easy to see the $(P,E_P)$ is a simple undirected graph that can contain a $3$-clique, but not a $4$-clique. But can $\chi(P,E_P)$ become arbitrarily large?

EDIT. Peter Taylor points out that my remark on $3$-cliques is wrong - sorry about that.

Improve this question
$\endgroup$
3
  • $\begingroup$ Your "direct neighbour graph" looks like the transitive reduction, but I'm not sure how it could contain a 3-clique. $\endgroup$
    – Peter Taylor
    Commented Oct 11, 2017 at 14:16
  • $\begingroup$ Right @PeterTaylor - it can't...! If it cannot contain an odd cycle, then the answer is clear. Sorry for my mistake $\endgroup$
    – Dominic van der Zypen
    Commented Oct 11, 2017 at 14:35
  • 2
    $\begingroup$ It can contain an odd cycle. Consider a poset which is fully characterised by two chains: $a < b < c$ and $a < d < e < c$. Then $(P, E_P)$ is a single cycle of length 5. $\endgroup$
    – Peter Taylor
    Commented Oct 11, 2017 at 14:50

1 Answer 1

Reset to default
3
$\begingroup$

Yes, the chromatic number of a Hasse diagram can be arbitrarily large. Bollobás shows in the following article that for any $k$ there exists a finite lattice whose Hasse diagram is not $k$-colorable.

MR505730 05C15 (06A20) 
Bollobás, Béla Colouring lattices. Algebra Universalis 7 (1977), no. 3, 313–314.

Here are a few other papers that solve the problem, but I have not been able to find any freely available paper.

MR748915 05A17 (06B99 06D99) 
Nešetřil, Jaroslav; Rödl, Vojtěch Combinatorial partitions of finite posets and lattices—Ramsey lattices. Algebra Universalis 19 (1984), no. 1, 106–119.

MR1129613 05C15 (06A07) 
Kříž, Igor; Nešetřil, Jaroslav Chromatic number of Hasse diagrams, eyebrows and dimension. Order 8 (1991), no. 1, 41–48.
Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .