A quasi-stability result for dictatorships in \(S_n\)

DOI10.1007/s00493-014-3027-1zbMath1389.05167OpenAlexW2122024168MaRDI QIDQ519995

David Ellis, Ehud Friedgut, Yuval Filmus

Publication date: 31 March 2017

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-014-3027-1

zbMATH Keywords

Fourier transformBoolean functionedge-isoperimetric inequalityintersecting families of permutationstransposition graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of representation theory (05E10) Extremal set theory (05D05) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Symmetric groups (20B30)

Related Items (11)

Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations ⋮ Boolean degree 1 functions on some classical association schemes ⋮ An isoperimetric inequality for conjugation-invariant sets in the symmetric group ⋮ Structure and supersaturation for intersecting families ⋮ Boolean functions on $S_n$ which are nearly linear ⋮ Stability for intersecting families in \(\mathrm{PGL}(2,q)\) ⋮ Unnamed Item ⋮ LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY ⋮ Characterization of intersecting families of maximum size in \(\mathrm{PSL}(2,q)\) ⋮ Geometric stability via information theory ⋮ FKN theorem for the multislice, with applications

Cites Work

• Unnamed Item
• Stability for \(t\)-intersecting families of permutations
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• An Erdős-Ko-Rado-type theorem in Coxeter groups.
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the spectrum of the derangement graph
• On the maximum number of permutations with given maximal or minimal distance
• A note on the edges of the n-cube
• Boolean functions with low average sensitivity depend on few coordinates
• On the degree of Boolean functions as real polynomials
• 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
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Triangle-intersecting families of graphs
• Fourier analysis and large independent sets in powers of complete graphs
• A proof of the Cameron-Ku conjecture
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Generating a random permutation with random transpositions
• Assignment of Numbers to Vertices
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Maximally Connected Arrays on the n-Cube
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Optimal Assignments of Numbers to Vertices
• Intersecting families of permutations
• Intersecting families of permutations

This page was built for publication: A quasi-stability result for dictatorships in \(S_n\)