Independent sets in graph powers are almost contained in juntas

Irit Dinur, Ehud Friedgut, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)77-97
Number of pages21
JournalGeometric and Functional Analysis
Volume18
Issue number1
DOIs
StatePublished - Apr 2008

Keywords

  • Discrete Fourier analysis
  • Independent sets
  • Intersecting families
  • Product graphs

ASJC Scopus subject areas

  • Analysis
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Independent sets in graph powers are almost contained in juntas'. Together they form a unique fingerprint.

Cite this