Geodesic
Covering the Edges of a Random Hypergraph by Cliques
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1333-1349 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2022_42_4_a17,
     author = {R\"odl, Vojt\v{e}ch and Ruci\'nski, Andrzej},
     title = {Covering the {Edges} of a {Random} {Hypergraph} by {Cliques}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1333--1349},
     year = {2022},
     volume = {42},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a17/}
}
TY  - JOUR
AU  - Rödl, Vojtěch
AU  - Ruciński, Andrzej
TI  - Covering the Edges of a Random Hypergraph by Cliques
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1333
EP  - 1349
VL  - 42
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a17/
LA  - en
ID  - DMGT_2022_42_4_a17
ER  - 
%0 Journal Article
%A Rödl, Vojtěch
%A Ruciński, Andrzej
%T Covering the Edges of a Random Hypergraph by Cliques
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1333-1349
%V 42
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a17/
%G en
%F DMGT_2022_42_4_a17
Rödl, Vojtěch; Ruciński, Andrzej. Covering the Edges of a Random Hypergraph by Cliques. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1333-1349. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a17/

[1] 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

[2] 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

[3] 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

[4] H. Guo, K. Patten and L. Warnke, Prague dimension of random graphs, manuscript submitted for publication.

[5] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (Wiley, 2000). https://doi.org/10.1002/9781118032718

[6] J. Lehel, Covers in hypergraphs, Combinatorica 2 (1982) 305–309. https://doi.org/10.1007/BF02579237

[7] 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

[8] L. Warnke, On the method of typical bounded differences, Combin. Probab. Comput. 25 (2016) 269–299. https://doi.org/10.1017/S0963548315000103