Can I read Robustness of Erd\H{o}s--Ko--Rado theorems on permutations and perfect matchings on EtoBox?

Robustness of Erd\H{o}s--Ko--Rado theorems on permutations and perfect matchings by Gunderson, Karen; Meagher, Karen; Morris, Joy; Pantangi, Venkata Raghu Tej; Shirazi, Mahsa N. is a scholarly article available to read on EtoBox.

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

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

Author

Gunderson, Karen; Meagher, Karen; Morris, Joy; Pantangi, Venkata Raghu Tej; Shirazi, Mahsa N.

Published

2024

Language

EN