Name
Abstract | ||
|---|---|---|
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 G^k as a k-dimensional hypercube. We study the distributions of edges crossed by a cut in G^k 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 G^k. |
Year | Venue | Keywords |
|---|---|---|
2011 | Clinical Orthopaedics and Related Research | discrete mathematics |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Tuple,Cartesian product,Mathematical proof,Isoperimetric inequality,Mathematics,Hypercube | Journal | abs/1105.3 |
Citations | PageRank | References |
3 | 0.53 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sushant Sachdeva | 1 | 3 | 1.20 |
| Madhur Tulsiani | 2 | 358 | 24.60 |