Covering the edges of a random hypergraph by cliques (Q2158205): Difference between revisions

The paper examines the minimal number of cliques needed to cover all the edges of a random regular hypergraph. This random object is defined as follows: we fix an integer \(r\geq 2\), a real number \(0<p<1\), and the number of vertices, which is \(n\). Then, each subset of the vertices of size \(r\) becomes a hyperedge independently with probability \(p\). Notice that the case \(r=2\) corresponds to the Erdős-Rényi graph on \(n\) vertices. The minimal number of covering cliques is interesting also because it is equal to the representation number of the hypergraph. In a representation of a hypergraph, we take an arbitrary set \(S\), and assign a subset of \(S\) to each vertex of the hypergraph (which is assumed to be \(r\)-uniform now). Then, \(r\) vertices form an edge if and only if the intersection of the corresponding subsets of \(S\) is the empty set. The question is the following: how many elements does \(S\) have to have so that it can admit a representation of the \(r\)-uniform hypergraph \(H\)? This is denoted by \(\vartheta_1(H)\), and this is called the representation number of \(H\). The goal of the paper is to determine the magnitude of \(\vartheta_1(H)\), where \(r\) and \(p\) are fixed, and the number of vertices, \(n\) tends to infinity. The authors provide lower and upper bounds which differ only in a constant factor. The lower bound generalizes the results of \textit{A. Frieze} and \textit{B. Reed} [Combinatorica 15, No. 4, 489--497 (1995; Zbl 0839.05084)] and \textit{H. Guo} et al. [``Prague dimension of random graphs'', Preprint, \url{ arXiv:2011.09459}] in the case of \(r=2\). The proof is based on a first-moment method, in particular, on calculating the expected number of certain cliques covering the edges of \(H\). By showing an expanding property of random \(r\)-uniform hypergraphs, the authors prove a concentration inequality for this quantity. Another key element of the proof is finding a pair of descending graphs and ascending cliques in a wide family of hypergraphs.