2022/12/05 by Tian, Fang, Yang, Yiting
#05C80 #05D40 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2212.02001
For a fixed integer r\geqslant 3, let ℍr(n,p) be a random r-uniform hypergraph on the vertex set [n], where each r-set is an edge randomly and independently with probability p. The random r-generalized triadic process starts with a complete bipartite graph Kr-2,n-r+2 on the same vertex set, chooses two distinct vertices x and y uniformly at random and iteratively adds \x,y\ as an edge if there is a subset Z with size r-2, denoted as Z=\z1,⋯,zr-2\, such that \x,zi\ and \y,zi\ for 1\leqslant i\leqslant r-2 are already edges in the graph and \x,y, z1,⋯,zr-2\ is an edge in ℍr(n,p). The random triadic process is an abbreviation for the random 3-generalized triadic process. Korándi et al. proved a sharp threshold probability for the propagation of the random triadic process, that is, if p= cn - \frac 12 for some positive constant c, with high probability, the triadic process reaches the complete graph when c> \frac 12 and stops at O(n\frac 32) edges when c< \frac 12. In this note, we consider the final size of the random r-generalized triadic process when p=o( n- \frac 12log α(3-r) n) with a constant α> \frac 12. We show that the generated graph of the process essentially behaves like \mathbbG(n,p). The final number of added edges in the process, with high probability, equals \frac 12n2p(1± o(1)) provided that p=ω(n-2). The results partially complement the ones on the case of r=3.