2022/07/23 by Chakraborty, Suman, Raaijmakers, Kjell, van der Hofstad, Remco
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2207.11471
In this note, we investigate fundamental relations between exploration processes in random graphs, and branching processes. We formulate a class of models that we call \em rank-k random graphs, and that are special in that their neighborhood explorations can be obtained by a \em thinning of multi-type branching processes. We show that any rank-2 random graph can be described in terms of thinning of a 2-type branching process, while for higher rank, it is not clear how many types are needed.