Article in volume
Authors:
Title:
Covering the edges of a random hypergraph by cliques
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1333-1349
Received: 2021-03-24 , Revised: 2021-09-06 , Accepted: 2021-09-06 , Available online: 2021-09-17 , https://doi.org/10.7151/dmgt.2431
Abstract:
We determine the order of magnitude of the minimum clique cover of the edges of
a binomial, $r$-uniform, random hypergraph $G^{(r)}(n,p)$, $p$ fixed.
In doing so, we combine the ideas from the proofs of the graph case ($r=2$) in
Frieze and Reed [Covering the edges of a random graph by
cliques, Combinatorica 15 (1995) 489–497] and Guo, Patten, Warnke
[Prague dimension of random graphs, manuscript submitted for publication].
Keywords:
$r$-uniform random hypergraph, clique covering
References:
- N. Alon, J.-H. Kim and J. Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math. 100 (1997) 171–187.
https://doi.org/10.1007/BF02773639 - B. Bollobás, P. Erdős, J. Spencer and D.B. West, Clique coverings of the edges of a random graph, Combinatorica 13 (1993) 1–5.
https://doi.org/10.1007/BF01202786 - A. Frieze and B. Reed, Covering the edges of a random graph by cliques, Combinatorica 15 (1995) 489–497 (see arXiv:1103.4870v1 for corrected version).
https://doi.org/10.1007/BF01192522 - H. Guo, K. Patten and L. Warnke, Prague dimension of random graphs, manuscript submitted for publication.
- S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, 2000).
https://doi.org/10.1002/9781118032718 - J. Lehel, Covers in hypergraphs, Combinatorica 2 (1982) 305–309.
https://doi.org/10.1007/BF02579237 - C. McDiarmid, Concentration, in: Probabilistic Methods for Algorithmic Discrete Mathematics, (Springer, Berlin 1998) 195–248.
https://doi.org/10.1007/978-3-662-12788-9_6 - L. Warnke, On the method of typical bounded differences, Combin. Probab. Comput. 25 (2016) 269–299.
https://doi.org/10.1017/S0963548315000103
Close