Robustness of Erdős–Ko–Rado Theorems on Permutations and Perfect Matchings

ABSTRACT The Erdős–Ko–Rado (EKR) theorem and its generalizations can be viewed as classifications of maximum independent sets in appropriately defined families of graphs, such as the Kneser graph . In this paper, we investigate the independence number of random spanning subgraphs of two other families of graphs whose maximum independent sets satisfy an EKR‐type characterization: the derangement graph on the set of permutations in and the derangement graph on the set of perfect matchings in the complete graph . In both cases, we show there is a sharp threshold probability for the event that the independence number of a random spanning subgraph is equal to that of the original graph. As a useful tool to aid our computations, we obtain a Friedgut–Kalai–Naor (FKN) type theorem on sparse boolean functions whose domain is the vertex set of . In particular, we show that boolean functions whose Fourier transforms are highly concentrated on the first two irreducible modules in the module , is close to being the characteristic function of a union of maximum independent sets in the derangement graph on perfect matchings.