Robustness of Erdős--Ko--Rado theorems on permutations and perfect matchings
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913401700089856 |
|---|---|
| author | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej Shirazi, Mahsa N. |
| author_facet | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej Shirazi, Mahsa N. |
| contents | 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 $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15739 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robustness of Erdős--Ko--Rado theorems on permutations and perfect matchings Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej Shirazi, Mahsa N. Combinatorics 05D05, 05C80, 05D40 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 $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. |
| title | Robustness of Erdős--Ko--Rado theorems on permutations and perfect matchings |
| topic | Combinatorics 05D05, 05C80, 05D40 |
| url | https://arxiv.org/abs/2406.15739 |