2012/11/07 by Michael Langberg, Langberg, Michael, Dan Vilenchik +1
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Information Theory (cs.IT) #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.1211.1467
openalex publication_date 2012/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G=(V,E), an integer k, and a function fG:Vk × Vk → 0,1, the kth graph product of G w.r.t fG is the graph with vertex set Vk, and an edge between two vertices x=(x1,...,xk) and y=(y1,...,yk) iff fG(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 fG of the form fG(x,y)=1 iff there are at least t indices i ∈ [k] s.t. (xi,yi)∈ E, where t ∈ [k] is a fixed parameter in fG. 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 Gk 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 kth bi-partite graph product of G w.r.t fG is the bi-partite graph with vertex sets Xk and Yk and edges between x ∈ Xk and y ∈ Yk iff fG(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.