On the Prague dimension of sparse random graphs

Abstract

The Prague dimension of a graph $G$ is defined as the minimum number of complete graphs whose direct product contains $G$ as an induced subgraph. Introduced in the 1970s by NeÅ¡etřil, Pultr, and Rödl -- and motivated by the work of Dushnik and Miller, as well as by the induced Ramsey theorem -- determining the Prague dimension of a graph is a notoriously hard problem. In this paper, we show that for all $\epsilon >0$ and $p$ such that $n^{-1+\epsilon }\le p\le n^{-\epsilon }$, with high probability the Prague dimension of $G_{n,p}$ is $\hat{I}{˜}_{\epsilon }(pn)$, which improves upon a recent result by Molnar, Rödl, Sales and Schacht. Inspired by the work of Bennett and Bohman, our approach centres on analysing a random greedy process that builds an independent set of size $\hat{I}\text{c◯}(p^{-1}\log pn)$ by iteratively selecting vertices uniformly at random from the common non-neighbourhood of those already chosen. Using the differential equation method, we show that every non-edge is essentially equally likely to be covered by this process, which is key to establishing our bound.

19 pages