NDLI: Independent Sets in Graph Powers are Almost Contained in Juntas

Please wait, while we are loading the content...

Geometric and Functional Analysis : Volume 27

Geometric and Functional Analysis : Volume 26

Geometric and Functional Analysis : Volume 25

Geometric and Functional Analysis : Volume 24

Geometric and Functional Analysis : Volume 23

Geometric and Functional Analysis : Volume 22

Geometric and Functional Analysis : Volume 21

Geometric and Functional Analysis : Volume 20

Geometric and Functional Analysis : Volume 19

Geometric and Functional Analysis : Volume 18

Geometric and Functional Analysis : Volume 18, Issue 6, March 2009

Geometric and Functional Analysis : Volume 18, Issue 5, February 2009

Geometric and Functional Analysis : Volume 18, Issue 4, December 2008

Geometric and Functional Analysis : Volume 18, Issue 3, September 2008

Geometric and Functional Analysis : Volume 18, Issue 2, July 2008

Geometric and Functional Analysis : Volume 18, Issue 1, April 2008

Density Theorems for Complete Minimal Surfaces in $${\mathbb{R}}^{3}$$

Length and Stable Length

Independent Sets in Graph Powers are Almost Contained in Juntas

Non-Wrapping of Hyperbolic Interval Bundles

The De Rham Decomposition Theorem For Metric Spaces

Boolean Functions with small Spectral Norm

On Polynomials Sharing Preimages of Compact Sets, and Related Questions

Lie Atoms and Their Deformations

Contributions to the Hypergeometric Function Theory of Heckman and Opdam: Sharp Estimates, Schwartz Space, Heat Kernel

L 2-Cohomology for Von Neumann Algebras

Hall’s Theorem for Limit Groups

Geometric and Functional Analysis : Volume 17

Geometric and Functional Analysis : Volume 16

Geometric and Functional Analysis : Volume 15

Geometric and Functional Analysis : Volume 14

Geometric and Functional Analysis : Volume 13

Geometric and Functional Analysis : Volume 12

Geometric and Functional Analysis : Volume 11

Geometric and Functional Analysis : Volume 10

Geometric and Functional Analysis : Volume 9

Geometric and Functional Analysis : Volume 8

Geometric and Functional Analysis : Volume 7

Independent Sets in Graph Powers are Almost Contained in Juntas

Content Provider	Springer Nature Link
Author	Dinur, Irit Friedgut, Ehud Regev, Oded
Copyright Year	2008
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.
Starting Page	77
Ending Page	97
Page Count	21
File Format	PDF
ISSN	1016443X
Journal	Geometric and Functional Analysis
Volume Number	18
Issue Number	1
e-ISSN	14208970
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2008-01-30
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Independent sets intersecting families product graphs discrete Fourier analysis Analysis
Content Type	Text
Resource Type	Article
Subject	Analysis Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Independent Sets in Graph Powers are Almost Contained in Juntas

Independent sets in graph powers are almost contained in juntas (2006)

Independent sets in graph powers are almost contained in juntas (2006)

Independent sets in graph powers are almost contained in juntas (2006)

Intersecting families are essentially contained in juntas (2007)

Intersecting families are essentially contained in juntas (2007)

Nearly flat almost monotone measures are big pieces of lipschitz graphs

Fourier analysis and large independent sets in powers of complete graphs (2006).

Sets which are almost starshaped

Independent Sets in Graph Powers are Almost Contained in Juntas

Similar Documents

Independent Sets in Graph Powers are Almost Contained in Juntas

Independent sets in graph powers are almost contained in juntas (2006)

Independent sets in graph powers are almost contained in juntas (2006)

Independent sets in graph powers are almost contained in juntas (2006)

Intersecting families are essentially contained in juntas (2007)

Intersecting families are essentially contained in juntas (2007)

Nearly flat almost monotone measures are big pieces of lipschitz graphs

Fourier analysis and large independent sets in powers of complete graphs (2006).

Sets which are almost starshaped

Independent Sets in Graph Powers are Almost Contained in Juntas