Premium
The stripping process can be slow: Part I
Author(s) -
Gao Pu,
Molloy Michael
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20760
Subject(s) - hypergraph , combinatorics , vertex (graph theory) , mathematics , constant (computer programming) , integer (computer science) , stripping (fiber) , degree (music) , upper and lower bounds , discrete mathematics , physics , computer science , mathematical analysis , graph , materials science , acoustics , composite material , programming language
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.