Paths of specified length in random k-partite graphsReport as inadecuate

Paths of specified length in random k-partite graphs - Download this document for free, or read online. Document in PDF available to download.

1 CSA - Department of Computer Science and Automation Bangalore

Abstract : Fix positive integers k and l. Consider a random k-partite graph on n vertices obtained by partitioning the vertex set into V i, i=1, \ldots,k each having size Ω n and choosing each possible edge with probability p. Consider any vertex x in any V i 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 V i 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.

Keywords : random graphs paths bijections

Author: C.R. Subramanian -



Related documents