The stripping process can be slow: Part I

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 asH 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 constantc r , ksuch 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 approachesc r , ksufficiently 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 fromH 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.