TY - JOUR
T1 - Graph products, fourier analysis and spectral techniques
AU - Alon, N.
AU - Dinur, I.
AU - Friedgut, E.
AU - Sudakov, B.
N1 - Funding Information:
N.A.’s research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. E.F.’s research supported in part by the Israel Science Foundation. Part of this research was done while E.F. visited Microsoft Research and the Institute for Advanced Study in Princeton. B.S.’s research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.
PY - 2004/10
Y1 - 2004/10
N2 - We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others, complete graphs, line graphs of regular graphs which contain a perfect matching and Kneser graphs. In many cases this also characterizes the optimal colorings of these products. We show that the independent sets induced by the base graph are the only maximum-size independent sets. Furthermore we give a qualitative stability statement: any independent set of size close to the maximum is close to some independent set of maximum size. Our approach is based on Fourier analysis on Abelian groups and on Spectral Techniques. To this end we develop some basic lemmas regarding the Fourier transform of functions on {0,...., r - 1}n, generalizing some useful results from the {0, 1}n case.
AB - We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others, complete graphs, line graphs of regular graphs which contain a perfect matching and Kneser graphs. In many cases this also characterizes the optimal colorings of these products. We show that the independent sets induced by the base graph are the only maximum-size independent sets. Furthermore we give a qualitative stability statement: any independent set of size close to the maximum is close to some independent set of maximum size. Our approach is based on Fourier analysis on Abelian groups and on Spectral Techniques. To this end we develop some basic lemmas regarding the Fourier transform of functions on {0,...., r - 1}n, generalizing some useful results from the {0, 1}n case.
UR - http://www.scopus.com/inward/record.url?scp=12744277463&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=12744277463&partnerID=8YFLogxK
U2 - 10.1007/s00039-004-0478-3
DO - 10.1007/s00039-004-0478-3
M3 - Article
AN - SCOPUS:12744277463
SN - 1016-443X
VL - 14
SP - 913
EP - 940
JO - Geometric and Functional Analysis
JF - Geometric and Functional Analysis
IS - 5
ER -