On the chromatic number of random subgraphs of a certain distance graph

We study the chromatic number of the graph G(n,3,1), whose vertices are all 3-element subsets of [n]={1,2,…,n}, and there is an edge between two vertices if the corresponding subsets intersect in exactly one element. This graph was employed by Larman and Rogers to provide an estimate for the chromatic number of Rn, and quite recently Balogh, Kostochka and Raigorodskii found that the chromatic number of this graph is asymptotically n2∕6. We consider a random setting of this problem, where every edge of the original graph is removed with a fixed probability 1∕2, independently of the other edges, and prove that the chromatic number of this random graph is asymptotically n212log2n with high probability.