Independent sets in graph powers are almost contained in juntas.

*(English)*Zbl 1147.05058Summary: 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},\dots, u_{n})\) and \((v_{1},\dots, 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 [E. Mossel, R. O’Donnell, O. Regev, J. E. Steif and B. Sudakov, “Noise stability of functions with low influences: invariances and optimality, Proc. 46th IEEE Symp. on Foundations of Computer Sciences, 21–30 (2005)]. This principle has already been shown in [I. Dinur, E. Mossel and O. Regev, Conditional hardness for approximate coloring, in: Proc. 38th ACM Symp. on Theory of Computing, STOC’06, ACM, New York, 344–353 (2006)] 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.

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 [E. Mossel, R. O’Donnell, O. Regev, J. E. Steif and B. Sudakov, “Noise stability of functions with low influences: invariances and optimality, Proc. 46th IEEE Symp. on Foundations of Computer Sciences, 21–30 (2005)]. This principle has already been shown in [I. Dinur, E. Mossel and O. Regev, Conditional hardness for approximate coloring, in: Proc. 38th ACM Symp. on Theory of Computing, STOC’06, ACM, New York, 344–353 (2006)] 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.

##### MSC:

05D05 | Extremal set theory |