Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2407.14155 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917727896076288 |
|---|---|
| author | Anderson, Sara Casper, W. Riley Fleyshman, Sam Rathbun, Matt |
| author_facet | Anderson, Sara Casper, W. Riley Fleyshman, Sam Rathbun, Matt |
| contents | We obtain a correspondence between pairs of $N\times N$ orthogonal Latin squares and pairs of disconnected maximal cliques in the derangement graph with $N$ symbols. Motivated by methods in spectral clustering, we also obtain modular conditions on fixed point counts of certain permutation sums for the existence of collections of mutually disconnected maximal cliques. We use these modular obstructions to analyze the structure of maximal cliques in $X_N$ for small values of $N$. We culminate in a short, elementary proof of the nonexistence of a solution to Euler's $36$ Officer Problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Disconnected Cliques in Derangement Graphs Anderson, Sara Casper, W. Riley Fleyshman, Sam Rathbun, Matt Combinatorics Discrete Mathematics Representation Theory 05C69, 05C40, 20C30 We obtain a correspondence between pairs of $N\times N$ orthogonal Latin squares and pairs of disconnected maximal cliques in the derangement graph with $N$ symbols. Motivated by methods in spectral clustering, we also obtain modular conditions on fixed point counts of certain permutation sums for the existence of collections of mutually disconnected maximal cliques. We use these modular obstructions to analyze the structure of maximal cliques in $X_N$ for small values of $N$. We culminate in a short, elementary proof of the nonexistence of a solution to Euler's $36$ Officer Problem. |
| title | Disconnected Cliques in Derangement Graphs |
| topic | Combinatorics Discrete Mathematics Representation Theory 05C69, 05C40, 20C30 |
| url | https://arxiv.org/abs/2407.14155 |