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 -