2011/05/17 by Sushant Sachdeva, Sachdeva, Sushant, Madhur Tulsiani +1
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1105.3383
openalex publication_date 2011/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-fold Cartesian product of a graph G is defined as a graph on k-tuples of vertices, where two tuples are connected if they form an edge in one of the positions and are equal in the rest. Starting with G as a single edge gives Gk as a k-dimensional hypercube. We study the distributions of edges crossed by a cut in Gk across the copies of G in different positions. This is a generalization of the notion of influences for cuts on the hypercube. We show the analogues of results of Kahn, Kalai, and Linial (KKL Theorem [KahnKL88]) and that of Friedgut (Friedgut's Junta theorem [Friedgut98]), for the setting of Cartesian products of arbitrary graphs. Our proofs extend the arguments of Rossignol [Rossignol06] and of Falik and Samorodnitsky [FalikS07], to the case of arbitrary Cartesian products. We also extend the work on studying isoperimetric constants for these graphs [HoudreT96, ChungT98] to the value of semidefinite relaxations for edge-expansion. We connect the optimal values of the relaxations for computing expansion, given by various semidefinite hierarchies, for G and Gk.