Paths of specified length in random k-partite graphsReportar como inadecuado

Paths of specified length in random k-partite graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: C.R. Subramanian -



Documentos relacionados