Loading...
Please wait, while we are loading the content...
Similar Documents
Independent Sets in Graph Powers are Almost Contained in Juntas
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dinur, Irit Friedgut, Ehud Regev, Oded |
| Copyright Year | 2006 |
| Abstract | Let G = (V, E) be a simple undirected graph. Define G, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1, . . . , un) and (v1, . . . , vn) are adjacent if and only if ui is adjacent to vi 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. 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 [18]. This principle has already been shown in [11] 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cims.nyu.edu/~regev/papers/indset.pdf |
| Alternate Webpage(s) | http://www.cs.huji.ac.il/~dinuri/mypapers/DFR.pdf |
| Alternate Webpage(s) | http://www.math.huji.ac.il/~ehudf/docs/indset.pdf |
| Alternate Webpage(s) | http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/DFR.pdf |
| Alternate Webpage(s) | http://www.ma.huji.ac.il/~ehudf/docs/indset.pdf |
| Alternate Webpage(s) | http://math.huji.ac.il/~ehudf/docs/indset.pdf |
| Alternate Webpage(s) | http://www.cs.tau.ac.il/~odedr/papers/indset.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Analog Contain (action) Cylinder seal Fourier analysis Graph (discrete mathematics) Graph - visual representation Graph product Independent set (graph theory) Power (Psychology) Stationary process Vertex (graph theory) |
| Content Type | Text |
| Resource Type | Article |
