MTSU/Vanderbilt Graph Theory and Combinatorics Seminar- Sieve Methods in Random Graph Theory-Vanderbilt: Buttrick 206- MTSU-KOM 204
In this talk, we introduce the Turan sieve, which was first developed by Pal Turan to give a simpler proof of the Hardy and Ramanujan result on the normal order of the number of prime factors of a positive integer. The Turan sieve and its complement the simple sieve were developed further by Ram Murty and Yu-Ru Liu to problems in combinatorics. We apply the Turan sieve and the simple sieve here to examine the diameter of a random graph. In particular, we obtain upper and lower bounds on the probability of a random graph on n vertices having diameter d for some d >= 2 with edge probability p, where the edges are chosen independently. An interesting feature revealed in these results is that the Turan sieve and the simple sieve “almost completely” complement each other. This result recovers an asymptotic result on the diameter of a random graph by Bela Bollobas, as well provide concrete upper and lower bounds for n and p (the number of vertices and the edge probability in the random graph in question respectively) in certain ranges.