Cuts in Cartesian Products of Graphs

Details Cuts in Cartesian Products of Graphs Cuts in Cartesian Products of Graphs

2011-05-17

arxiv.org/abs/1105.3383v1

Computer Science

Discrete Mathematics

16 pages

Scientific paper

The k-fold Cartesian product of a graph G is defined as a graph on tuples (x_1, ..., x_k) 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 the statements of Kahn, Kalai and Linial (KKL Theorem) and that of Friedgut (Friedgut's Junta Theorem), for the setting of Cartesian products of arbitrary graphs. We also extends the work on studying isoperimetric constants for these graphs to the value of semidefinite relaxations for expansion. We connect the optimal values of the relaxations for computing expansion, given by various semidefinite hierarchies, for G and G^k.

Affiliated with

Also associated with

No associations

Rating

Cuts in Cartesian Products of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cuts in Cartesian Products of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cuts in Cartesian Products of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727846