Edge distribution in generalized graph products

arXiv1211.1467MaRDI QIDQ6236962FDOQ6236962

Authors: Michael Langberg, Dan Vilenchik 

Publication date: 7 November 2012

Abstract: Given a graph $G=(V,E)$, an integer $k$, and a function $f_G:V^{k}imes{V}^{k}o0,1$, the $k^{th}$ graph product of $G$ w.r.t $f_G$ is the graph with vertex set $V^k$, and an edge between two vertices $x=(x_1,\mathrm{...},x_k)$ and $y=(y_1,\mathrm{...},y_k)$ iff $f_G(x,y)=1$. Graph products are a basic combinatorial object, widely studied and used in different areas such as hardness of approximation, information theory, etc. We study graph products for functions $f_G$ of the form $f_G(x,y)=1$ iff there are at least $t$ indices $iin[k]$ s.t. $(x_i,y_i)inE$, where $tin[k]$ is a fixed parameter in $f_G$. This framework generalizes the well-known graph tensor-product (obtained for $t=k$) and the graph or-product (obtained for $t=1$). The property that interests us is the edge distribution in such graphs. We show that if $G$ has a spectral gap, then the number of edges connecting "large-enough" sets in $G^k$ is "well-behaved", namely, it is close to the expected value, had the sets been random. We extend our results to bi-partite graph products as well. For a bi-partite graph $G=(X,Y,E)$, the $k^{th}$ bi-partite graph product of $G$ w.r.t $f_G$ is the bi-partite graph with vertex sets $X^k$ and $Y^k$ and edges between $xin{X}^k$ and $yin{Y}^k$ iff $f_G(x,y)=1$. Finally, for both types of graph products, optimality is asserted using the "Converse to the Expander Mixing Lemma" obtained by Bilu and Linial in 2006. A byproduct of our proof technique is a new explicit construction of a family of co-spectral graphs.

This page was built for publication: Edge distribution in generalized graph products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236962)