Extremal graphs of order dimension 4

Abstract

We study the maximal number of edges of a graph on $p$ vertices of order dimension 4. We will show that the lower bound for this number is greater than $\frac{3}{8}p^{2} + 2p - 13$. In particular the Turn-4 graph on $p$ vertices does not have the maximal number of edges among the graphs of order dimension 4.