×

The stripping process can be slow. II. (English) Zbl 1388.05168

Summary: This paper is a continuation of previous results [the author and M. Molloy , “The stripping process can be slow. I”, Random Struct. Algorithms (to appear)] on the stripping number of a random uniform hypergraph, and the maximum depth over all non-\(k\)-core vertices. The previous results focus on the supercritical case, whereas this work analyzes these parameters in the subcritical regime and inside the critical window.

MSC:

05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Achlioptas and M. Molloy, {\it The solution space geometry of random linear equations}, Random Structures Algorithms, 46 (2015), pp. 197-231. · Zbl 1309.05129
[2] B. Bollobás, {\it The evolution of sparse graphs}, Graph Theory Combin., Academic Press, 1984, pp. 35-57. · Zbl 0552.05047
[3] B. Bollobás, {\it A probabilistic proof of an asymptotic formula for the number of labelled regular graphs}, European J. Combin., 1 (1980), pp. 311-316. · Zbl 0457.05038
[4] B. Bollobás, J. Kim, and J. Verstraëte, {\it Regular subgraphs of random graphs}, Random Structures Algorithms, 29 (2006), pp. 1-13. · Zbl 1101.05061
[5] J. Cain and N. Wormald, {\it Encores on cores}, Electron. J. Combin., 13 (2006). · Zbl 1112.05094
[6] V. Chvátal, {\it Almost all graphs with 1.44n edges are 3-colorable}, Random Structures Algorithms, 2 (1991), pp. 11-28. · Zbl 0715.05026
[7] S. Cocco, O. Dubois, J. Mandler, and R. Monasson, {\it Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices}, Phys. Rev. Lett., 90 (2003), 047205.
[8] C. Cooper, {\it The cores of random hypergraphs with a given degree sequence}, Random Structures Algorithms, 25 (2004), pp. 353-375.
[9] J. Ding, A. Sly, and N. Sun, {\it Proof of the Satisfiability Conjecture for Large \(k\)}, preprint, arXiv:1411.0650, 2014. · Zbl 1321.68304
[10] P. Gao, {\it Analysis of the Parallel Peeling Algorithm: A Short Proof}, preprint, arXiv:1402.7326, 2014.
[11] P. Gao and M. Molloy, {\it The stripping process can be slow: Part} I, Random Structures Algorithms, to appear. · Zbl 1401.05205
[12] P. Gao and M. Molloy, {\it Inside the clustering window for random linear equations}, Random Structures Algorithms, 52 (2018), pp. 197-218. · Zbl 1396.60008
[13] M. Ibrahimi, Y. Kanoria, M. Kraning, and A. Montanari, {\it The set of solutions of random XORSAT formulae}, in Proceedings of SODA, 2012, pp. 760-779. · Zbl 1341.68061
[14] S. Janson and M. Luczak, {\it A simple solution to the \(k\)-core problem}, Random Structures Algorithms, 30 (2007), pp. 50-62. · Zbl 1113.05091
[15] J. H. Kim, {\it Poisson cloning model for random graphs}, in Proceedings of the International Congress of Mathematicians, Vol. III, European Mathematical Society, Zürich, 2006, pp. 873-897. · Zbl 1100.05093
[16] J. Jiang, M. Mitzenmacher, and J. Thaler, {\it Parallel peeling algorithms}, in Proceedings of SPAA (ACM), 2014, pp. 319-330.
[17] T. Łuczak, {\it Size and connectivity of the \(k\)-core of a random graph}, Discrete Math., 91 (1991), pp. 61-68. · Zbl 0752.05046
[18] T. Łuczak, {\it Sparse random graphs with a given degree sequence}, Random Graphs, Vol. 2, Wiley, New York, 1992, pp. 165-182. · Zbl 0817.05057
[19] M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, {\it Two solutions to diluted p-spin models and XORSAT problems}, J. Stat. Phys., 111 (2003), pp. 505-533. · Zbl 1049.82073
[20] M. Molloy, {\it Cores in random hypergraphs and Boolean formulas}, Random Structures Algorithms, 27 (2005), pp. 124-135. · Zbl 1068.05063
[21] M. Molloy and B. Reed, {\it A critical point for random graphs with a given degree sequence}, Random Structures Algorithms, 6 (1995), pp. 161-179. · Zbl 0823.05050
[22] B. Pittel, J. Spencer, and N. Wormald, {\it Sudden emergence of a giant \(k\)-core in a random graph}, J. Combin. Theory Ser. B, 67 (1996), pp. 111-151. · Zbl 0860.05065
[23] M. Pretti and M. Weigt, {\it Sudden emergence of \(q\)-regular subgraphs in random graphs}, Europhys. Lett., 75 (2006), pp. 8-14.
[24] O. Riordan, {\it The k-core and branching processes}, Combin. Probab. Comput., 17 (2008), pp. 111-136. · Zbl 1136.05071
[25] C. Sato,{\it On the robustness of random k-cores}, European J. Combin., 41 (2014), pp. 163-182. · Zbl 1300.05186
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.