Independent sets in graph powers are almost contained in juntas
From MaRDI portal
Publication:2427036
DOI10.1007/s00039-008-0651-1zbMath1147.05058MaRDI QIDQ2427036
Oded Regev, Ehud Friedgut, Irit Dinur
Publication date: 14 May 2008
Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00039-008-0651-1
05D05: Extremal set theory
Related Items
Kneser graphs are like Swiss cheese, Vertex isoperimetry and independent set stability for tensor powers of cliques, On symmetric intersecting families of vectors, Hypercontractivity for global functions and sharp thresholds, On the failure of concentration for the \(\ell_\infty\)-ball, Randomly colouring graphs (a combinatorial view), Colouring, constraint satisfaction, and complexity, A new line of attack on the dichotomy conjecture, On the measure of intersecting families, uniqueness and stability, Non-trivially intersecting multi-part families, On arithmetic progressions in symmetric sets in finite field model, Linear-time algorithms for tree root problems, High dimensional Hoffman bound and applications in extremal combinatorics, Independent sets of maximal size in tensor powers of vertex-transitive graphs