Fourier analysis and large independent sets in powers of complete graphs

DOI10.1016/j.jctb.2007.06.003zbMath1127.05069arXivmath/0612377OpenAlexW2053790252MaRDI QIDQ2464160

Mahya Ghandehari, Hamed Hatami

Publication date: 10 December 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0612377

zbMATH Keywords

Fourier analysisharmonic analysisindependent setsweak product

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

Vertex isoperimetry and independent set stability for tensor powers of cliques, Isoperimetry, stability, and irredundance in direct products, Stability for intersecting families in \(\mathrm{PGL}(2,q)\), Non-trivially intersecting multi-part families, Randomly colouring graphs (a combinatorial view), Not being (super)thin or solid is hard: A study of grid Hamiltonicity, A structure theorem for almost low-degree functions on the slice, A quasi-stability result for dictatorships in \(S_n\)

Cites Work

• Diophantine problems in variables restricted to the values 0 and 1
• Additive bases of vector spaces over prime fields
• Boolean functions with low average sensitivity depend on few coordinates
• Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
• On boundaries and influences
• Graph products, Fourier analysis and spectral techniques
• Stable sets of maximal size in Kneser-type graphs
• On the distribution of the Fourier spectrum of Boolean functions
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Constant depth circuits, Fourier transform, and learnability
• Applications of product colouring
• Advanced Lectures on Machine Learning
• Intersecting families of permutations
• Noise sensitivity of Boolean functions and applications to percolation