Robustness of Erd\H{o}s--Ko--Rado theorems on permutations and perfect matchings

Abstract

The Erd\H{o}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 \(K(n,k)\). In this paper, we investigate the independence number of random spanning subraphs of two other families of graphs whose maximum independent sets satisfy an EKR-type characterization: the derangement graph on the set of permutations in \(\mathrm{Sym}(n)\) and the derangement graph on the set \(\mathcal{M}_{n}\) of perfect matchings in the complete graph \(\mathcal{K}_{2n}\). 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 \(\mathcal{M}_{n}\). In particular, we show that boolean functions whose Fourier transforms are highly concentrated on the first two irreducible modules in the \(\mathrm{Sym}(2n)\) module \(\mathbb{C}[\mathcal{M}_{n}]\), is close to being the characteristic function of a union of maximum independent sets in the derangement graph on perfect matchings.