Tight products and Expansion - Computer Science > Discrete MathematicsReportar como inadecuado




Tight products and Expansion - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this paper we study a new product of graphs called {\em tight product}. Agraph $H$ is said to be a tight product of two undirected multi graphs $G 1$and $G 2$, if $VH=VG 1\times VG 2$ and both projection maps $VH\toVG 1$ and $VH\to VG 2$ are covering maps. It is not a priori clear whentwo given graphs have a tight product in fact, it is $NP$-hard to decide. Weinvestigate the conditions under which this is possible. This perspectiveyields a new characterization of class-1 $2k+1$-regular graphs. We alsoobtain a new model of random $d$-regular graphs whose second eigenvalue isalmost surely at most $Od^{3-4}$. This construction resembles random graphlifts, but requires fewer random bits.



Autor: Amit Daniely, Nathan Linial

Fuente: https://arxiv.org/







Documentos relacionados