Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers

We study distance graphs with exponentially large chromatic numbers and without $k$-cliques, that is, complete subgraphs of size $k$. Explicit constructions of such graphs use vectors in the integer lattice. For a large class of graphs we find a sharp threshold for containing a $k$-clique. This enables us to improve the lower bounds for the maximum of the chromatic numbers of such graphs. We give a new probabilistic approach to the construction of distance graphs without $k$-cliques, and this yields better lower bounds for the maximum of the chromatic numbers for large $k$.