The stripping process can be slow: Part I. Issue 1 (4th February 2018)

• Record Type: Journal Article
• Authors: Gao, Pu; Molloy, Michael
• Is Part Of: Random structures & algorithms. Volume 53:Issue 1(2018)
• Page Start: 76
• Page End: 139
• Publication Date: 2018-02-04
• Subjects: critical window -- k‐core -- number of iterations -- random hypergraphs -- the stripping process; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20760
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Given an integer k, we consider the parallel k ‐stripping process applied to a hypergraph H : removing all vertices with degree less than k in each iteration until reaching the k ‐core of H . Take H as H r ( n, m ) : a random r ‐uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing k, r ≥ 2 with ( k, r ) ≠ ( 2, 2 ), it has previously been proved that there is a constant c r, k such that for all m = cn with constant c ≠ c r, k, with high probability, the parallel k ‐stripping process takes O ( log ⁡ n ) iterations. In this paper, we investigate the critical case when c = c r, k + o ( 1 ) . We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches c r, k sufficiently fast. A second result we show involves the depth of a non‐ k ‐core vertex v : the minimum number of steps required to delete v from H r ( n, m ) where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non‐ k ‐core vertices.