Discrete Mathematics & Theoretical Computer Science, Vol 4, No 2 (2001)

Font Size:  Small  Medium  Large

Paths of specified length in random k-partite graphs

C. R. Subramanian


Fix positive integers k and l. Consider a random k-partite graph on n vertices obtained by partitioning the vertex set into Vi, (i=1, …,k) each having size Ω(n) and choosing each possible edge with probability p. Consider any vertex x in any Vi and any vertex y. We show that the expected number of simple paths of even length l between x and y differ significantly depending on whether y belongs to the same Vi (as x does) or not. A similar phenomenon occurs when l is odd. This result holds even when k,l vary slowly with n. This fact has implications to coloring random graphs. The proof is based on establishing bijections between sets of paths.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page