1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Covering the Edges of a Random Hypergraph by Cliques

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1333 - 1349
Received: 24 Mar 2021
Accepted: 06 Sep 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

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

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

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

[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 Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo