TY - JOUR

T1 - Independent sets in graph powers are almost contained in juntas

AU - Dinur, Irit

AU - Friedgut, Ehud

AU - Regev, Oded

N1 - Funding Information:
Keywords and phrases: Independent sets, intersecting families, product graphs, discrete Fourier analysis AMS Mathematics Subject Classification: 05d05 I.D. is the incumbent of the Harry and Abe Sherman Lectureship Chair at Hebrew Univeristy. Her research is supported by the Israel Science Foundation and by the Binational Science Foundation. E.F.’s research is supported in part by the Israel Science Foundation, grant no. 0329745. O.R. is supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848.

PY - 2008/4

Y1 - 2008/4

N2 - Let G = (V,E) be a simple undirected graph. Define G n , the n-th power of G, as the graph on the vertex set V n in which two vertices (u 1, . . . , u n ) and (v 1, . . . , v n ) are adjacent if and only if u i is adjacent to v i in G for every i. We give a characterization of all independent sets in such graphs whenever G is connected and non-bipartite. Consider the stationary measure of the simple random walk on G n . We show that every independent set is almost contained with respect to this measure in a junta, a cylinder of constant co-dimension. Moreover we show that the projection of that junta defines a nearly independent set, i.e. it spans few edges (this also guarantees that it is not trivially the entire vertex-set). Our approach is based on an analog of Fourier analysis for product spaces combined with spectral techniques and on a powerful invariance principle presented in [MoOO]. This principle has already been shown in [DiMR] to imply that independent sets in such graph products have an influential coordinate. In this work we prove that in fact there is a set of few coordinates and a junta on them that capture the independent set almost completely.

AB - Let G = (V,E) be a simple undirected graph. Define G n , the n-th power of G, as the graph on the vertex set V n in which two vertices (u 1, . . . , u n ) and (v 1, . . . , v n ) are adjacent if and only if u i is adjacent to v i in G for every i. We give a characterization of all independent sets in such graphs whenever G is connected and non-bipartite. Consider the stationary measure of the simple random walk on G n . We show that every independent set is almost contained with respect to this measure in a junta, a cylinder of constant co-dimension. Moreover we show that the projection of that junta defines a nearly independent set, i.e. it spans few edges (this also guarantees that it is not trivially the entire vertex-set). Our approach is based on an analog of Fourier analysis for product spaces combined with spectral techniques and on a powerful invariance principle presented in [MoOO]. This principle has already been shown in [DiMR] to imply that independent sets in such graph products have an influential coordinate. In this work we prove that in fact there is a set of few coordinates and a junta on them that capture the independent set almost completely.

KW - Discrete Fourier analysis

KW - Independent sets

KW - Intersecting families

KW - Product graphs

UR - http://www.scopus.com/inward/record.url?scp=42749093780&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=42749093780&partnerID=8YFLogxK

U2 - 10.1007/s00039-008-0651-1

DO - 10.1007/s00039-008-0651-1

M3 - Article

AN - SCOPUS:42749093780

SN - 1016-443X

VL - 18

SP - 77

EP - 97

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 1

ER -