A scaling limit for the length of the longest cycle in a sparse random graph

Abstract: We discuss the length of the longest cycle in a sparse random graph

G_{n, p}, p = c / n

.

c

constant. We show that for large

c

there is a function

f (c)

such that

L_{n} (c) / n o f (c)

a.s. The function

f (c) = 1 - s u m_{k = 1}^{i} n f t y p_{k} (c) e^{- k c}

where

p_{k}

is a polynomial in

k

. We are only able to explicitly give the values

p_{1}, p_{2}

, although we could in principle compute any

p_{k}

. We see immediately that the length of the longest path is also asymptotic to

f (c) n

w.h.p.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: A scaling limit for the length of the longest cycle in a sparse random graph