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.
Gunderson et al. (Thu,) studied this question.