# Posets as graphs with the direct neighbor relation

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.

• Your "direct neighbour graph" looks like the transitive reduction, but I'm not sure how it could contain a 3-clique. Oct 11 '17 at 14:16
• Right @PeterTaylor - it can't...! If it cannot contain an odd cycle, then the answer is clear. Sorry for my mistake Oct 11 '17 at 14:35
• 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. Oct 11 '17 at 14:50

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.

• Section 3.2.1 of Ruidong Wang's PhD thesis seems to work as a freely available constructive proof. Oct 11 '17 at 16:44