Prague dimension of random graphs (Q6081403)

The Prague dimension \(\text{dim}_{P}(G)\) of a graph \(G\) is the smallest \(d\) such that \(G\) is an induced subgraph of the tensor product of \(d\) complete graphs, where the tensor product of graphs \(H_{1},H_{2},\dots, H_{d}\) has as vertex set the Cartesian product of their vertex sets with \((u_{1},u_{2},\ldots ,u_{d})\) adjacent to \((v_{1},v_{2},\ldots, v_{d})\) if and only if \(v_{i}\) is adjacent to \(u_{i}\) for all \(1\leq i\leq d\). There are several equivalent definitions of (and names for) this quantity, which was introduced by \textit{Nešetřil} and \textit{V. Rödl} [Discrete Math. 23, 49--55 (1978; Zbl 0388.05036)], and is linked to efficient representations of graphs. However, it seems in general hard to calculate.\par The paper under review studies the Prague dimension of random graphs \(G(n,p)\) for \(0<p<1\) fixed. The main result is that there are constants \(c\) and \(C\) such that whp - i.e. with probability tending to 1 as \(n\rightarrow\infty\) - we have \[\frac{cn}{\log(n)} \leq \text{dim}_{P}(G(n,p)) \leq \frac{Cn}{\log(n)}.\] The lower bound was basically already known and follows from the fact that \(\text{dim}_{P}(G)\) is the minimum number of subgraphs of \(\overline{G}\) (the complement of \(G\)) such that every subgraph is a disjoint union of cliques and every edge of \(\overline{G}\) is in at least one of the subgraphs (and every pair of vertices is not adjacent in some subgraph). This means it is either \(\text{cc}^{\prime}(\overline{G})\), the chromatic index of the hypergraph of clique coverings of the edges of \(G\), or one more than that. This in turn is bounded below by the maximum degree of such a hypergraph, which \textit{Z. Füredi} and \textit{I. Kantor} [SIAM J. Discrete Math. 32, No. 2, 1016--1028 (2018; Zbl 1387.05237)] showed is \(\Theta(n/\log(n))\) for \(G(n,p)\) with constant \(p\). \par Thus the main interest is in the upper bound. Very crudely, the strategy is to carefully combine two greedy approaches; firstly, a \lq nibble-type\rq\, algorithm to decompose the edges of \(\overline{G(n,p)}\) into cliques of order \(O(\log(n))\) and secondly an algorithm to rearrange these cliques into \(O(n.log(n))\) subgraphs consisting of disjoint cliques. Key to getting all this to work is a version of the Pippinger-Spencer theorem about colouring random hypergraphs which works when the hypergraphs have hyperedges of size \(O(\log(n))\) (as opposed to constant size in the original version) which is of independent interest. The analysis uses the differential equations method. Other results from this substantial paper include the proof of a conjecture of \textit{Z. Füredi} and \textit{I. Kantor} [SIAM J. Discrete Math. 32, No. 2, 1016--1028 (2018; Zbl 1387.05237)] on thickness and chromatic index of clique coverings of random graphs and a strengthening of an old result of \textit{A. Frieze} and \textit{B. Reed} [Combinatorica 15, No. 4, 489--497 (1995; Zbl 0839.05084)] on the smallest number of cliques required to cover (or partition) the edges of \(G(n,p)\), the latter result being that both the covering number and partition number are whp bounded above and below by constant multiples of \(n^{2}p/(\log_{1/p}(n))^{2}\). (For general graphs, the clique partition number can be a lot more than the clique covering number.)