Graph products, Fourier analysis and spectral techniques

DOI10.1007/S00039-004-0478-3zbMath1056.05104OpenAlexW2125710943MaRDI QIDQ1764292

Noga Alon, Irit Dinur, Benjamin Sudakov, Ehud Friedgut

Publication date: 24 February 2005

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00039-004-0478-3

zbMATH Keywords

Fourier analysisregular graphsindependent setscoloringsperfect matchingKneser graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Related Items (35)

More complete intersection theorems ⋮ In praise of homomorphisms ⋮ Boolean functions: influence, threshold and noise ⋮ Spatio-spectral limiting on Boolean cubes ⋮ Boolean degree 1 functions on some classical association schemes ⋮ When is a random graph projective? ⋮ Vertex isoperimetry and independent set stability for tensor powers of cliques ⋮ Isoperimetry, stability, and irredundance in direct products ⋮ Maximum independent sets in direct products of cycles or trees with arbitrary graphs ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Bounds on the Twin-Width of Product Graphs ⋮ Graphical designs and extremal combinatorics ⋮ KKL's influence on me ⋮ Stability for intersecting families in \(\mathrm{PGL}(2,q)\) ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Non-trivially intersecting multi-part families ⋮ Asymptotic values of the Hall-ratio for graph powers ⋮ Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ On 3-colorings of direct products of graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Colouring, constraint satisfaction, and complexity ⋮ A structure theorem for almost low-degree functions on the slice ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ Local tail bounds for functions of independent random variables ⋮ On robust colorings of Hamming-distance graphs ⋮ A quasi-stability result for dictatorships in \(S_n\) ⋮ On the Fourier tails of bounded functions over the discrete cube ⋮ On the measure of intersecting families, uniqueness and stability ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Maximum stable sets in analogs of Kneser and complete graphs ⋮ Measure preserving homomorphisms and independent sets in tensor graph powers ⋮ Independent sets of maximal size in tensor powers of vertex-transitive graphs ⋮ Stable sets of maximal size in Kneser-type graphs ⋮ FKN theorem for the multislice, with applications

This page was built for publication: Graph products, Fourier analysis and spectral techniques