2024/12/17 by Peled, Yuval, Peleg, Niv · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.13127
We study the maximum dimension d=d(n,p) for which an Erdős-Rényi G(n,p) random graph is d-rigid. Our main results reveal two different regimes of rigidity in G(n,p) separated at pc=C_*log n/n,~C_*=2/(1-log 2) -- the point where the graph's minimum degree exceeds half its average degree. We show that if p < (1-ε)pc , then d(n,p) is asymptotically almost surely (a.a.s.) equal to the minimum degree of G(n,p). In contrast, if pc ≤ p = o(n-1/2) then d(n,p) is a.a.s. equal to (1/2 + o(1))np. The second result confirms, in this regime, a conjecture of Krivelevich, Lew, and Michaeli.