Extremal paths in inhomogenous random graphs (Q2288750)

This paper considers an independent random graph over \(n\) nodes with edge probability \(p_n(e_{ij})\) on each edge \(e_{ij}\) satisfying \(a_n(i)=\frac{1}{n-1}\sum_{j\not=i}p_n(e_{ij})\) and \(a_n(i,S)=|S|^{-1}\sum_{j\in S}p_n(e_{ij})\). Suppose there is a probability sequence \(p_n\) and constants \(\alpha\in(0,1)\) and \(\beta>0\) such that for all large \(n\), \(\min a_n(i)\ge p_n\ge(\sqrt{\alpha\beta n})^{-1}\) and \(\min_i\min_{i\not\in S,|S|\ge\alpha n p_n}a_n(i,S)\ge\beta p_n\). For every \(\epsilon<\min(1/6,1-\alpha)\) there is a \(Q\ge1\) such that for all \(n\ge Q\) it holds: For any \(\delta\in(0,1)\), the length of the longest path \(L_n\) satisfies \(\mathbb{P}(L_n\ge n-ne^{-\delta v_n})\ge1-2e^{-(1-\delta)v_n}\), where \(v_n=\min(\alpha\beta n p_n^2,(\varepsilon^2/5)np_n-\ln n)\ge1\).