A QUASI-STABILITY RESULT FOR DICTATORSHIPS IN Sri DAVID ELLIS, YUVAL FILMUS, EHUD FRIEDGUT

被引：9

作者：

Ellis, David ^{[1
]}

Filmus, Yuval ^{[2
]}

Friedgut, Ehud ^{[3
]}

机构：

[1] Univ London, Sch Math Sci, London WC1E 7HU, England

[2] Inst Adv Study, Sch Math, Princeton, NJ 08540 USA

[3] Weizmann Inst Sci, Fac Math & Comp Sci, IL-76100 Rehovot, Israel

来源：

COMBINATORICA | 2015年 / 35卷 / 05期

关键词：

INTERSECTION-THEOREMS; BOOLEAN FUNCTIONS; FOURIER; FAMILIES; SYSTEMS; PROOF;

D O I：

10.1007/s00493-014-3027-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that Boolean functions on S-n whose Fourier transform is highly concentrated on the first two irreducible representations of S-n are close to being unions of cosets of point-stabilizers. We use this to give a natural proof of a stability result on intersecting families of permutations, originally conjectured by Cameron and Ku [6], and first proved in [10]. We also use it to prove a 'quasi-stability' result for an edge-isoperimetric inequality in the transposition graph on S-n, namely that subsets of S-n with small edge-boundary in the transposition graph are close to being unions of cosets of point-stabilizers.

引用

页码：573 / 618

页数：46

共 34 条

[21] A new proof of the Erdos-Ko-Rado theorem for intersecting families of permutations [J].