Covering the edges of a random hypergraph by cliques

Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80)

Review text

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Covering the edges of a random hypergraph by cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158205)